出题人题解|完美洗牌

【ZSROI R1-A】完美洗牌

注意到题目描述中有这一句话：可以证明最小的 $k$ 一定小于 $n$。

每次洗牌操作是 $O(n)$ 的，总共就是 $O(nk)$，约等于 $O(n^2)$

所以直接模拟一定可以通过。

#include<bits/stdc++.h>
using namespace std;
int n;
char a[1009],b[1009],c[1009];
void solve(){
    int ans = 0;
    while(1){
        ++ans;
        if(ans!=1){
            bool f = 0;
            for(int i = 1;i<=n;++i){
                if(a[i]!=c[i]){
                    f = 1;
                    break;
                }
            }
            if(f == 0){
                cout<<ans-1<<endl;
                return ;
            }
        }
        for(int i = 1;i<=n/2;++i){
            b[2*i-1] = a[i];
        }
        for(int i = n/2+1;i<=n;++i){
            b[2*i-n] = a[i];
        }
        for(int i = 1;i<=n;++i) a[i] = b[i];
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        cin>>a;
        for(int i = strlen(a);i>=1;--i){
            a[i] = a[i-1];
            c[i] = a[i];
        }
        solve();
    }
}

时间复杂度：$O(Tn^2)$