together: Find's Blog

尽管Pólya是一个很偏的东西, 但还是花了两三天的时间大概的学了一下, 搞了两道sgu上的题. 因为没有系统的学, 所以很多东西还是了解的不透彻.

sgu282 Isomorphism
一道用来实践Pólya原理的好题. 给一个有n个结点的完全图, 求用m种颜色染色的不同方案, 重新排列点的序号后重合的方案算一种.

这道题可以很容易看出需要用Pólya原理, 但是不同的置换方案超过52!(每一种点的置换方案唯一的对应一种边的置换方案). 于是我们需要将点置换分类别, 将置换按循环节长度排序, 如(1)(234)(5678)就是一种”格式”为 1-3-4 置换方案, 如果一种置换表示为 s1-s2-s3-…-sk, 显然 s1+s2+s3+…+sk=n. 于是这是n的一个划分. 通过搜索我们知道53的划分并不多. 当有了一个特定的置换”格式”, 我们可以很容易的用组合数学知识算出有多少种对应的点置换, 对于”格式” s1-s2-s3-…-sk, 有 n!/(s1!*s2!*s3!*…*sk!)/(t1*t2*…*tr) * (s1-1)!*(s2-1)!*(s3-1)!*…*(sk-1)! = n!/(s1*s2*s3*…*sk)/(t1*t2*…*tr) 种, 其中t1, t2, …, tr是相邻重复的sk的个数, 如 1-3-3-4-5-5-5-6 就有 t=(1,2,1,3,1). 由于对Pólya原理的理解不对, 我到这儿以为只要将点置换的个数及循环节数套进公式就可以了, 但这是错的, 回想Pólya原理的证明, 它的证明是建立在Burnside定理基础上的, Burnside定理中对象是不同的染色方案, 染色方案是针对边的, 所以在Pólya原理中置换群中的对象也必须是边 (而不是点).

Read the rest of this article »

这是我在准备noi2009时在online judge上的做的部分题目. 从wordpress的修订版本记录来看, 主要记的应该是2008年9月至2009年5月做的题目, 每题都附有简短的算法描述. 另外, usaco曾写过第三章之后几乎全部题解, 但因为Rob认为题解对使用usaco的练习者有害, 所以后来全部删除. 这里曾作为blog的一个页面存在, 现在在online judge上做题没有以前那样的耐心写感受, 即使某天忽然想写专门的题解了, 那也一定是值得我写一篇单独blogpost的收获, 所以这个页面只是留下来做纪念, 不再更新, 发布时间仍保留在2008年.
btw, 我知道自己好没有恒心与毅力, 大家就不用留言鄙视我的题量了.

Read the rest of this article »

我被SGU整疯了, 真的.. 同样的程序, 交一遍, runtime error on test 5; 第二遍, runtime error on test 7, 再交, Accept, 再交, runtime error on test 10… 俄罗斯人耍我..

哪位给个俄罗斯的代理? 打开SGU的时间我都可以吃一顿饭了. 或者, 哪位做SGU的同学告诉我有没有什么别的办法提高访问SGU的速度( ps. 让中国电信兼并俄罗斯电信这类无厘头的方法就不用说了 ) 无比怀念透明的USACO.

冬令营的题目, 一直放在硬盘里. 打开, 关掉, 就是不大会做, 总想翻解题报告. 恶习..

下了6个G左右的柯南, 够我看一阵了. 呃~ 我知道那是日本人的东西, 但毕竟, 我总不能去看蓝猫淘气三千问吧? 或者葫芦娃?