题解 UVA306 【Cipher】

zhikong · 2021-01-06 23:15:02 · 题解

题目相当于是求一个串按某种指定方式换位多次后形成的串。

因为 k 很大，所以不能直接模拟。

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

时间复杂度为 O(nlogk)

#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;
}