POJ 1026 Cipher（更换）

                                                               Cipher

Description

Input

Output

Sample Input

10
4 5 3 7 2 8 1 6 10 9
1 Hello Bob
1995 CERC
0
0

Sample Output

BolHeol  b
C RCE

第一次做这样的多个循环节。对每一个循环节中的元素分开求解的题目，记录一下。

题意：给出一个n个数的置换，依照置换规则把一个字符串置换k次，假设字符串的长度不足n，则在字符串末尾补空格。直到长度为n。求置换k次之后的字符串是什么。

分析：假设直接依照题目描写叙述的模拟，肯定会超时。
对整个字符串置换，能够转换为对每一个循环节进行置换。由于一个循环节里面的元素,对其它元素没有影响，这样我们就能够先求出全部的循环节和每一个循环节中的元素及循环节的长度。然后对每一个循环节中的元素进行置换。一个循环节中的元素置换k次，等价于每一个元素置换k%（这个元素所在循环节的长度）次，这样模拟次数变得非常小。就能够模拟了。

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 215;
char str[N];  //原始字符串
char ans[N]; //置换后的字符串
int key[N];  //置换规则
int cnt; //循环节数量
int num[N]; //每一个循环节的长度
int cir[N][N]; //cir[i][j]表示第i个循环节中的第j个元素相应的位置
int vis[N]; //记录每一个数是否訪问过

int n;

void get_circle() {
    memset(vis, 0, sizeof(vis));
    memset(num, 0, sizeof(num));
    cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            vis[i] = 1;
            num[cnt] = 0;
            int tmp = key[i];
            cir[cnt][num[cnt]++] = tmp;
            while(!vis[tmp]) {
                vis[tmp] = 1;
                tmp = key[tmp];
                cir[cnt][num[cnt]++] = tmp;
            }
            cnt++;
        }
    }
}

int main() {
    int k;
    while(~scanf("%d",&n) && n) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &key[i]);
        get_circle();
        while(~scanf("%d", &k) && k) {
            gets(str);
            int len = strlen(str);
            for(int i = len; i <= n; i++)
                str[i] = ' ';
            for(int i = 0; i < cnt; i++) {
                for(int j = 0; j < num[i]; j++) {
                    ans[cir[i][(j+k)%num[i]]] = str[cir[i][j]];
                } //第i个循环节中的第j个元素置换k次之后的位置为第（j+k）% num[i]
            }
            ans[n+1] = '\0';
            printf("%s\n", ans+1);
        }
        printf("\n");
    }
    return 0;
}