Codeforces Round #705 K-beautiful Strings 模拟

题意

给你一个n和k。n表示字符串长度。

定义beautiful string:如果一个串里面,所有字母出现的次数都能被k整除,这个字符串就是美的。

定义字符串大小(字符串长度都是n):以第一个不一样的字符算,第一个不一样的字符小的串就小。

现在要找:大于或等于输入s的,最小的,美的,串。

题解

显然是贪心,但是这个贪心比较显然。更多还是细节处理和模拟……

  1. 首先如果n和k都不整除就不用看了。一定是-1。
  2. 然后 对于本身就美的,也不用看了,直接输出s。
  3. 然后就开始正题了:
    1. 首先,肯定是找改动点。也就是和原串第一个不一样的点。从后往前找,改动点越后面当然越好。
    2. 然后,看前面缺什么,补什么就好了。

但是里面其实一万个细节

首先,改动点的选择。改动点要考虑改动后是否能填前面的坑。比如对于ddbccc和3。当考虑改b的时候,如果改成c,那么后面要填坑的是1个d和2个b。而如果b改成d,那么后面什么坑都不用填。
相关处理:

    private static int getChangePos() {
        for (int i = n - 1; i >= 1; i--) {
            int now = s[i] - 'a';
            if (now == 25) continue;

            int totalNeed = 0;
            boolean useful = false;
            for (int j = 0; j < 26; j++) {
                int need = getNeed(i - 1, j);
                totalNeed += need;
                if (need != 0 && j > now) {
                    useful = true;
                }
            }
            if (useful) totalNeed -= 1;
            else totalNeed += m - 1;

            int afterMe = n - 1 - i;
            if (totalNeed <= afterMe) {
                return i;
            }
        }
        return 0;
    }

再有在真正改改动点的时候思路其实又不一样了。因为改动点其实不一定非要填前面的坑。只要后面能填上,就越小越好。
相关处理:

            int afterMe = n - 1 - changeAtMe;

            int currentChar = s[changeAtMe] - 'a';
            int nextChar = currentChar + 1;

            int totalDirectNeed = 0;
            for (int i = 0; i < 26; i++) {
                totalDirectNeed += getNeed(changeAtMe - 1, i);
            }
            if (totalDirectNeed + m - 1 > afterMe) {
                for (int i = nextChar; i < 26; i++) {
                    if (getNeed(changeAtMe - 1, i) != 0) {
                        nextChar = i;
                        break;
                    }
                }
            }

            count[changeAtMe][currentChar]--;
            count[changeAtMe][nextChar]++;
            s[changeAtMe] = (char) (nextChar + 'a');

最后,填坑要从后面往前填。坑填完了,就全部填a。

代码

我好菜啊。。。这个题显然是个水题,但是写了好久,而且还挂了几发。。。

Submission #110597170 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论