CSP-J2/S2 游记

抱着玩玩的心态去打一下 J 组。

开题，秒 T1，秒 T2。T3 找找规律，也不是很难。半个小时左右开 T4。

然后就是各种不会。想到 T4 的 DP 了但还是不会转移。最后几分钟极限发现 T3 的一个错。300 pts 遗憾离场。

认真打了 S 组。进场先打了线段树。

14：35 开题。14：42 过了 T1。

然后先看了一下后面三个题。发现 T2 大概是个中型的模拟，T3 是小清新 DP，T4 是一堆东西。

决定了先思考一下 T2 正解。第一问维护前后缀做是容易的，第二问可以转化为经典区间选点问题，贪心是显然的。稍微用点技巧规避一下浮点数就过了。此时还剩 3h。

然后决定想一个小时 T3，想到了以 f_{i,j,0/1} 表示将 [j,i] 全部涂成红/蓝色的答案。本来以为这个转移是 O(n^3) 的，但是可以发现 O (n) 的转移只有 n 次，所以是平方的。50 分拿下。随后思考 15 分的 O(nv^2) 做法，无果。

这时候我觉得 T3 在优化就不太可做了，于是果断看了 T4。T4 的 12 分暴力可以做，但是细节超级多。我写了将近 60 min 过了样例 1。

最后还有 15 min，也没有得分了。期望得分 100 + 100 + 50 + 12 = 262。

总结：没想 T3 线性做法，输。

upd on 11.4: S = 262 > J = 200，蚌。