首页 > 代码库 > 置换群与轮换

置换群与轮换

2024-07-20 14:30:21   224人阅读

昨晚BestCoder第一题：

 

一开始看了半天不知所云2333333

其实它是让求置换群的轮换

比如对于原题中的

有o(1)=2, o(2)=5, o(3)=4, o(4)=3, o(5)=1

其中o(1)=2,o(2)=5,o(5)=1就是一个轮换，转了一圈之后又回来了233

同理，o(3)=4, o(4)=3又是一个轮换。

所以输出答案为(1 2 5)(3 4)

---------------------------------------------------------------------------------

挺水的一个水题，结果不知道为什么我的代码总是TLE   T^T

终于知道为什么了T^T

while (~scanf(......))

注意加上那个～

因为OJ上读入结束之后scanf返回值是-1（即二进制11111111），加个～就可以让循环结束了

很隐蔽的bug......手测根本发现不了T^T

 

附代码

 1 #include "stdio.h" 2 int a[100010]; 3 int v[100010]; 4 int tx,ty,n,i; 5  6 int main() 7 { 8     while (~scanf("%d\n",&n)) 9     {10         for (i=1;i<=n;i++)11         {12             scanf("%d",&a[i]);13             v[i]=0;14         }15         for (i=1;i<=n;i++)16         {17             if (v[i]==0)18             {19                 printf("(%d",i);20                 v[i]=1;21                 tx=i;22                 ty=a[i];23                 while (v[ty]==0)24                 {25                     printf(" ");26                     v[ty]=1;27                     tx=ty;28                     ty=a[ty];29                     printf("%d",tx);30                 }31                 printf(")");32             }33         }34         printf("\n");35     }36     return 0;37 }
View Code

 

 

Orz

 

置换群与轮换


联系
我们