almost 3 years ago
前言

又是一年的NOIP,又是一次联赛总结。(依旧滚粗(-__-)b
(这个总结是只测了山寨数据后的总结。)

概述

对于Day1,前两题很快可以切掉,斗地主那道题稍微麻烦一点搞了一个多小时。
对于Day2,比Day1的题目难了一个档次,时间的分配也有点紧张。

Day1

考前先常规地调试一下机子能不能编译运行,然后上个厕所回来考试开始。
首先看了一遍题目,感觉题目难度大概是T1<T2<T3,就按这个顺序做了。
T1填幻方,它还告诉你了怎么做,直接模拟,测了一下特殊的n=1和最大的n=39以及样例,过了直接去做T2。貌似刚刚到8:30
T2也是一道裸题,只存在简单环的有向图找最小环,直接Dfs或者Tarjan都可以(中间还写挂了一次囧)。我写了这两个做对拍。差不多到了9:10。写到这里的时候心情还是比较轻松的。
T3斗地主(看到题面之后心里是万匹草泥马共同飞奔而过啊&#&@%&),貌似足足把题目看了5-6遍才把细节搞清楚。起初是有一个Dfs+优化搜索顺序+最优化剪枝的思想,大概就是因为出牌方式之间互不干扰,所以先枚举出牌张数多的出牌方式,然后如果当前步数大于全局最优答案那么return。写了差不多一个小时(写得脑袋晕( ╯□╰ )),调对了小样例之后大样例也一遍过了,然后想了想手出了一组极限数据发现要跑3-4s,整个人都不好了。。。继续优化,因为发现有很多重复状态,因此对状态存一个五进制数,范围是(我竟然没想到可以只用,真是驴啊),作死用了map<longlong> ,其实也并不慢,然后发现极限数据可以秒出,结果答案错了囧,然后又是一波调试,过了所有样例和极限数据之后,差不多是11:40,正式宣告弃疗。
以上就是Day1了,感觉还行,除了T3没有很大把握能AC

Day2

依旧常规调试机器。
依旧常规先看一遍题目,然后感觉有点不对劲,这个难度和Day1不是一个等级的。
首先是T1,刚开始想是堆贪心,然后上了个set然后发现怎么调试样例都过不去,然后也没想法,就先去做T2了。现在是9:00
T2很明显的一个字符串Dp,根绝数据范围估计是个Dp。刚开始想的时候,少考虑一个情况,过不了大样例,然后看了下时间已经又过去了30分钟(开始有点慌了( ╯□╰ ),一个半小时没拿分囧),喝了口水,上个厕所之后突然想到了少考虑的一种情况,加上去之后过了所有样例。
在写完T2之后同时想到了T1可以二分答案后贪心,5分钟写了之后,和暴力对拍暂时没出错,就开始想T3
刚开始没一点想法,想了想了想了想,大概想出了可以用基于树上路径合并的LCA做法,结果三分钟研究路径并之后果断弃疗,细节想不清(我蛤了个蛤)。这个时候习惯性检查一下T1的对拍是否出错,发现挂了,然后发现又是少考虑了一种情况(我真是蛤了个蛤),改了之后重新思考了一遍题目,没有漏洞之后继续想T3。然后发现不开始写的话估计要写不完了,反正觉得不管怎么做都要LCA,就先写了一个在线LCA。写着写着感觉可以二分答案,然后还是要路径并,此时的路径并我们可以用的时间来求出,用了一个树上打标记的方法,给询问的都打上标记,再给打上标记。一条父边如果在路径并上,那么子树的标记和应该等于询问数。按着这个想法,花了分钟写完了,过了样例后和之前写完的暴力对拍没出错,此时已经11:45了,想改也没时间了,正式弃疗。
Day2感觉考得惨不忍睹,T3山寨数据竟然在一条链的数据上全挂了(虽然暂时并没有发现错在哪里),一切等正式成绩出来吧。(感觉要AFO,只能期待数据水的本质)

计划与安排

NOIP之后,目标就成了WC,好像还要写一本书啥的。
先是做题计划,首先先把历年NOI的题目做一遍(目前正在搞09年的),然后开始是各大省选和WC的题目,每道题都要有题解。
然后是看论文,先把今年的集训队论文搞定,然后如果有时间的话再从之前的集训队论文中挑一些出来看,一次是三篇左右,每一篇论文看过之后都要有总结。
至于写书就真是蛤了个蛤,数学和计算几何到时候看着办吧,感觉不是一件容易搞定的事。。虽然我也想毒害下一代。。

差不多就是以上了,总之加油吧。

update


真的AFO了哇

← 替罪羊树:bzoj3065 NOI2009 AC达成 →
 
comments powered by Disqus