题解 CF1389C 【Good String】

54 阅读 0 评论 36 点赞

我是靠谱客的博主痴情棉花糖，最近开发中收集的这篇文章主要介绍题解 CF1389C 【Good String】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

简要题意：

对于一个字符串 $t_1,t_2,cdots,t_n$ ，

我们定义它的右移为 $t_n,t_1,cdots,t_{n-1}$ ；

我们定义它的左移为 $t_2,t_3,cdots,t_{1}$ 。

现在请问对于给出的一个字符串，最少删掉多少个字符才能是这个字符串的左移和右移完全相同？

我们来分析一下性质，比较一下右移和左移

右移： $t_n,t_1,cdots,t_{n-1}$

左移： $t_2,t_3,cdots,t_{1}$

要使这 $2$ 个东西相同就必须使得 $t_2=t_n,t_1=t_3,cdots,t_{n-1}=t_1$

我们举个具体的例子，假设 $n = 8$ 。

右移： $t_8,t_1,t_2,t_3,t_4,t_5,t_6,t_7$

左移： $t_2,t_3,t_4,t_5,t_6,t_7,t_8,t_1$

显然， $t_2=t_4=t_6=t_8$ ， $t_1=t_3=t_5=t_7$ 。

可以证明当 $n$ 为偶数时，这个字符串的循环节必须为 $2$ 。

我再来试试 $n = 7$ 。

右移： $t_7,t_1,t_2,t_3,t_4,t_5,t_6$

左移： $t_2,t_3,t_4,t_5,t_6,t_7,t_1$

显然， $t_1=t_3=t_5=t_7=t_2=t_4=t_6$

可以证明当 $n$ 为奇数时，这个字符串的循环节必须为 $1$ 。

这 $2$ 个东西笔者都试着证明了一下，有些麻烦，这里就不放了。

// Problem: C. Good String
// Contest: Codeforces - Educational Codeforces Round 92 (Rated for Div. 2)
// URL: https://codeforc.es/contest/1389/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
const int MAXN=2e5+10;
int s[11][2];
int work(){
memset(s,0,sizeof(s));
string st;cin>>st;
int n=st.size(),ans=n;
st=' '+st;
for(int i=0;i<=9;i++){
int s=0;
for(int j=1;j<=n;j++)
if(st[j]!=char(i+48))s++;
ans=min(ans,s);
}
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++){
int s=0;
for(int k=1;k<=n;k++){
if(s%2==0){
if(st[k]==char(i+48))s++;
}else{
if(st[k]==char(j+48))s++;
}
}
if(s%2==1)s--;
ans=min(ans,n-s);
}
cout<<ans<<endl;
return 0;
}
int main(){
int T;read(T);
while(T--){
//memset
work();
}
return 0;
};