2025 年 8 月（及以前）做题记录
可能会不定时放一些远古时代的题目。
[NOI2005] 月下柠檬树
平面几何，自适应辛普森法求面积，预处理圆的公切线，求值时单点取 max。
复习一下 simpson 公式 \(\dfrac {r-l} 6 (f(l)+f(r)+4f(\dfrac {l+r} 2))\)。
注意如果超时可以去除层数的限制。
[HAOI2015] 数组游戏
博弈论翻棋子游戏 + 整除分块，感觉还是挺结论的。可能考场上打表或者认真思考也可以发现。
Hard Life
网络流最大权闭合子图模板，参考的这篇题解。
[PA 2022] Mędrcy
好像是随机跳到的？
考虑从 corner case 开始到一般，这种每个人都绝顶聪明的推理要从每个人的视角考虑是否出现矛盾，即假设自己没有不知道的咒语，看他人的反应和基本公理是否冲突，可推断自己的状态。
最后得出结论求最小点覆盖，由于点数 \(k \le 30\)，可用 \(T(n) = T(n-1) + T(n-3)\) 的最小点覆盖做到可以接受的复杂度（朴素做法 \(\mathrm{O}(2^k)\)），参考。
有空补一下 CF164D。
【UR #6】懒癌
感觉还是比较抽象的，首先考虑一个人什么时候开枪，由于每个人都知道整个有向图，所以每个人可以从自己的狗没病的情况出发，在符合自己所见的情况中枚举所有可能状态，取最大值后+1即为开枪时间。转移成环的话都不开枪（相当于每个人都在等别人开枪）。
然后这个转化就抽象了，我们首先建一个有向图，图中边 \(u \to v\) 存在当且仅当 \(u\) 看不见 \(v\)，然后考虑一个病的状态 \(s\)，将有向图上的 \(s\) 中的点染黑，发现每次选择一个人转移相当于枚举 \(u \in s\)，然后将 \(u\) 染白，将 \(u\) 的出边的一个子集染黑，求最大操作次数（做一次+1）。因为我们对有病的狗的主人的开枪时间取 min，所以每次只选除自己外可达前驱中没有黑点的黑点染白（不然的话选前驱会更小，前驱会再次染黑这个点，避免冗余操作）。显然黑点越多操作次数不降，而且转移成环相当于有向图中的一个环不停转圈，所以考虑缩点。如果一个强连通分量由至少 2 个点缩成，即存在环，那么这个强连通分量内以及它的前驱都不能染黑，否则没人开枪。然后考虑剩余点中染黑一个子集，发现策略是能染黑就染黑，且每个点只会染白一次，于是所有初始黑点的可达后继求个并集，大小就是开枪时间。
那么开枪人数呢？发现一个状态中开枪人数是取到 min 值的位置数，而为了取到 min 值，上面有提到只选除自己外前驱中没有黑点的黑点，计数是显然的。
用 bitset 优化求可达点集做到 \(\mathrm{O}(\dfrac {n^3} \omega)\)。
【UR #19】前进四
Segment Beats。
可以兔队线段树做到 2log，不足以通过。
考虑离线，对序列进行扫描线，维护时间轴。每次扫到一个数，它在时间轴上呈现若干个区间，且这些区间总个数是 \(\mathrm{O}(n+q)\) 的。操作时对区间取 min 并记录有效取 min 次数，可以 Segment Beats \(\mathrm{O}((n+q)\log n)\) 解决。
有空补 线段树 3。
[NOI2018] 情报中心
赛时没有认真思考，感觉看完题解好像没什么难点。
关键在于想到将贡献分拆在 lca 上，然后是带权直径的板子，可能会有一点细节。正解是分讨，会复杂许多。
[NordicOI 2022] 能源网格 Power Grid
想着数论做法，一边 assert 一边拍验证结论，大脑直接放空，导致获得 0 分。
还是要独立思考，发现自己在无脑猜结论时出去洗把脸。
主要是思路错了，一直 dfs 导致极其低效，做了 1h 后就应该反思或者放弃，正解思路有一点重合，感觉还是没有 bfs 式想题。
[ROI 2024] 无人机比赛 (Day 2)
被低年级选手单调队列 /ll
重点在于发现前缀严格最大值只有 \(\mathrm O(\sqrt n)\) 且只有这些位置有意义。然后拆贡献得到几个 \(\sum\) 后再根号平衡下就可以得到 \(\mathrm O(n \sqrt n)\) 的做法。
错误之一是没想到是根号，一直想 log 的部分分。然后是没拆贡献，感觉还是 trick 没有把握好。
[WC2016] 挑战NPC
一般图最大匹配，感觉还是挺考思维的。
AGC005E Sugigma: The Showdown
AGC 还是太吃思维了，什么时候可以战胜 /yiw
关键在于注意到如果一条边在另一树上两点距离大于 2 会 inf，于是只考虑距离为 1,2 的边。
又发现在对手的树上一定会深度递增（以对手起点为根），于是对手会不停向当前点走，即策略可定，dfs 找最优解即可。
P8864 「KDOI-03」序列变换
第一次被决策单调性打败，深刻认识到自己什么都不会。
赛时写了一个复杂 DP，没有想到更简单的形式，可能是后续优化没能进行的原因。
关键在于简单地刻画相邻两个不同位置最多 \(k\) 个，发现可以刻画成最多 \(\lfloor \dfrac k 2 \rfloor\) 连续的 1 段，奇数时特殊处理下。
于是用 \(w_{l,r}\) 表示所有的 \([l,r]\) 中的 1 移动到一起的花费，因为一定取中位数为中心最优，可以 \(\mathrm O(n^2)\) 预处理。
然后发现转移是 \(k\) 次 \((\min,+)\) 矩阵乘法，于是快速幂做到 \(\mathrm O(n^3 \log k)\)，运用神秘的决策单调性可以做到 \(\mathrm O(n^2 \log k)\)。
[JOISC 2024 Day2] 棋盘游戏
可能看到 \(5 \times 10 ^ 4\) 已经不知所措了，赛场上打了 17 分还挂了。
关键在于想到其他 \(k-1\) 个棋子有两种决策，就是在两个棋子之间跳或者围着一个棋子跳，所以 \(1\) 号点每多经过一个停止单元格就会增加至少 \(k-1\) 的贡献，所以最多多经过 \(\lfloor \dfrac n {k-1} \rfloor\) 个。于是有 \(\mathrm O(\dfrac {n^2} k)\) 的做法。
然后发现 \(k\) 很小的话可以枚举斜率去切凸包，跑 dij 可以做到 \(\mathrm O(nk \log n)\)。
平衡下可以做到 \(\mathrm O(n \sqrt{n \log n})\)。
细节有点多，考察了 01bfs 和 dij。主要难点在于想到一个点对答案贡献是斜率为 1 或 2 的函数，然后想到两种做法后平衡。
P13497 【MX-X14-T7】墓碑密码
FWT 计数题，主要是想到用 FWT 推式子，然后用 __int128 和 popcount 加速计算 \(\sum_{j \in S} (-1)^{|i\cap j|}\)，可能推式子需要一定的熟练度不然会推错或者做不出来，最后预处理组合数就好了。
还是有一定难度的，有空补 利物浦集合。
[POI 2023/2024 R1] Satelity
\(n + \lceil \log_2 n \rceil\) 是显然的，然后就懵逼了。
发现原来可以这么推：设左边 \(s_l\)，右边 \(s_r\) 个等价类（不失一般性设 \(s_l \le s_r\)），设左边最大等价类有 \(c_l\)，右边有 \(c_r\) 个，那么花费是 \(s_l + \lceil \log_2 c_l \rceil + \lceil \log_2 c_r \rceil\)，容易发现 \(s_l \le n - c_l + 1\)，\(s_r \le n - c_r + 1\)，又 \(s_l \le s_r\)，设 \(x = \max (c_l,c_r)\)，花费不会超过 \(n-x+1+2\lceil \log_2 x \rceil\)，这个东西超过 \(n+1\) 是 \(x=3\) 或 \(x=5\) 的 corner case，特判即可。
还是比较思维的，以后束手无策时可以考虑设一些量推一推说不定发现上界。
P11692 [Ynoi Hard Round 2025] 《十字神名的预言者》宏伟（色彩）
lxl 安利的可持久化平衡树题。
先考虑 \(r=n\) 的情况，发现相当于在值域上从某个区间复制而来，或者再重复几遍然后放到操作的定义域中，并且对其中一段异或上 \(a\)，于是可以用可持久化平衡树维护。
考虑一般情况下会出现什么状况，可能会产生 \(r\) 以外的贡献导致答案出错。一般的想法是 pushdown 的时候记录下异或产生的位置并且不合并标记，但是空间可能爆炸。
这时候需要用到取模的性质，即一个数取模不超过 \(\mathrm O(\log V)\) 次，因为一次取模至少减半。然后考虑 tag 用一个特殊节点表示，即操作点，只有一个儿子，节点本身有异或的信息。从节点内分裂出的子树要重新打上 tag，合并时不对特殊节点进行分裂。
考虑这样做树高时多少，发现从平衡树上一个普通节点往下走后如果不是走到特殊节点那么 size 减半，否则因为取模发生 \(\log\) 次，所以特殊节点只经过 \(\log\) 个，总树高还是 \(\log\) 的。
这里用到了全局平衡思想，即把取模的 \(\log\) 与平衡树的 \(\log\) 相加而非相乘，得到更优的复杂度，类似于全局平衡二叉树从树剖处优化而来。
总时间复杂度 \(\mathrm O(n \log n)\)，不卡常。