CTSC2014 & APIO2014酱油记
CTSC2014 DAY 1, April 28
CTSC一试。
拿到T1，感觉“这不是我几天前刚在《数学之美》里看到过的相似哈希？”然后开心地敲了1h，手写Complex什么都搞好了，最后发现相似关系不满足传递性囧……整个人都赛高了。先敲了O(N^2L)。
然后看T2。感觉可能需要预处理出每棵“广义的”子树（也就是子树和子树的补集）的信息。不过根本就不知道需要什么信息啊囧……然后就输出样例，当然是没分的。
然后看T3。一开始感觉不知所云，等我发现可以用矩阵描述一次递推的时候，一下子变得可做起来了。然后写了三个subtask，也就是10pts的暴力，15pts的矩乘快速幂，20pts的矩阵BSGS。
最后T1写了个SA就没了。顺便说一下N＞5000写的是输出“I give up”。据说SA其实能过#5,#6……囧。
最后是40+0+45，第一题分比第三题少真是不能多说……
CTSC2014 DAY 2, April 30
CTSC二试。
发现旁边坐着策爷……太神了跪跪跪。
先看T1，好像K1是废条件。本来想要拿第一个点的暴枚check和第三个点的高斯消元，结果模拟似乎写错了？（或是读入萎了？）然后就爆零了。
发现T2似乎和MST有关？不过没有想下去。可惜如果从MST往下想，说不定就A掉了。
发现策爷在虐提答题，然后写完T2的10分就去看T3。发现似乎非常适合手标？写了个可爱的辅助小程序手玩了1K个。之后又给辅助小程序加入了自动识别功能，自动识别失败转手标，这样刷刷下来15K个。然后考完了，完了。
最后复测的时候发现T3我的out居然有60K个数，而不是一开始跑的15K个……太灵异了，我的成绩结果就多了20分……当然人太弱，多20分也救不了了，Ag滚粗。
APIO2014, May 3
APIO。
今年的APIO有点厉害啊，那个ZJOI，比APIO不知道高到哪里去了，我被它虐得谈笑风生……
开场50分钟就把裸题palindrome给1A掉了，后缀数据结构转来转去还是很愉悦的。
然后捉T3，一开始以为是DFS+构造，然后发现特例很多。搞了0.5h爆零。静态查错+构造反例又1h，搞出13pts，之后再也不能愉快地玩耍……
滚回去看T2。仔细想想是个区间dp。打印了一下决策发现是单调的，然后就dodp(lyr, l, r, Opt_l, Opt_r)水掉了。
最后专心攻T3。换了一种思路，先枚举开始点，然后树形dp。朴素的28分。
然后把状态放在边上，这样加上记忆化，是O(Σdeg^2)的，57分了。
感觉可以使用“第二次访问一个节点时处理出所有子树信息”来优化成O(N)，然后截止前15min写完，WA on Subtask 1，感觉是肺热，静查动查无果，最后就只有57分。
这样就只有100+100+57了。看到AK的cenbo，感觉自己多半是肺热。
最后全国只有4个AK爷？太灵异了……
Others：
经过这两次比赛，我已经成为了jcvb和vfleaking的脑残粉。太强了跪跪跪。
评论 (0)
