之前听说今天的考试难度是 NOIP - 。
T1
赛时只会暴力。甚至还想出了比时间复杂度 \(O(n^2)\) 的暴力更慢的时间 \(O(n^3)\)（可能不是，可能要 \(/ \omega\)）的 bitset 做法。
正解之一是 xor hashing。前年（T3）、去年（T2 ?）的 CSP-S 我都没想出 hash 做法。感觉自己缺乏想 hash 的意识。
这个题：由出现次数的奇偶性想到异或，但直接异或可能会出现问题（\(1 \operatorname { xor } 3 = 2\)；\(1 \operatorname { xor } 2 \operatorname { xor } 3 = 0\)，但我们预期的是 \(2 \operatorname { xor } 2 = 0\)）。于是考虑让本身紧凑的值分散开，用随机数实现，把同样的数变成同一个数。这样就可以直接用异或来做了。
另，[树链的 xor 和] 可以转化成 [两个端点到根的路径的 xor 和] xor 起来。
另外好像还有点分治做法。
T2
显然有（时间）\(O(n^2k)\) DP。用前缀和，在 DP 转移方程里拆前缀和（\(sum_r - sum_{l-1}\)）。发现转移的时候是从一段 前缀/后缀 里求 max/min，于是可以直接优化成（时间）\(O(nk)\)。（注意前缀和要处理原 [序列]（？） 上第一个位置 \(- 1\) 的位置（原 [序列]（？） 上第一个位置的前一个位置），虽然在这题中初始化为 \(0\)（全局数组）即可，但还是要注意，有时要特殊考虑，不要数组越界了（原来就是从 \(0\) 开始的情况））
\(O(nk)\) DP 预计有 \(50\) 分。
然后赛时我整了个贪心乱搞。发现最后可能是在某个区间上反复横跳。于是在 DP 后枚举跳了多少次后在哪个位置，剩下的次数都拿来在 这个位置作为端点且方向正确的 和最大的 区间上反复横跳。
然后没想到这样就有 \(90\) 分了。
正解是找贪心结论 + DP。详见题解。我还没完全搞懂。
T3
应该算是构造题。
感觉我现在做构造题没什么章法。可能是做少了也总结少了。
赛时只有大概的想法。和正解有相似之处，但是想法不清晰，应该也不对。就是说自己有一点感觉，但不多。
正解有 递归，划分成子问题，再合并 的思想（算不算分治？）（有点像树形 DP）。感觉树上的东西就 [很]（？） 可能是这类做法。
听说这个题是树分块的基础。（？）但是一位 [新高二]（？） 的学长认为我们现在不用学树分块。
T4
赛时想偏了。
正解：FHQ-Treap，结点维护复杂的东西 + 复杂的 PushUp（找了奇妙的性质）。
正解用了从弱化的问题着手的思想。在此题中即先考虑二元的情况，再由二元推至题目中三元的情况。
总体的总结
赛时一个题都没有想出正解。该打的暴力都打了，应该没有挂分。贪心乱搞 骗分 运气好骗到了 \(40\) 分。听说相比 NOIP，这次暴力分给得很多。
自己实力不足。思维上很弱，有的技巧套路（T1）不熟悉；有的题（T3）只有感觉，没有想出正确清晰的做法。而且思考的时间太长了——从 8:00 考到 12:00，我大概 [9:30]（？？） 左右才开始写代码。
还是尽量把题都改了，多写博客总结吧。而且我应该有意识地去总结本质的东西。
2024.8.11
标签：11,xor,赛时,2024.8,operatorname,正解,集训,DP,前缀 From： https://www.cnblogs.com/huangkxQwQ/p/18353875