CF496B Secret Combination

_JF_ · 2023-11-27 13:34:16 · 题解

CF496B Secret Combination

你说的对，但是转眼之间，又要月考了。

来一个 O(n) 的做法。

首先发现两个操作是没有互相影响的，就把他们分开来看。

如果先进行操作二的话，发现只会至多进行 10 次，这个字符串就会变成原来的样子，所以我们就只做 10 次。

每一次加完后，在这个基础上找最小，相当于把这个字符串看成一个环，从某一个位置开始走一圈，实际上就是找这个字符串的最小表示法。这就只用 O(n) 的时间。

那对 10 种情况取最小即可。

当然还有一种做法就是，先看 1 操作，再看 2 操作，那就是钦定字符串的任意一个位置变为第一个字符，然后让他变成 0 取最小，不过这样是 O(n^2) 的了。

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
char s[N],S[N];
int n;
bool vis=false;
string ans;
void Slove(string k){
    for(int i=0;i<k.length();i++)
        S[i+1]=S[i+n+1]=k[i];
    int i=1,j=2;
    while(i<=n&&j<=n){
        int k=1;
        while(S[i+k-1]==S[j+k-1]&&k<=n) k++;
        if(k>n) break;
        if(S[i+k-1]<S[j+k-1])   j=j+k;
        else    i=i+k;
        if(i==j)    j++;
    }
    int num=min(i,j);
    string num1;
    for(int len=1;len<=n;len++) num1+=S[num+len-1];
    if(vis==false){
        vis=true,ans=num1;
        return ;
    }
    ans=min(ans,num1);
    return ;
}
int main(){
    cin>>n;
    scanf("%s",s+1);
    for(int num=0;num<=9;num++){
        string k;
        for(int i=1;i<=n;i++){
            k+=char((int(s[i]-'0')+num)%10+'0');
        }
        Slove(k);
    }   
    cout<<ans<<endl;
}