浅谈Bestcoder Round #41
停课申请.tex

Happy Ending

__Shi posted @ Wed, 22 Jul 2015 10:52:16 +0800 in Life with tags NOI2015 , 408 readers
NOI还是过去了,还是不错的。
 
Day1的前两题就不说什么了。。。反正都是废题。。。第三题似乎在前几天的51nod“算法马拉松”中有类似的出现。遗憾的是,原题要求的是一个最小值的问题,当时直接用贪心水过了。这次成了计数题,贪心自然就不可行了。比较神奇的是,在考试的时候,我筛了一波素数,然后统计了$\sqrt{500}$以内的素数个数。记得数出了20多个,也没有怀疑,然后就不会做了。其实int(sqrt(500))也就22。。。直到现在,我还不知道当时是什么情况。
 
Day1 20多人300+,还有一波人255+,可是我只有250。。。
 
Day2的第一题显然是像建哈夫曼树那样贪心地并起来就可以了。K叉哈夫曼树和二叉哈夫曼树的区别,也就是可能在最后一组,不是完整的K个子树并到一个根上。观察小样例,就可以发现如果最后一组合并时,不是完整的K个,需要在第一次合并的时候就把多余的并起来。这些多余的当然是取最小的几个。于是我就取了$w_i$的开头的若干个,再用priority_queue建树。过了大样例太自信,没对拍(也是唯一没有对拍的题)。复评的时候看到后面的点都WA了。之后意识到没有sort。。。过的那些点是$w_i$相等,$K=2$,直接并没有多余的之类的暴力点。
 
Day1和Day2的考前一天都分别码了一遍Suffix Array,恰好第二题就是SA的经典题,很顺利地码完拍过。
 
第三题的前两问,忽略离散的复杂度,可以$O(n)$dp。第三问看上去要网络流,建图似乎不太方便。想着没有时间建网络流的图了,就在dp的基础上建了一个dp值转移的图,然后贪心分配压路机。不过建图是错的。其实$y_i$相同的树不多,建图的时候可以复杂度高一些的。没时间了。。。没过样例就交了。。。最后第三问只对了三个点。 
 
Day2只有219。。。估计大众水平240+。。。
 
不过最后还是卡着au线20来分进队了。。。Happy ending。。。
 
blog comments powered by Disqus