UVa 306 - Cipher
传送门
题意
先给一串数字，意思是每一轮变换的时候对应这个数字的字母变换的位置。
然后给n句字母，问经过k次变换后长什么样。
思路
对于每个位置，最多换200次就会回到原位，所以只要求出每个位置的周期再算出变换$k \% circle$时的位置即可。
不过求周期的时候想晕了好久。。。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#pragma comment(linker, "/STACK:102400000,102400000")
const int MAXN = 200 + 10;
int prcp[MAXN], refer[MAXN], len[MAXN], n;
char ans[MAXN], str[MAXN];
void GetCircle()
{
int i, j;
for (i = 1; i <= n; i++)
scanf("%d", &prcp[i]);
for (i = 1; i <= n; i++)
{
int t = i, cnt = 1;
while (prcp[t] != i)
{
t = prcp[t];
cnt++;
}
len[i] = cnt;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
int i, j, k;
while (scanf("%d", &n), n)
{
GetCircle();
while (scanf("%d", &k), k)
{
gets(str);
for (i = strlen(str); i <= n; i++)
str[i] = 32;
for (i = 1; i <= n; i++)
refer[i] = i;
for (i = 1; i <= n; i++)
for (j = 1; j <= k % len[i]; j++)
refer[i] = prcp[refer[i]];
for (i = 1; i <= n; i++)
ans[refer[i]] = str[i];
for (i = 1; i <= n; i++)
putchar(ans[i]);
printf("\n");
}
puts("");
}
return 0;
}