UVA306 题解

Fengxiang008 · 2021-07-25 23:13:00 · 题解

思路1：（TLE）

这题可以用模拟做，但是会超时（血的教训）。

思路2：(TLE）

如果每次模拟都记录下字符串还会内存超限，后来得知是置换群，每个字符的出现都是有周期的，这样整个串的周期就是所有字符周期的最小公倍数数。如果求了串的周期，k 取模之后再模拟，当然还是会超时。

思路3：（正解）

我们考虑样例，对于一个以 4 5 3 7 2 8 1 6 10 9 为标准的转移，我们若转移两次，就相当于进行一次以 7 5 3 1 2 8 4 6 10 为标准的转移，并且每次换的方式是固定的，所以满足结合律，可以用快速幂来解决。

时间复杂度为 O(n \times logk)

正解代码：

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int a[M],b[M],ans[M],d[M];
char s[M];
int n,k;
void solve1(){
    for(int i=1;i<=n;i++){
        a[i]=ans[i];
    }
    for(int i=1;i<=n;i++){
        ans[b[i]]=a[i];
    }
}
void solve2(){
    for(int i=1;i<=n;i++){
        a[i]=b[i];
    }
    for(int i=1;i<=n;i++){
        b[i]=a[b[i]];
    }
}
int main(){
    while(1){
        scanf("%d",&n);
        if(!n) return 0;
        for(int i=1;i<=n;i++){
            scanf("%d",&d[i]);
        }
        while(1){
            scanf("%d",&k);
            getchar();
            if(!k) break;
            for(int i=1;i<=n;i++){
                ans[i]=i;
                b[i]=d[i];
            }
            int len=0;  
            while((s[++len]=getchar())!='\n');
            len--;
            if(len<n){
                for(++len;len<=n;++len){
                    s[len]=' ';
                }
            }
            while(k){
                if(k&1){
                    solve1();
                }
                solve2();
                k>>=1;
            }
            for(int i=1;i<=n;i++){
                printf("%c",s[ans[i]]);
            }
            printf("\n");
        } 
        printf("\n");
    }
    return 0;
}