9
初赛
DAY -1
对。
DAY 0
不对。
DAY 1
对。
感觉还行，由于休息够了感觉比既报 J 又报 S 的更有优势。
好了看题。
我去什么 KMP？什么线段树？什么 Trie？吓哭了。
然后是一道 DAG 拓扑排序的题，我觉得答案可能有很多，但选项的答案特别小，而且前面几题都选的 D，这题为了保险就选了 B 了。
然后单选题印象最深的就是两个“编程”题。
第一个是 01 背包。
不难发现当物品的重量越大，价值也越大。
我们还注意到全选不行，但是可以放弃一个选。放弃一个中，放弃第二个是最优的。那有没有其他情况呢？可以发现最小两个的价值加起来已经超过第二个了，所以不存在其他情况。
第二个是那个任务的。
第一眼看到感觉像可反悔贪心，然后正常按右端点排序，结果发现可以无惩罚解决，然后就结束了。
后面发现可反悔贪心做法假了。
然后是组合题。
第一题是一个简单全排列问题，当时时间还有一个半小时，我干脆直接把所有全排列都打了一遍。
第二题有点难绷。不过这是 CSP 第一次出交互题，还是挺震惊的。
题目意思就是给你两个相同的蛋，猛锤超过 kkk 次就会爆炸，求这个 kkk。
solve1 很简单，就是暴力试。
我没看 solve2，先猜一下，应该是分块，尝试 O(n)O(\sqrt n)O(n ) 次。结果果然如此，但是为什么他的分块这么奇怪，以递减数列来分呢？不管了，肯定有他的道理。
正常写写到最后一题时才发现原来他这么做是为了平衡次数，减小常数。比如说第一块最坏需要查询 1+131+131+13 次，第二块最坏要查询 2+122+122+12 次，以此类推。
第三题看着很唬人，其实也就是个折半搜索。
注意值域是 [1,m][1,m][1,m] 就行。
然后完善程序第一题是一道免费边的题，一眼分层图最短路，秒切。
第二题是个小交互，仔细读十几分钟题后就发现是枚举所有可能组合就行了，可以证明每种情况都有它对应的组合。
最小测试轮数我不会证，但题目也没要证。
最后注意的一点是，CCF 还是这么喜欢阴人，它的每一种情况是前 111 后 000 的，所以枚举全排列需要选上一个排列（prev_permutation）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY 1.5
去 ACGO 测了一下：我去？？？？？？93？？？？？？？
错了几个很糖的错误，比如那个 DAG 答案就是以上都不对，猜蛋那题 check2 次数可能比 check1 多。可以看出我不会造 hack 数据
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DAY +∞+\INFTY+∞
还真是 939393。群友现在还不知道他们被拉爆了。（我向他们报的是 737373）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
复赛
DAY 0
做了一下超速检测，2h2h2h 才做完第一部分。我该在哪里停留？我问我自己。
DAY 1
不想那么多了，相信自己。
666 监考老师把 J 组解压密码当 S 组放上去了，硬控我 1min。
666 放上去的解压密码漏了个 4，硬控我 2min。
先开 T1。
什么鬼。不超过 n2\frac{n}{2}2n ？那就枚举最大的咯？
不管了，先拿暴力分再说。
令 dp[i][j][k]dp[i][j][k]dp[i][j][k] 分别为拿 iii 个 111，拿 jjj 个 222，拿 kkk 个 333 的结果。
好的，303030 以内的数据都过了。
现在开始想正解。
首先蒙个结论：最多的一定拿 n2\frac{n}{2}2n 。然后枚举最大的贪心就行。
结果发现样例没过，结论假了。
现在还剩 3h3h3h，没办法了，先开 T2。
第一眼，肯定是 MST。
诶 kkk 这么小？估一下时间复杂度吧。有分 k=5,k=10k=5,k=10k=5,k=10 的数据，nnn 还只有 10410^4104，那时间复杂度不出意外就是 O(nk2k)O(nk2^k)O(nk2k) 了。
注意到原来的有很多浪费，我们真正需要的只有 n−1n-1n−1 条边，就是原来的最小生成树。
然后枚举 kkk 二进制位，看看选哪些是最优的。此时我们只需要 nnn 个点和这几个点连通就行了。排序后 MST 即可。
时间复杂度 O(nk2klog(nk))O(nk2^k\log (nk))O(nk2klog(nk))，瓶颈在于排序。
赛时没想到怎么优化，赛后才想到：我预处理出 n−1n-1n−1 条边和所有点的连边排序，这样每次枚举 kkk 就不用排序了啊，时间复杂度可以降到 O(nklog(nk)+2kn(k+nα(n)))O(nk\log (nk)+2^kn(k+n\alpha(n)))O(nklog(nk)+2kn(k+nα(n)))，我啥比吧。
然后看 T3。
我去 T3 怎么是字符串啊。有点难度，先打暴力。
好了暴力打好了，样例过。
先写一个哈希板子再说。
不对正解好像是 Trie 之类的。
那算了，还是看看 T1 吧。
又想了 20min 还是没想出来，那就拼测试点吧。
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我为什么场切 000 题，这下得被群友打爆了 555555555555555555。
拼好了，O(n4)O(n^4)O(n4) 的可以拿前 444 个点，错误的结论可以拿性质 A,B，随机数据也可以顺便过了。
总共 656565 分，但当时赛时以为是 O(n3)O(n^3)O(n3) 的，所以阈值定为 n>200n>200n>200，估计又少 10pts10pts10pts。
T3 后面还是想了想，弄了个 O(n2)O(n^2)O(n2) 的暴力和性质 B。
然后随便写写，最后考完后发现写了了棍母，喜提 0pts0pts0pts。
最终结果：55+80=13555+80=13555+80=135，T2 还可能挂。
我是给 CCF 送钱的那一批吧。
有帮助，赞一个