台湾菜

置换群及Pólya定理专题

twcai • acm/icpc

pku2369:概念题,理解置换群的合成运算即可

3878349 clumsydragon 2369 Accepted 212K 16MS C++ 579B

pku1026:置换群的幂运算

3879155 clumsydragon 1026 Accepted 208K 63MS C++ 825B

pku1721:像置换群的开方运算,但其实不用开方运算

4321228 clumsydragon 1721 Accepted 216K 16MS C++ 883B

pku3270:求最小花费(简单) 算法黑数上有讲,比较详细

4378625 clumsydragon 3270 Accepted 528K 47MS G++ 1266B

pku2409:关于环的polya,公式见下

首先是环长度为奇数的形式,一共有两种共 2 * s 个置换,分别是旋转和反射各 s 个置换,旋转的置换群除了最原始的{1,2,3,...,s} 循环个数为 s,其他循环个数模拟置换过程求得。反射的置换群有 s个,每个置换群都有 s/2 + 1个循环,包含了 s / 2 对以及处于对称轴上的那个点。

然后是环长度为偶数的实行,一共有三种,除了旋转和反射,还有“对折”(姑且这样称呼吧-_-|),旋转没有区别,反射有 s / 2 种置换,循环个数为 s/2 + 1个,"对折"也有 s/2 中置换,循环个数为 s/2 个。

推出了每种情况的循环节个数,这题就好做了,只要代入ploya公式就可以了。

4379482 clumsydragon 2409 Accepted 400K 0MS G++ 1128B

pku1286:2409简化版,注意数据范围就好了

4379536 clumsydragon 1286 Accepted 400K 0MS G++ 1139B

pku1879:这道题,minute truck, five minute truck, hour truck 都可用栈模拟,模拟一天后小球的序列:s1, s2, s3………接下来的做法基本和2369一样,需要注意的是,代表第12个小时的小球是跟在它前面的11个小球后面进入queue的,因为没有注意这点,花 费了很多时间调试

3887339 clumsydragon 1879 Accepted 208K 16MS C++ 1283B

hdoj1537:置换(算置换比较麻烦)

hdoj 1812:Ploya定理

这题刚开始用枚举所有8种置换群,找出循环个数再使用Ploya公式的方法要TLE。不过还好每种置换群的循环个数都是有规律的,可以推出 N 分别为偶数和奇数时的公式。比较麻烦的是还要用到大数,我直接用java还是跑了将近两秒……这题时间卡得有些苛刻。

897436 2008-11-15 15:25:47 Accepted 1812 1812MS 2880K 852 B Java
comments powered by Disqus