codeforces-Ed92-C

codeforces-Ed92-C

七月 30, 2020

C. Good String

题意
定义good string

符合某个字符串t1 t2 t3,,, tn变成两个新串s1,s2后s2=s1

其中s1=tn t1 t2…. tn-1 和s2= t2 t3 … tn t1

现在给出 一个只含有0-9的字符串

问要删取最少几个字符能让他变成good string

题解

构成good string只有两种构造

变成xxxxxx or xyxyxyxyxy

枚举保留那两个数字xy 更新最少删除的方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
ll data[Max];
int num[10];
/*
*/
int main() {
    Turnoff;
    int t;cin>>t;
    while(t--){
     	string s,ns="";cin>>s;
        int len=s.size();
        ns=s[len-1]+s.substr(0,len-1);
        //ns2=s.substr(1,len)+s[0];
        //cout<<ns<<endl;
        for(int i=0;i<10;i++)num[i]=0;
        for(auto i:s)num[i-'0']++;
        int ans=2e5;
        for(int i=0;i<10;i++)ans=min(ans,len-num[i]);
        for(char a='0';a<='9';a++){
            for(char b='0';b<='9';b++){
                if(a==b)continue;
                int sum=0;
                bool flag=0;
                for(int i=0;i<len;i++){
                    if(ns[i]==a)flag=1;
                    else if(flag&&ns[i]==b)sum+=2,flag=0;
                }
                //cout<<a<<" "<<b<<" "<<len-sum;
                ans=min(ans,len-sum);
            }
        }
        cout<<ans<<endl;
    }
}