Shiroha白羽的博客
·
Codeforces Round 910 (Div. 2)
💡
原文中文，约4800字，阅读约需12分钟。
📝
内容提要
给定一个由A和B组成的字符串，找到将字符串转换为所需模式所需的最小操作次数。解决方案涉及计算字符串中B的数量，并将其与所需模式进行比较。如果计数匹配，则不需要操作。否则，迭代字符串并调整计数直到匹配所需模式。
🎯
关键要点
- 给定一个由A和B组成的字符串，找到将字符串转换为所需模式所需的最小操作次数。
- 解决方案涉及计算字符串中B的数量，并将其与所需模式进行比较。
- 如果计数匹配，则不需要操作；否则，迭代字符串并调整计数直到匹配所需模式。
- 允许不断的差分一个数组中的值，问至少需要拆多少次，才能让数组非递减。
- 从后往前遍历，如果当前值比后面的值大，则均匀的拆成x份，使得恰好比后面的值小或者相同。
- 有一个棋盘，允许在棋盘的边上染色，使得从最左上角到最右下角的路径长度恰好为k，并且路径上红蓝间隔染色。
- 需要兼容两种情况：k恰好是最短的距离加上4n，或者不满足4n的情况。
- 有两个数组，允许交换b数组中的两个值一次，问使得|a_i - b_i|的和最大。
- 需要找到最大的a_j - b_i，并证明可以恒定满足a_i < b_i。
- 有一个字符串a，允许选择片段排序或删掉一个指定的字符，问是否能够变成b字符串。
- 选择片段排序最有用的是选择两个相邻的字母排序，以最小的改动将一个值往前移动。
➡️
