POJ 1026 Cipher（置换群）

题目链接

题意 ：由n个数字组成的密钥，每个数字都不相同，都在1～n之间，有一份长度小于等于n的信息，要求将信息放到密钥下边，一一对应，信息不足n的时候补空格，然后将位置重新排列，将此过程重复k次，求最后的字符串序列，最后的空格不用输出。

思路 ：如果按照最原始的求循环结的话会超时，因为k值范围很大。所以要用置换群，把每个的元素的循环求出来，直接对其取余即可。会3270的话，这个题理解起来挺容易的。

 //

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 using namespace std ;

 int a[],ch[] ;

 char sh[] ,pri[];

 void xh(int n)

 {

     for(int i =  ; i <= n ; i++)

     {

         int cnt =  ;

         int pos = a[i] ;

         while(pos != i)

         {

             pos = a[pos] ;

             cnt ++ ;

         }

         ch[i] = cnt ;

     }

 }

 int main()

 {

     int n,k ;

     while(~scanf("%d",&n) && n)

     {

         memset(a,,sizeof(a)) ;

         for(int i =  ; i <= n ; i++)

             scanf("%d",&a[i]) ;

         //memset(sh,0,sizeof(sh)) ;

         xh(n) ;

         while(~scanf("%d",&k) && k)

         {

             getchar() ;

             gets(sh+) ;

             for(int i = strlen(sh+) +  ; i <= n ; i++ )

                 sh[i] = ' ' ;

                 sh[n+] = '\0' ;

             for(int i =  ; i <= n ; i++)

             {

                 int pos = i ;

                 for(int j =  ; j < k % ch[i] ; j ++)

                     pos = a[pos] ;

                 pri[pos] = sh[i] ;

             }

             pri[n+] = '\0' ;

             for(int i =  ; i <= n ; i++)

                 printf("%c",pri[i]) ;

             puts("") ;

         }

         puts("") ;

     }

     return  ;

 }