#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
int v[32770];
int l[32770];
int k;
map<int,int> m;
int main()
{
	string rule[10];
	char str[20];
	char ans[50];
	char min[50];
	int n,s,i,t,q,j,b,cyc;
	
	while(cin>>n){
		cin>>str;
		m.clear();
		t=0;
		for(i=0;i<8;i++) cin>>rule[i];
		min[0]=0;
		sort(rule,rule+8);
		
		cin>>s;
		for(i=0;i<n;i++) t=t*2+str[i]-'a';
		memset(v,0,sizeof(v));
		memset(l,0,sizeof(l));
		k=1;
		while(k<=s){
			q=0;
			for(i=0;i<n;i++){
				j=0;
				b=n-1-i;
				if (t&(1<<((b+2)%n))) j+=4;
				if (t&(1<<b)) j+=2;
				if (t&(1<<((b-1+n)%n))) j+=1;
				q=q*2+rule[j][3]-'a';
			}
			if (v[q]){cyc=k-m[q];break;}
			v[q]=1;
			m[q]=k;
			l[k++]=q;
			t=q;
		}
		
		if (s==0) b=t;
		else if (s<=k) b=l[s];
		else{
			if ((s-m[q]+1)%cyc==0) s=m[q]-1+cyc;
			else s=m[q]-1+(s-m[q]+1)%cyc;
			b=l[s];
		}
		
		for(i=n-1;i>=0;i--) if (b&(1<<i)) ans[n-1-i]='b';else ans[n-1-i]='a';
		for(i=n;i<2*n;i++) ans[i]=ans[i-n];
		ans[2*n]=0;
		
		for(i=0;i<n;i++)
			if (i==0) strncpy(min,ans,n);
			else if (strncmp(ans+i,min,n)<0) strncpy(min,ans+i,n);
		min[n]=0;
		
		for(i=0;i<n;i++) cout<<min[i];
		cout<<endl;
	}
	return 0;
}

• 此题数据比那边多不少 (0) hawk 2005-04-06 17:36:14