Seventh Mist

GDKOI2016

Day 1

扫了一眼今天的题, 发现第一题还是比较simpIe的, 拆位维护一下就好了.

之后看了看第二题, 发现是个概率题, 然后一开始怎么推式子得到的答案都非常奇怪, 后来发现自己设状态的时候, 没有把两个本质不同的状态分离开. 然后我就猜测它肯定是存在一种决策顺序的, 推了一下发现确实可以按照某个东西排序, 然后直接DP.

之后看了看后两题, 发现都非常可做: 第三题是分数规划+网络流; 第四题是插头DP. 然后我决定还是先做第三题, 但是做的时候也没有细想, 就直接用Tarjan缩环, 然后分数规划再跑最大权闭合图, 但由于我印象中网络流不能处理实数, 因此我就把它放大10810^8再做, 但是在打的过程中犯了许多错误, 包括但不限于

  1. 最大权闭合图的权值设错;
  2. 最优化方向反了;
  3. 判无解判错.

然后就一直拍一拍, 改一改, 拍一拍, 改一改, 这样反复了许多遍, 最后在还剩下20分钟的时候, 我解决了除判无解以外的所有问题. 这时我考虑到无解最多只有10分, 就果断不判无解了.

然后去检查前面的题, 我记得我当时发现了几个很simpIe但是会导致我爆0的错误, 感觉好险……

不过最后还是有惊无险地拿到了100 + 100 + 90.

Day 2

由于感觉第一天考得太惊险, 因此决定第二天还是打稳一点……

看题的时候发现今天的四个题好像要难很多, 没有昨天的那么simpIe了.

第一题想的时候感觉博弈双方不是对立的, 然后困惑了一下, 问了问出题人, 出题人又说没有问题. 然后我就先去做第二题了. 第二题是很simpIe的数位DP, 暴力设一设状态, 就可以做出来了. 然后再想一想才搞明白第一题的意思, 就打了第一题. 之后就一直拍前两题.

之后我感觉还是第三题好做一点, 就去想第三题. 然后脑洞一开, 想到了一个很simpIe的做法, 然后我也不知道对不对, 就先打了个暴力验证的程序, 然后拍过了, 就果断去改成正解.

还剩半小时的时候我去检查各题的程序, 发现第三题会爆栈……赶紧改了过来, 然后又拍了一遍, 感觉还是比较险的……

最后拿到了100 + 100 + 100 + 20, 暴力分比昨天拿得多了一点……

总结

  1. 做比赛还是要稳一点的好;
  2. 不要慌;
  3. 以后要尽力多拿点暴力分, 不过一定要建立在保证前面的题的正确性的基础上.