CSP挂分记

· · 生活·游记

上午普及组，前两道题差不多 30 分钟就切掉了，但是第三题就卡住了，刚开始想弄枚举或贪心，发现写不出来，于是考虑动态规划。差不多半个小时左右，就想出正解了。而且赛后看题解，似乎没有和我一样做法的，不过又交不了，所以说算了。第四题赛时想出来了 80 分做法，但是卡在值域上了，现在想来似乎可以用树状数组优化，不过也没用了。

所以说，普及组差不多就是 100+100+100+80=380，有点可惜，没有 AK，明年还要加油啊。

下午提高组，今年似乎没有送分题了，第一道就是一个类似于反悔贪心的东西，但是似乎比较简单，三个优先队列差不多就可以了，大概 40 分钟敲完。

第二道题很尴尬，我其实特别想喷我考试地点的机子，不知道是怎么做到这么慢的。第二道题原本是敲出来了 \cal O( 2^kn) 的做法，但是在本地测第三个大样例的时候，竟然跑了差不多 2 秒钟，瞬间就感觉不好了。然后就换思路。想的是把每个改造的代价分摊到路径上，然后再来统一调度。时间复杂度倒是对的，但是第四个样例又炸了，应该是写假了。所以说，不敢赌，于是按照时间复杂度，把两个都交上去了，运气好有 100，运气不好应该有 80，但是由于写了两个算法，而且第二个算法又很难实现，所以说写完第二题的时候，只剩 1 个小时了。

剩下一个小时，只能敲暴力了。第三题一看就有了思路，直接哈希暴解，整体时间复杂度差不多是平方级别的，结合几个 q=1 的特性，差不多应该有 20 分。

关键是我在敲哈希的时候，式子记不到了，还是先推的。关键是，我们那个考场，提前差不多 30 分钟收草稿纸，只能脑算，写完差不多只剩 15 分钟了。

然后就急忙看最后一道题，没有任何由于，直接打暴力 dfs，然后验证答案，差不多有 8 分的样子。

因此应该保底都有 100+80+20+8=208 的样子。

最后成绩出来了。普及组没有挂分，提高组倒是有点意外 100+80+40+8=228 第三题还多了 20 分。

PS：等代码发下来之后，来洛谷测第二题，结果发现第一次写的算法可以过，服，白丢 20 分。