uva 306 - Cipher(周期） - c++编程基础

题目大意：给出n，以及a1 ~ an，然后给出k，若k不为0的话，会有一个字符串，按照给出的a方式编码k次，输出所得字符串。

解题思路：这题和我刚做的一题有点像，uva 10205 - Stack 'em Up，不过那道题是用模拟的方式，这题刚开始用了模拟，结果超时了，后来想到说，因为a1 ~ an为不等的1~n，所以一定存在一个周期，可以通过周期的性质缩短时间。

#include   
#include   
const int N = 205;  
  
int n, k, a[N], t[N];  
char ans[N];  
  
void init() {  
    int cnt;  
    for (int i = 1; i <= n; i++)  
        scanf("%d", &a[i]);  
    for (int i = 1; i <= n; i++) {  
        int p = a[i];  
        for (cnt = 1; p != i; cnt++, p = a[p]);  
        t[i] = cnt;  
    }  
}  
  
void solve() {  
    char tmp[N], code[N];  
    int p[N], cnt;  
    memset(tmp, ' ', sizeof(tmp));  
    for (int i = 1; ans[i]; i++)  
        tmp[i] = ans[i];  
    for (int i = 1; i <= n; i++) p[i] = i;  
  
    for (int i = 1; i <= n; i++) {  
        cnt = k % t[i];  
        for (int j = 0; j < cnt; j++) p[i] = a[p[i]];  
    }  
  
    for (int i = 1; i <= n; i++)  
        code[p[i]] = tmp[i];  
    for (int i = 1; i <= n; i++)  
        printf("%c", code[i]);  
    printf("\n");  
}  
  
int main () {  
    while (scanf("%d", &n), n) {  
        init();  
        while (scanf("%d", &k), k) {  
            gets(ans);  
  
            solve();  
  
            memset(ans, 0, sizeof(ans));  
        }  
        printf("\n");  
    }  
    return 0;  
}