CF1997A Strong Password 题解

题意

给定一个由小写字母组成的字符串 $s$，你可以在其任意位置插入一个小写字母（包括最前面和最后面），最大化新字符串的权值。输出任意一个权值最大的新字符串。

权值定义：

• 若某个字符是第一个字符，或与前一个字符不同，贡献 $2$ 点。
• 若与前一个字符相同，贡献 $1$ 点。

分析

设原串长为 $n$，权值为 $W$。

在位置 $i$（$0\le i\le n$，表示在 $s_i$ 之后，$i=0$ 表示最前）插入字符 $c$：

• 插入字符 $c$ 的贡献：若 $i=0$（首位）则固定 $2$；否则与 $s_i$ 比较，不同则 $2$，相同则 $1$。
• 原 $s_{i+1}$ 的前驱由 $s_i$ 变为 $c$，贡献可能变化。

分类讨论权值增量 $\Delta$：

结论：优先在相邻相同字符之间插入一个不同字符，可得 $+3$；若无相邻相同，则在首尾插入一个与邻居不同的字符，可得 $+2$。不存在更大的增量。

构造方法

1. 扫描 $s$，找到第一个 $i$ 满足 $s_i = s_{i+1}$，在它们之间插入一个不同于 $s_i$ 的字符（例如 $s_i$ 是 'a' 则插 'b'，否则插 'a'），输出结果。
2. 若不存在相邻相同，在 $s$ 开头插入一个不同于 $s_1$ 的字符，输出结果。

时间复杂度 $O(|s|)$。

代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.size();

    // 找相邻相同字符
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == s[i + 1]) {
            char c = (s[i] == 'a') ? 'b' : 'a';
            s.insert(s.begin() + i + 1, c);
            cout << s << '\n';
            return;
        }
    }

    // 无相邻相同，在开头插入不同字符
    char c = (s[0] == 'a') ? 'b' : 'a';
    cout << c << s << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}