题解：P14225 [ICPC 2024 Kunming I] 左移 2

· · 题解

P14225 [ICPC 2024 Kunming I] 左移 2

题目描述

给定一个由小写字母组成的字符串，称该字符串是美丽的，若字符串中每一对相邻的字符都不相同。例如，\texttt{icpc} 和 \texttt{kunming} 是美丽的，但 \texttt{hello} 不是，因为它的第 3 个和第 4 个字符相同。

给定由小写英文字母组成的，长度为 n 的字符串 S = s_0s_1\cdots s_{n-1}，令 f(S, d) 表示将 S 左移 d 次后获得的字符串。也就是说 f(S, d) = s_{(d+0)\bmod n}s_{(d+1)\bmod n}\cdots s_{(d+n-1)\bmod n}。

令 g(S, d) 表示将 f(S, d) 变得美丽的最小操作次数。每次操作中，您可以将 f(S, d) 中的任意一个字符改为任意小写字母。

找到一个非负整数 d 最小化 g(S, d)，并输出这个最小化的值。

输入格式

有多组测试数据。第一行输入一个整数 T 表示测试数据组数。对于每组测试数据：

第一行输入一个仅由小写字母组成的字符串 s_0s_1\cdots s_{n-1}（1 \le n \le 5 \times 10^5）。

保证所有数据 n 之和不超过 5 \times 10^5。

输出格式

每组数据输出一行一个整数，表示最小的 g(S, d)。

输入输出样例 #1

输入 #1

3
abccbbbbd
abcde
x

输出 #1

2
0
0

说明/提示

对于第一组样例数据，考虑 d = 5。有 f(S, 5) = \texttt{bbbdabccb}。对于这个字符串，我们可以将它的第 2 个字符改成 \texttt{x}，并将它的第 8 个字符改成 \texttt{y}。这样字符串就会变成 \texttt{bxbdabcyb}，是一个美丽的字符串。

思路

字符串中不能有两个相邻的相同字符，所以我们将字符串首尾相接（长度乘 2），然后所有由相同字符组成的连续字符串统计起来。结果发现，如果我们要使字符串符合题意，在一段长度为 n 的连续字符串中，我们需要修改 \frac{n}{2} 个字符。

然后考虑“左移”这一操作对答案的影响。

当我们将一个偶数长度的字符串左移到字符串首尾时，可以使其变为两个奇数长度字符串，就能使操作次数减 1（例如，设 n 为偶数，a，b 为奇数，n=a+b，整数运算下 \frac{n}{2}-1=\frac{a}{2}+\frac{b}{2}）。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){
        cin>>s;
        s+=s;
        n=s.size();
        if(n==2){
            cout<<"0\n";
            continue;
        }
        int ans=0,cnt=1;
        bool f=0;
        for(int i=1;i<n;i++){
            if(s[i]==s[i-1])cnt++;
            else{
                if(cnt%2==0)f=1;
                ans+=cnt/2;
                cnt=1;
            }
        }
        ans+=cnt/2;
        if(f)ans--;
        cout<<ans/2<<'\n';
    }
    return 0;
}