Cipher--POJ 1026

时间：2010-09-23 来源：勇泽

1、题目类型：字符串、置换群。

2、解题思路：（1）根据输入n个编码的顺序分别记录每单个字符置换的周期，记录为Cy[i]；（2）编码次数k对Cy[i]分别进行求余，余数即为此字符k次置换后的位置。

3、注意事项：注意题意理解，题中说说的是将所有成双的sock按序输出，而不是单个输出其最小的两双。

4、实现方法: 不可对整个序列求周期（此时的周期为n个单个字符周期的最小公倍数），否则TLE。

#include<iostream>
#include<string>
using namespace std;

int n;
int pos[210],Cy[210];

void Solve()
{
    int k,i,j,m,len;
    char str[210],ans[210];
    while(cin>>k && k)
    {
        getchar();
        gets(str);
        len=strlen(str);
        while(len<n)
        {
            str[len++]=' ';
        }
        str[len]='\0';
        for(i=0;i<n;i++)
        {
            m=k%Cy[i];            
            j=i;
            while(m--)
                j=pos[j]-1;
            ans[j]=str[i];
        }
        ans[n]='\0';
        cout<<ans<<endl;
    }
}

int main()
{
    int i,j;
    while(cin>>n && n)
    {    
        memset(Cy,0,sizeof(Cy));
        for(i=0;i<n;i++)
            cin>>pos[i];
        for(i=0;i<n;i++)
        {
            j=i;
            while(pos[j]!=i+1)
            {
                j=pos[j]-1;
                Cy[i]++;
            }
            Cy[i]++;
        }
        Solve();
        cout<<endl;
    }
    return 0;
}