ZOJ 2139 ACM

February 28, 2014 at 11:18 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1139 离完成410题之后有一段时间了,前几天又被工作折腾,这两天终于有空练一两道题目,哎,工作真是辛苦,还有毕设要担忧,算了不扯淡了。本来是打算刷1235这四个数的排列中简单的题目的,结果瞄到2139这个题目霸气的标题,于是毅然决然要把它A了(好吧实际上是因为题目描述很短)。 题目的大意是说,有一个机器编号为n,如果你知道第k张卡片的密码,你就能算出编号为f(k)=k/2+(k%2)*2^(n-1)的卡片的密码,那么对于0到2^n-1这样2^n个数,至少要知道几张卡片的密码才能知道所有卡片的密码。 简单的算几个例子就可以发现不可能一张卡片得出所有卡片的密码,公式会循环,比如对于n=2时,f(0) = 0, f(1) = 2, f(2) = 1, f(3) = 3 知道编号为0的卡片,无论计算多少次公式,也永远也只能得到编号为0的卡片的密码,而知道卡片1,也只能得到卡片1,2的密码,知道卡片3,只能得到卡片3的密码。显然公式f(k)把卡片分成了若干个等价类,而目的就是求这个等价类的数目。其实想到这里,就应该知道是置换群相关的知识,应该使用Pólya定理。我对定理的理解太肤浅,所以找规律找了很久。。。实际上,公式里都是2,所以这么2的题目应该也要考虑2进制。只要想到了2进制就不难发现,如果k为偶数,那么就是右移一位,如果是奇数,那么就是右移一位,然后最高位补一,如对于n=4: 8 = 1000(2) = […]