acm数学(待续)

时间:2022-10-03 18:07:03

意图写出http://www.cnblogs.com/kuangbin/archive/2012/08/28/2661066.html这个东西的完善版。

1.置换,置换的运算

poj 2369 Permutations置换群中有一个定理:设T为一置换,e为单位置换,T^k=e,那么k的最小正整数解是T的拆分的所有循环长度的最小公倍数。

 #include <cstdio>
 ;
  ? a : gcd(b, a % b);}
 int lcm(int a,int b){return a / gcd(a, b) * b;}

 int a[maxn];

 int main()
 {
     int n;
     scanf("%d", &n);
     ; i <= n; i++)
     {
         scanf("%d", &a[i]);
     }
     ;
     ; i <= n; i++)
     {
         ;
         while(temp != i)
         {
             len++;
             temp = a[temp];
         }
         ans = lcm(ans, len);
     }
     printf("%d\n", ans);

     ;
 }

poj 1026 Cipher

PE真的巨坑,每个blocks结束之后要加一个换行,样例输出是有问题的。

注意一下,这个地方,和上一道比较,是一个倒过来的,倒过来的能明白吗。

 #include <cstdio>
 #include <cstring>
  + ;
  ? a : gcd(b, a % b);}
 int lcm(int a,int b){return a / gcd(a, b) * b;}

 int n,k,x;
 int a[maxn], round[maxn];
 char s[maxn], ss[maxn];
 int main()
 {
     while(~scanf("%d", &n) && n)
     {
         ; i <= n; i++)
             scanf("%d", &a[i]);
         //找寻环节并记录。
         ; i <= n; i++)
         {
             ;
             do
             {
                 temp = a[temp];
                 len++;
             }while(temp != i);
             round[i] = len;
         }

         while(~scanf("%d", &k) && k)
         {
             getchar();
             gets(s+);
             );

             while(slen <= n)
             {
                 s[++slen] = ' ';
             }
             s[n+] = '\0';
             strcpy(ss+, s+);
             ; i <= n; i++)
             {
                 int t = round[i] - k % round[i];
                 int temp = i;
                 while(t--)
                 {
                     temp = a[temp];
                 }
                 ss[i] = s[temp];
             }
             printf();
         }
         puts("");
     }
     ;
 }