首页 > 代码库 > 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数学(待续)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。