CSP 2019 游记

# CSP 2019 游记 可惜了啊.../kel ### D1 开题感觉就是个很sb的结论题，看到 $ n \leq 64 , k \leq 2^{64}-1 $ 估计就是卡卡ull的事，可能还会特判一下。 于是手玩了玩样例和自己的小数据就会了一个 $ O(n) $ 做法。 只是 做法会用到 `1<<n+2` 所以特判了 64 、 63 写的时候很注意，还造小数据测了测，确认没问题发现都开考 40分钟了。。。有点慌，于是开T2 T2看起来就很套路啊。。**写完**一个dp后发现貌似直接这么莽有问题（过不去大样例）。。心态又有点崩，然后想怎么改，结果发现自己只会一个线段树+二分的$ O(nlog^2n) $ 的~~优秀~~ 扣脚做法。。线段树上二分确实可以$ O(logn) $ 但是觉得有点麻烦。然后发现倍增貌似很好写就直接写了个 $ O(nlogn) $ 的东西。大概思路就是先倍增找到第一个位置使得前缀和小于当前位置，再对于当前的前缀和进行二分。 用了 `vector​` 维护，感觉这个三倍的常数过 $ 5\times 10^5 $ 已经有点慢了没敢用 `lower_bound` 就写了个二分（反正也没几行） 过了大样例感觉没问题就没管了。 **真正的勇士，敢于直面 D1T3** 开 D1T3 还有1.5h，时间还比较够打个暴力分。读完题会了10分。 然后 1.5h 后。。我还是只会10分。。。 最后五分钟还以为自己倍增写错了。。还好是最后慌了想错了。。 于是210 滚粗。。场上以为人均猜出菊花、链的结论没想到大众分210.。。。也是好事。 ### D2 这场 D2 我是真的凉啊。。。。 开场看 T1 ，这不是很组合数学嘛，想了快半小时无果。于是开始想dp，发现自己已经会了一个 $ O(n^3m) $ 的84分做法。就是考虑 `dp[i][j][k]` 表示前i个菜的所有子集，一共点了j个菜，其中k个是钦定的菜。 因为钦定的菜被点超过一半是一种合法状态，而且显然不会两个菜同时超过一般，所以不用容斥。 想了想怎么优化，不管了先写了再说。。~~反正16分用处不大~~（假的！ 写完发现才一个小时多一点嘛。。然后过不了 `n==3` 调试。。调试。。调试。。 时间一份一秒过去，不管怎么输出dp都没挂。。 11：00的时候，我还没看后两个题，，已经认为自己今年退役稳了。。。 最后发现统计答案挂了。 调出来的时候还有50分钟。。 然后开始看后面两个题。。 T3 暴力显然，重心直接找，然后链打算先写完T2暴力再来写。。也很显然啊 15分钟T3暴力写完，T2没仔细看直接开始莽 $ n^3 $ dp，写完还调了一小下，20分钟不到搞完了。。 想了想T2优化，发现没时间回头写T3，链没写完就结束了。。 最后T3没清空边，40 -> 25 D2真的心态全崩。。 可惜如果D2没心态那么炸暴力打满还说不定可以卡线入冬令营，现在看来全没了。 就这样了吧，明年CSP前估计也就SCOI能打一打了。 总结教训，心态也是得锻炼的吧。。 其实去年D2心态可能比今年更炸（大概是全省唯一一个去年MLE D2T2 45 -> 0 的），而且如果去年的我2h40min弄出T1非正解估计都没心态看T2T3了吧？ 去年到今年的进步大概只是从卡线省一到比较高的省一。 不过还有一年呢，明年继续加油，Bless All QWQ~