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) = […]

ZOJ 3365 Integer Numbers

January 21, 2014 at 8:24 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3365 今天由于外力因素,没法干其它的事,于是在ZOJ上又水了水,算上这题,终于是AC400题了。回头想想,这个目标应该是在去年,还是前年就应该达成的,时间过得真快,不知不觉又被我水过去了两年么,果然已是拖延症晚期。 题目的大意是说小男孩写了一个连续的整数序列(n <= 50000),然后被腹黑的小女孩修改了一些数字,使得序列不再连续了。小男孩很伤心,希望你在修改尽量少的数字的前提下恢复序列的连续性,要求输出被修改的数字的个数和最终的序列,任何可行解都可接受,是个special judge。 考虑元素array[i],如果保持它不变,那么array[0]必须等于或者修改为array[i] - i,这是确定的,即所有元素都有保持它不变所需要的一个初值。拥有共同初值的元素构成一个等价类。元素最多的那个等价类中的所有元素就是需要保持不变的元素。使用O(n)的时间计算出所有元素的初值,问题就转化为求众数了。 一开始想用hash,后来想想C++没有hash,所以就有map求了一下,220 ms AC.后来发现ZOJ已经支持C++11,托STL设计者的福,仅修改了几行代码就有了unordered_map版本,150ms AC.但作为一个平均复杂度O(n)的算法来说,unordered_map在这个数据量上的表现并不理想。   #include <cstdio> #include <unordered_map> using namespace […]

ZOJ 3710 Friends

January 20, 2014 at 10:02 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3710 已经很久没有在ZOJ上刷题了,这算是回来刷的第一题,算是一个新的开始。 题目的大意是说有n(<=100)个人,他们之间的某些人互为朋友,这是初始条件。然后如果两个人有共同的k个及以上的朋友,他们就会变成朋友。要求的是通过这种方式形成的新朋友的对数。 最简单的方法莫过于模拟整个过程,把符合条件的人设为朋友,然后更新相应的状态。这里遍历所有的人是O(n^2)的,判断符合条件是O(n)的,然后外层加一个while(changed){}的循环。但这样复杂度就比较难以分析[分析不出来,sigh],就最坏的情况来看,如果每次只有一对新人符合条件,最后又是所有人都成为朋友,那么这个while循环就是O(n^2)的,所以整个算法是O(n^5)的。这个最坏的情况是否能达到,暂时分析不出来了。 这时候我是这样的两个思路: 1.把模拟的代码码出来,提交看是否AC,过了万事大吉。 2.想一个复杂度更小一点的算法。 我想着出题者一定不会只给这么一个模拟的复杂度都看不到的算法出来,而且说不定会把直接模拟的给卡死,所以直接跳过了第一步[事实证明是我想太多了,直接模拟是可以AC的] 幸好这道题也算有一个我比较满意的,以我的智商也能快速想到的O(n^3)的算法。当两个人有共同的k个及以上的朋友时,他们会变成朋友,并且它们变成朋友影响到的关系是O(n)的。比如A和B变成了朋友,那么唯一影响到的是所有A的朋友和B多了一个共同朋友A,所有B的朋友和A多了一个共同朋友B。所以只要维护一个记录两人共同朋友个数的数组common[][],初始化时把>=k的两个人存入队列(或者堆栈)中,每次从中取出两人,O(n)地更新,并把其中大于等于k的两个人存入队列中,重复上述操作直至队列为空。由于关系对最多O(n^2),所以队列里最多这么多个元素,而每次更新是O(n)的,是个O(n^3)的算法。 AC的时间是260ms,暂时还没有想到更好的算法,代码还可以做一些优化,但达不到目前最优的20ms,不知是如何实现的。 #include <cstdio> #include <cstring> #include <queue> using namespace std; int […]