跳转至

I - 完美回文

基本信息

题目出处2022 ICPC 亚洲区域赛南京站
队伍通过率464/465 (99.8%)

题解

\(f(A, d)\) 是回文串,说明 \(a_d = a_{(d + n - 1) \bmod n}\)。因此若 \(A\) 是完美回文,说明 \(a_0 = a_1 = \cdots = a_{n - 1}\)

因此枚举最终将 \(A\) 统一成哪个字符 \(c\),我们需要将所有非 \(c\) 的字符都变成 \(c\)。答案就是 \(\min(n - cnt_c)\),其中 \(cnt_c\) 是字符 \(c\)\(A\) 中出现的次数。

复杂度 \(\mathcal{O}(n + |\Sigma|)\),其中 \(|\Sigma|\) 是字符集大小。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
using namespace std;

int n, ans;
char s[MAXN + 10];

int cnt[26];

void solve() {
    scanf("%s", s + 1); n = strlen(s + 1);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) cnt[s[i] - 'a']++;

    ans = n;
    for (int i = 0; i < 26; i++) ans = min(ans, n - cnt[i]);
    printf("%d\n", ans);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}