NSOqwq

题解 CF1480A 【Yet Another String Game】

Codeforces Round #700 (Div.2) A 题解

题目大意

有一个字符串 $s$,小A和小B在玩游戏,每人每次能选择字符串里的一个下标,把它改成一个新的字符(不能与原来的字符相等)。下标不能重复选择。

小A在游戏过程中,会尽量使新字符串的字典序最小,而小B会尽量使字符串字典序最大。小A先开始游戏,且小A、小B足够聪明,每次一定能选择最优的方案。求问最终的字符串(即所有下标都被选过以后)是什么。

分析题目

为了使字符串字典序最小/最大,小A和小B一定是选择操作没被改变过的第一个字符。

因为小A先开始游戏,所以她一定会把第一个字符变成类似 a, b 这种字典序最低的字符(实际上,如果原字符不是 a,她一定会把字符改成 a。如果原字符是 a,她会把它改成除它以外最小的 b)。

小B第二个开始游戏,他会对第二个字符进行操作,为了使字典序最大,同理,他一定会把这个字符变成 yz(原字符是 z 时变成 y 避免重复,否则变成 z)。

以此类推……

发现第奇数个字符都变成了 ab,第偶数个字符都变成了 yz

根据推得的这个结论模拟即可。

Code

#include <cstdio>
#include <cstring>
#include <string>
int t;
char a[10001];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%s", a);
        const int len = strlen(a);
        for (int i = 0; i < len; i += 1) {
            if (i % 2 == 0) {
                printf("%c", a[i] == 'a' ? 'b' : 'a');
            } else {
                printf("%c", a[i] == 'z' ? 'y' : 'z');
            }
        }
        printf("\n");
    }
    return 0;
} // qwq

2021-02-08 08:54:08 in 题解