Seventh Mist

GDOI2016 赛前集训

赛前最后两轮集训的总结就放这里啦QWQ

Round 1

Day 1

先看了一遍题……

第一印象感觉T1瞎搞搞就可以了, T2应该是数位DP然后强上矩阵快速幂, 然后后两题不大可做, 而T4比T3更加不可做.

于是决定按顺序做好了……

T1没怎么想, 直接打了个O(nn)O(n \sqrt n)的做法, 然后测了一发极限, 过了, 就写了个拍放在那里拍了.

T2先打了个没有矩阵的版本, 再把矩阵套上去, 然后先出了几个数据, 发现两者的答案是一样的, 再想了点办法检验正确性, 就没怎么管了.

T3感觉非常像BJOI2016的那个k近点对的题, 然而当时那题大家都是乱搞过的…… 然后我想起当时有一种乱搞的做法是分治, 就打了个分治, 然后把暴力加进去分段.

T4反正不会做, 随便骗骗分好了……

最后得分: 100 + 100 + 45 + 10, 感觉还是和预测比较一致的……

但我后来发现T3(分组测试)我是每一组数据T了一个点……无话可说了……

Day 2

T1看了一眼感觉是传递闭包+网络流, 然而本地机子太慢, n=500n = 500的传递闭包都要1秒……感觉没啥优化空间. 于是我感觉网络流是60分做法, 100分做法一时半会想不出, 就先没码这个题.

T2是一个字符串题, 然后我发现这题没啥部分分, 就想起来劼司机的一句话: “部分分那么少的肯定是sb题”. 然而我想了一会没想出来, 就决定先去看后面的题.

看了看T3的部分分, 然后想“T3部分分那么多肯定是神题”, 之后就打了个暴力放在那里,决定弃疗这个题.

T4感觉不大可做, 于是就先打了暴力.

当我码完后两题暴力之后大概只剩下2h了. 然后我坚定了一下信心, 决定硬刚T2……

然而剩1.5h的时候我还是没想出来, 就决定先去码T1, 码完之后大概只剩下1h了, 然而我还是三题暴力状态, 顿时感觉今天要狗带了……

然后T2我就尝试去找规律, 然而并没有什么收获.

在剩40min的时候我突然想出了T2的做法, 还好这个做法不太难打, 于是我就赶紧码了一个, 然后和暴力拍上了, 之后我感觉今天有救了……

最后得分: 100 + 80 + 50 + 30, T2由于C++中的一个坑错掉了(这个放到后面讲).

Day 3

看完T1发现: 这不就是k短路吗……然后没看其他题, 就迅速脑补了一个O(nlog2n)O(n \log^2 n)的做法, 码了一发. 结果这题码完, 拍完之后还剩下2h, 而且我发现我的做法不太能跑得过去……

之后赶紧去看后面的题哪个更好拿部分分.

T2看了一眼感觉是不可做的, 就打了暴力.

T4是大原题(三维计算几何), 感觉也是不大可做的, 而且暴力也不太会, 那就puts(0)骗分咯……

T3题面比较冗长, 所以我是最后看T3的, 然后发现这是个很裸的最小割的题……当时只剩下1h了, 只能用最暴力的方法把算法实现出来, 之后再想怎么优化……

把网络流那一部分实现出来之后, 拍了一下发现过掉了. 然后把求LCP的变成了O(logn)O(\log n). 测了一下极限发现不大跑得过去, 当时感觉今天又是两题被卡常了,然后又要狗带了……

最后得分: 70 + 40 + 95 + 10.

T1由于自己太虚……用了双hash, 如果胆大一点, 用个单hash, 就A掉了……

不过这也是稳定60分与期望100分之间的博弈……感觉还是挺难抉择的.

比较诧异的是T3居然有95分……ISAP大法好!

Round 2

Day 1

看了看前三题, 发现是SDOI Day 1的题……还是比较简单的……大概2h就码完了……

最后一题是CF原题……但当时并没有去看题解QAQ, 只记得大概是把点缩起来, 然后顺着这个思路拿了50分, 最后就350了……

Day 2

第二天果然是SDOI Day 2的题……大概3h才搞完前三题……第三题花了比较久的时间在调试上.

打完之后感觉比较累, 然后最后一题看题没看仔细, 以为有多个通配符, 然后感觉要用到高深的自动机理论, 基本不可做, 再加上自己想把比赛打稳一点, 就弃疗去检查前面的题了.

最后拿了300分.

Day 3

今天是ExfJoe的三个题加上绍一的一个题. 后三题之前见过就没管了, 然后第一题拆了一下式子发现是个贪心, 然后预处理可以分治+FFT, 就码了一个, 卡了卡常数发现没啥问题, 测了几个数据也没啥问题, 就没管了.

最后拿了第一题的100分……居然能第二……

左移位数超过字长是未定义行为! 例如1 << 32.

总结

心态要平和. 如果不会做, 就要找准时机先打暴力, 而且要把暴力打满……

在考场上不要弃疗.

总之省选这种比赛, 打稳一点比较好.