题目大意就是
给出1~n的置换序列, 然后给出一个整数k,和一个串
问置换k次后的串是什么样子的。
首先,给出的串的长度是小于等于n的,不足的位置要补上空格。
然后置换k次,不是直接就循环着置换,因为置换内的每个循环都是有一定长度的,如果超过这个长度的置换次数,必然会和前面的某个状态一样,所以对每个循环,如果长度为len,循环内的元素只需要置换k%len次即可。
第一次看置换群得概念,不由得想起来之前的一道题,就是给出一组无序的数,任意两个数之间可以互相交换位置,问最少要交换多少次达到升序状态,那么这就显然是一个置换的问题了,只需要求出题目中循环的个数,用元素个数-循环个数即为所求了。那么如果题目要求只能相邻的两个数之间进行交换,就是树状数组或者归并排序的问题了。
/* ID: sdj22251 PROG: inflate LANG: C++ */ #include <iostream> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cmath> #include <ctime> #define MAXN 1100 #define INF 1000000000 #define eps 1e-7 #define PI 3.1415926535898 using namespace std; int n, k, a[205], l[205]; char s[205], ans[205]; void zhihuan() { for(int i = 1; i <= n; i++) { int t = a[i]; int cnt = 1; while(t != i) { cnt++; t = a[t]; } l[i] = cnt; } } int main() { while(scanf("%d", &n) != EOF && n) { for(int i = 1; i <= n; i++) scanf("%d", &a[i]); zhihuan(); while(scanf("%d", &k) != EOF && k) { getchar(); gets(s + 1); int len = strlen(s + 1); for(int i = len + 1; i <= n; i++) s[i] = ' '; s[n + 1] = '\0'; for(int i = 1; i <= n; i++) { int pos = i; for(int j = 0; j < k % l[i]; j++) pos = a[pos]; ans[pos] = s[i]; } ans[n + 1] = '\0'; puts(ans + 1); } puts(""); } return 0; }