首页 > 代码库 > acm数学(待续)

acm数学(待续)

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

1.置换,置换的运算

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

 1 #include <cstdio> 2 const int maxn = 1005; 3 int gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);} 4 int lcm(int a,int b){return a / gcd(a, b) * b;} 5  6 int a[maxn]; 7  8 int main() 9 {10     int n;11     scanf("%d", &n);12     for(int i = 1; i <= n; i++)13     {14         scanf("%d", &a[i]);15     }16     int ans = 1;17     for(int i = 1; i <= n; i++)18     {19         int temp = a[i], len = 1;20         while(temp != i)21         {22             len++;23             temp = a[temp];24         }25         ans = lcm(ans, len);26     }27     printf("%d\n", ans);28 29     return 0;30 }

 

poj 1026 Cipher

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

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

 1 #include <cstdio> 2 #include <cstring> 3 const int maxn = 200 + 5; 4 int gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);} 5 int lcm(int a,int b){return a / gcd(a, b) * b;} 6  7 int n,k,x; 8 int a[maxn], round[maxn]; 9 char s[maxn], ss[maxn];10 int main()11 {12     while(~scanf("%d", &n) && n)13     {14         for(int i = 1; i <= n; i++)15             scanf("%d", &a[i]);16         //找寻环节并记录。17         for(int i = 1; i <= n; i++)18         {19             int temp = i, len = 0;20             do21             {22                 temp = a[temp];23                 len++;24             }while(temp != i);25             round[i] = len;26         }27 28 29         while(~scanf("%d", &k) && k)30         {31             getchar();32             gets(s+1);33             int slen = strlen(s+1);34 35             while(slen <= n)36             {37                 s[++slen] =  ;38             }39             s[n+1] = \0;40             strcpy(ss+1, s+1);41             for(int i = 1; i <= n; i++)42             {43                 int t = round[i] - k % round[i];44                 int temp = i;45                 while(t--)46                 {47                     temp = a[temp];48                 }49                 ss[i] = s[temp];50             }51             printf("%s\n", ss + 1);52         }53         puts("");54     }55     return 0;56 }

 

acm数学(待续)