寒(tui)假(fei)大(de)汇(zong)总(jie)

Recursion posted @ 2015年3月02日 21:10 in 杂文 with tags usaco 总结 JSOI POI bzoj uoj , 1258 阅读

今天都开学了...我还沉浸在寒假刷(tui)题(fei)的快感中真是没救了...还是来总结一下好了...省选round1考得实在是太逗比，本来不想单独写游记的，现在丢到这里面来好了...

值得记录的题：

poi18-20上学期没刷的部分题（见前面的题解），大部分poi的题都挺不错的，主要是算法思维巧妙，非常适合我这种脑洞不够大，智商非常低的人...

感觉其中最好的题应该是神构造题poi18 periodicity，证明过程非常复杂但是都很巧妙，而代码写起来很简洁优美。

poi20 polarization，非常有趣的题，算法非常有区分度，开始的结论虽然挺神但是不sxbk，也很好证明。然后综合运用了树的重心，背包dp等进行优化，最后按照根号分类虽然是经典技巧但用在这里也挺有趣，唯一的坑点是250000的范围很难让人想到最后是[tex]O(n \sqrt n)[/tex]的算法...

poi20 price list 坑爹结论题，无向图中三元环的数量是[tex]O(m \sqrt m)[/tex]的...不过还是优美的结论。

poi18 tree rotations 裸题，发现线段树合并确实比平衡树的启发式合并有用很多。虽然空间是[tex]O(n \log n)[/tex]容易被卡，但是时间复杂度少一个log，代码也非常好写。

poi19 a horrible poem 经典题，但是算法非常优美，再加上不卡hash写起来简直爽...质因数个数是log级别的确是是挺好的结论。

bzoj3884 （没抢到bzoj上一血好悲伤）算法很简单，就是迭代球phi，但是今天突然发现我们并没有证明为什么迭代次幂迭代到一定次数以后mod值就是定值了呢...至今为未想出证明...球解释...

bzoj3864 clj冬令营讲的题。把另一个dp的结果利用差分后不超过1的结论压缩在状态里确实是挺神的想法。

bzoj2035 前面写过题解了，把看起来很像是dp的题转化成图论模型很巧妙啊，很有poi题的感觉。

bzoj2029 我会说喜欢这道题的一部分原因是题目背景很文艺么>_<...贪心的方法想出来很好证明，但想要自己想出来有点难度。现在想想那些十几年前的题虽然没有今天很复杂的算法或数据结构，但思维性都很好啊...~~看看现在bzoj都进化成数据结构oj了...~~

bzoj2173 如果这题不是可以直接找规律递推球解的话这题就是神题了啊...正解用生成函数真是个强大的东西。

然后是寒假打的比赛：

UOJ GoodbyeJiawu：

感觉整场比赛都在犯逗，t1sb题竟然想了十几分钟，t2我貌似没考虑某种情况最后过了什么鬼。然后看了t3...这尼玛不就是三国杀的杀闪南蛮决斗么...你在逗我么...然后想了一会感觉细节好多的样子就弃疗了。然后看了t4，非传统题挺好玩的，发现70分不是随便打打表就过了么...果断写了...正准备交才发现是要交cpp而不是直接交QAQ代码...但我已经把生成器删了...无奈写了个程序给每行加了个printf...然后看了一下t5，发现竟然是提交答案题！而且还是魔塔...简直比卡坦岛传奇还sxbk...于是写了个手玩的程序...玩啊玩，最后就玩出24分真是醉了...果然我人类智慧太弱了...不过竟然是这题最高分...后来发现其实每个点还是有各自的特点的，但是比赛就5个小时各种状压dp，各种斯坦纳树能写完？最后t3随便写了个暴力拿了20分。

然后rank19滚粗。billxu2000怒虐全场rank4不能更神。~~人生第一次踩了waltz真是不容易~~>_<（大雾）大概waltz省选round1跪了在放水攒rp...

USACO Feb月赛：

大概是前两场太水了这场美国人来虐我们了...

开了t1发现就不会捉，跟bx2k一起想了一会发现[tex]O(n^3)[/tex]还是挺好写的，然后竟然过了13个点...玩了一会儿常数实在优化不出来就弃疗了。

这时已经1.5h过去了，赶快看了下t2t3发现t2好像是傻×AC自动机，t3竟然是计算几何+数据结构果断放弃。t2写了1h终于写完了太弱了T_T然后有6个点T了，感觉应该是边界没处理好死循环了，拼命查错怎么也搞不出来T_T然后赶紧写了个t3暴力就结束了。竟然有5个点好高兴...后来才知道shanquan2倒着暴力6个点，waltz在凸包上暴力7个点...真是醉了T_T

最后是大吐槽，JSOI round1滚粗记：

一上午在车上跟bx2k，youyl等人扯了半天泉岭精神，ra2，脑洞题，蓄镗波等等。bx2k讲了pear的烧桥计划感觉挺有趣的，这是脑洞到了一定境界了么...dyc还在车上问我树的同构判定，我胡扯了一通然后表示这种脑洞这么大的东西江苏怎么可能考（考试后，你懂的...）。bx2k好像不在听我就不扯了，然后他考试后表示很不爽...

wjh在车上表示，他这次绝对不会爆零。

中午到了~~沈洋中~~省扬中，shanquan2也来了，不愧是五门省队，气场强大，我们轮流跟他打biu果断被虐翻了...在食堂吃饭，面条简直感(sang)人(bing)，最后我竟然吃完了真是不敢相信，显然是被shanquan2影响的...食堂里面看到了waltz，果断Orz...

到了机房，感觉还不错，比去年的环境看起来舒服...再加上我今年是用c++所以不用在fpc那种坑爹的环境里写程序了...试机随便打了个kmp...本来想打manacher的没写（职业写错模板）...

看了下题目，坑爹的排版看起来真不爽...发现t1是sb树形dp果断写了，居然写了1h太弱了...然后看了下t2，感觉manacher可以搞，但想到还有坑爹的旋转和斜着的对称果断放弃了（我会说我这题30分暴力写了0.5h？）。然后看了下t3，简化树的同构，感(yi)觉(kou)非(xue)常(pen)的(chu)爽(lai)，这不是暴力找出重心然后hash就行了么，但是代码量对我这种傻×来说有点小大啊，不管了，还有3h不信我写不出来...但是这跟简化树有毛关系啊...然后想了个逗比贪心发现显然有反例就不管了（考试后，你懂的）。然后开始写，写了2h终于写完了...感觉小数据能过就不管了...然后突然发现t1递归好像会爆栈+爆空间(我用的priority_queue)，想想保险一点就改成了bfs序递推。然后就结束了...

讨论了一下他们说t1有三种情况心里有点虚...后来想想发现好像就是一种情况啊...貌似没错...

晚上领奖各种欢乐，bx2k领普及组的奖，wjh领提高组的奖，~~我很想吐槽明明该换一下→_→~~

去机房，看成绩发现囧了，100+40+0=140，t1A了很正常，t2居然多了10分有点爽，t3爆零了，我去...

然后发现t3我逗比了，每一层hash时应该mod不同的质数，我mod是相同的，于是直接滚粗...

然后我才知道原来t2被暴力各种艹？...各种奇怪的优化+卡常数直接70+分...

然后更无语的是t3我前面想的那种贪心可以直接A，我真是被出题人深深地感动了...果然是紧跟noi步伐...出题人你在干啥啊...