CSP-S 2022 VP 记

思考人生中 · 2022-10-29 23:24:30 · 个人记录

19:15开始VP的（

19:15

先开T1，感觉不难，只是点的判重需要点功夫。

19:30

开T2，发现很简单，开码。

19:40

感觉T2很多细节，先开T3，发现题意等价于判断所有点的出度是否为 1 。

20:07

想到了T1的做法，只要维护前三大即可。

20:41

T1写完调完，顺便看了眼T4。

21:00

感觉T4倍增可以做，所以先去切T2。

这很有逻辑

21:50

开始做T3的60pts做法，用的set不知道会不会被卡常。

22:34

调完了T3,知道自己T4基本寄了，开始写 k=1 的情况。

22:56

写完了 k=1 情况，仔细想了一下正解，想到的暴力倍增优化DP应该是 O(nk^3\log n) 的复杂度，写完估计至少有 88pts ，但是没时间了（悲

23:15

考完了，用民间数据测了一下，260pts 左右。

23:50

和cyk交流得知T4因为一些点数据随机直接暴力DP是76pts，亏大了。

总结

整体做题情况还算满意，但是不好之处是做题速度过慢，导致最后一题想出高分解法但是来不及写，应当多打一打CF。同时还有一些考场策略的问题，比如想到题目解法应当直接开写,而不是犹犹豫豫导致连暴力都没时间写。

不知道会挂多少分。

洛谷数据为 100+85+60+16=261pts 。

T2忘记特判 \text{INF} 的情况寄了。

Infinity Online Judge数据为 100+100+60+16=276pts

（估计T2数据氵了。）

发现自己T4来不及写亏了一大堆分。