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

CPP

3
abccbbbbd
abcde
x

输出 #1

CPP

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}

）。

代码

CPP

#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;
}

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

文章操作