Decode the Strings

http://acm.hdu.edu.cn/showproblem.php?pid=2371

题意：给出一个长度为n的字符串（标号为1~n），以及n个数代表字符串的变换规则，问该字符串是由哪个字符串按照变换规则变换m次得到的？如n=5,m=3,变换规则 2 3 1 5 4 （生成的下一个字符串即按照此标号的顺序对应的串）， “hello" -> "elhol" -> "lhelo" -> "helol", 故helol 是由"hello''变换3次得到的。

思路：此类型的题目一般是找循环节，但是此题不能找字符串的循环节，因为数据范围太大，找字符串的循环节会超时。由于只有80个字符，所以可以找每个字符的循环节，并在查找过程中记录下来该字符在变换t次后所在的位置，这样就能通过m对循环节取余，找到该字符在目标串中的位置。

 #include <stdio.h>

 #include <string.h>

 const int N=;

 int pos[N][N],p[N];

 char str[N],s[N];

 int main()

 {

     int n,m;

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

     {

         if (n==&&m==)

             break;

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

         {

             scanf("%d%*c",&p[i]);

             p[i]--;

         }

         gets(s);

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

         {

             int j = p[i];

             int cnt = ;

             pos[i][cnt++] = i;

             while(j!=i)//找第i个字符的循环节

             {

                 pos[i][cnt++] = j;//表示第i个字符在变换cnt次后所在的位置

                 j = p[j];

             }

             int t = m%cnt;//第i个字符变换的次数

             str[pos[i][t]] = s[i];//将该字符存入其在目标串中的位置上

         }

         str[n] = '\0';

         puts(str);

     }

     return ;

 }

巴特西

Decode the Strings

最新文章

热门文章