poj 1026 Cipher

时间：2010-10-21 来源：niuniu2006t

今天上体育课，羽毛球，哈哈，虽然被虐，但是学会发球了，发现我是后期型的，嘎嘎，开始被虐，后来反虐成功，主要对手累不行了，我还颠儿颠儿的。。。。回来继续a道题，水题，贡献了一个tle和wa后ac。这道题说，有n个数字 a1,a2,,,,an 然后给你一个字符串s和一个数字k 然后先把字符串跟上面的数字对齐，s不够的，拿空格补全。然后进行转换，是这样转换的，对于s每个元素，把这个元素放到另一个字符串的第m个位置，m就是他对应的那个数字。对于k呢，就是这样重复的次数。开始简单模拟，果断的tle了。因为k可以很大。其实对于每个字符来说，他每转换一次，就可能换一个位置。那么至多换n次，就回到原来位置了。这样就分别对每个字符计算周期，然后存储起来。然后用k对每个字符的周期取模就可以了。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

char arr[2][210];
int key[210];
int round[210];
int block;
int k;

int main()
{
    // freopen("in","rw",stdin);

    while(cin>>block){
    if(block==0)
     break;

    for(int i=0;i<block;++i)
     cin>>key[i];
    for(int i=0;i<block;++i){
     int count =0;
     int index=i;
     while(++count){

        index=key[index];
        index--;
        if(index==i)
         break;

     }
     round[i]=count;
    }

    while(cin>>k){
     if(k==0)
        break;
     getchar();
     cin.getline(arr[0],block+1);
     int len = strlen(arr[0]);
     for(int j=len;j<block;++j)
        arr[0][j]=' ';
     arr[1][block]=NULL;
     for(int j=0;j<block;++j){
         int cnt = k%round[j];
         int index=j;
         for(int t=0;t<cnt;++t){
         index = key[index];
         index--;
         }
         arr[1][index]=arr[0][j];
     }
     cout<<arr[1]<<endl;
    }
    cout<<endl;
    }
    return 0;
}