1026 polya.cpp

各种算法

#include"stdio.h"
#include <map>
#define N 256

int a[N] ={0};
int cyc[N] = {0};
char ch[N] = {0};

int circle(int n)//记录各循环周期
{	int i,k,t,j;int temp[N];
	memset(cyc,0,sizeof cyc);
	for(i = 0;i < n; i++){
		if(cyc[i])continue;
		k = 0; t = 0; j = i;
		do{	
			j = a[j];
			k++;
			temp[t++] = j;
		}
		while(j != i);
		while(t--)
		{	cyc[temp[t]] = k;
		}
	}
	return 1;
}
int leaving(char ch[],int n,int mov)//求剩余转移次数
{	int i,j,k;int rem[N];char b[N];
	for(i = 0;i < n; i++)
		rem[i] = mov % cyc[i];
	for(i = 0;i < n; i++){
		k = i;
		for(j = 0;j < rem[i]; j++) 
			k = a[k];
		b[k] = ch[i];
	}
	b[n] = 0;
	printf("%s\n",b);
	return 1;
}
int main()
{	int i,j,mov,n;char ch[N];
	while(scanf("%d",&n),n)
	{	
		for(i = 0;i < n; i++) {	scanf("%d",&a[i]); a[i]--;}
		circle(n);
		while(scanf("%d",&mov),mov)
		{	getchar();
			gets(ch);
			for(j = strlen(ch); j < n; j++) ch[j] = ' ';
			leaving(ch,n,mov);
		}
		printf("\n");
	}
	return 1;
}