11.2
这是 CSP 之后触发保底机制了吗，怎么是 4 + 0 模拟赛。
Kia Bakes a Cake
DS, dp, CF*3100.
模拟赛场上虽然一直在饭堂但是这个题最后还是过了没有变成区。
首先发现有不能重复的限制连多项式复杂度的暴力都打不出来，接着感觉不能重复的限制是假的，然后尝试证明发现容易有 \(\sum\limits_{j=2}^i \text{dist}(s_{j-1},s_j)<\text{dist}(s_i,s_{i+1})\)，而对于任意一个 \(s_j(j，\(\text{dist}(s_i,s_j)\) 小于等于前面那一坨，因此 \(s_j\) 不可能作为 \(s_{i+1}\) 出现。
于是考虑 dp，由于答案显然不高于 \(\log_2 n+1\)，可以将长度作为第二维，又因为需要考虑起点所以转置，令 \(dp_{u,i}\) 表示从 \(u\) 出发走 \(i\) 步，第一步的长度最大是多少。对于起点 \(u\) 来说，答案即为最大的 \(i\) 满足 \(dp_{u,i}\ge 0\)
。
转移形如 \(dp_{v,i+1}\leftarrow \text{dist}(u,v),2\text{dist}(u,v)\le dp_{u,i}\)
，容易点分治优化。场上饭堂了写了树状数组 3log，虽然把点分治过程离线下来只需要 500ms 不到，但是这个偏序范围是最大深度，直接开个数组维护最大和来自不同子树的次大即可。
回天
DS, Number Theory.
首先去重。值域很大，枚举其中一个的 \(\gcd\) 是没有前途的。有一个简单的解是把所有最大值 \(x\) 单独拿出来放进 \(A\)，剩下的放进 \(B\)，答案一定不会低于 \(x+f(B)\)
。
考虑如果 \(A\) 中掺进去其它元素，一定有 \(f(A)\leq x/2\) ，并且只要 \(B\) 中不同元素 \(\ge 2\) 个，\(f(B)\) 也一定 \(\leq x/2\)
，显然是不优的。由此得到一定有一个集合中只有一种数。
这里可以直接大力前后缀合并维护了。但是发现这个单独放一个集合的数一定是最大或次大值。假设次大值为 \(y\)，对于一个 \(z，有 \(z+\gcd(S\setminus\{z\})\le z+\gcd(x,y)\le z+x-y，一定不优于把最大值单独拿出来。
直接维护除开最大值和次大值的 \(\gcd\)
即是 1log。
[UOI 2025 II Stage] Digital Game
Ad-hoc.
神人 @xxxxxzy 叫人一起享用震撼美味。
发现部分分非常诡异，而且没有什么思路，考虑先大力状压 dp \(O(2^nn)\)
打表。发现不了任何规律，但是判一下初始就输了就可以得吃六个包的部分分。这个部分分摆成这个样子想必有什么深意吧！
此时发现第一个包一定是 No，这是为什么呢？紧接着发现其实是在 \(n\ge 4\) 时才会必输。那么第二个包呢？打个表发现第二个包在 \(n\ge 10\) 时必输！那么我们结合剩下的猎奇部分分合理猜测 \(n\ge 20\)
时必输！然后发现过了！
证明可以根据字符集大小归纳。
[UOI 2024 II Stage] GCD, Sum, Multiply. What?...
DS.
什么东西。
对右端点扫描线，显然后缀 gcd 只有 \(O(\log V)\) 种，只有边界位置可以贡献答案。直接大力数点可以做到 \(O(n\log n\log V)\)
。
但是我们可以动态维护贡献答案位置对应的单调栈，可以做到 1log。
11.3
杂题。
神人 tzy 给我喂弱智题然后我（几乎）全都不会做。
CF1601D Difficult Mountain
Ad-hoc, CF *2700.
考虑 exchange argument，然后分讨即可。
排序之后可以直接贪心，而不是像这个弱智一样 dp。
CF1781F Bracket Insertion
dp, CF *2700.
考虑左括号 1 右括号 -1，条件等价于任意时刻最小前缀和非负。
直接正着做需要刻画整个序列。考虑第一次操作插入的括号对，之后的操作会在三部分进行，每一部分的前缀和都会被加上 \(0,-1/1,0\)，于是可以设计 \(dp_{i,j}\) 表示前缀和整体加上 \(j\)，在 \(i\)
次操作后仍然合法的方案书，可以分步转移优化。
QOJ10542 Protecting Kingdom
DS.
一个简单的想法是长链剖分，然后合并轻儿子贡献时二分更新答案，这样是 1log 的。
考虑到答案的上界是 \(\sum k\leq 10^6\)
，可以直接每次检查当前答案能够增加，均摊线性。
[UOI 2023] An Array and XOR
DS.
考虑给定集合怎么做，直接在 Trie 上贪心，如果当前节点只有一个儿子，可以将 \(x\) 这一位设置为相反值来获得 \(2^i\) 的贡献。否则两个子树只能取一边，两边取 \(\max\) 即可。莫队维护 Trie 上这个 dp 可以做到 \(O(nm\sqrt q)\)
，不太能过。
上面是 tzy 喂给我时他说的部分，但是我觉得被他带歪了，非常生气！
我们直接考虑枚举 \(x\)。显然 \(x\) 应当是某个 \(a_i\) 的补，而答案的二进制下第 \(c\) 位为 \(1\) 当且仅当比 \(c\) 更高的位与 \(a_i\) 相同的 \(a_j\) 第 \(c\) 位也都和 \(a_i\) 相同，也就是在 Trie 树上这个地方只有 \(a_i\) 一个方向的儿子，可以发现这本质是直接维护 dp 的决策点。发现对于一个 \(i\) 向左向右分别有 \(O(m)\) 个使贡献发生改变的位置，因此共有 \(O(nm^2)\)
个支配区间。
可以直接数点，由于 \(nm^2\) 和 \(q\) 根本不是一个量级，考虑分块平衡到 \(O(nm^2+q\sqrt n)\)
。
[SWERC 2021] Drone Photo
Ad-hoc.
怎么，不会，弱智题/ll
研究发现每个合法的块都恰好对应两个“角”的结构，满足“角”的顶点是中位数，于是 \(O(n^2)\)
数出"角"再除以二就对了。
[VKOSHP 2025] Strange Sum
dp.
首先考虑刻画笛卡尔树结构，可以想到树上差分一下转换贡献为 \(f(l,r)=\sum\limits_{i=l}^r\sum\limits_{j=i}^r w_{i,j}\)
。
然后 \(f\) 显然满足四边形不等式，所以随便乱选一定能对应一组解。然后是一个背包的优化，可以先贪到剩余重量不超过 \(O(n^2)\)
。
11.4
什么叫昨天才做了一个长剖题今天模拟赛 T3 就搬了 QOJ14805 Cyan White Tree。为什么今年五月做过这个题但是其他人没做过。
T4 还是 Priority Queue 3，前两个题没有难度，绷不住了。
QOJ9986 Shiori
DS.
考虑每次暴力找 mex，如果没有操作一复杂度是对的，因为小于 mex 的数全都至少会翻倍。
有操作一可以颜色段均摊，每次可以直接取出一整段连续段一起处理保证复杂度。
[THUPC 2024 决赛] 古明地枣的袜子
DS.
等价类分治板子。
把修改操作按 \(x\)
排序之后相当于找到某个时间区间内的 info 合并起来，可以直接分块然后内部等价类分治。
复读机 / repeat
Ad-hoc, ds.
考虑二分答案 \(A\)，按两个数相加 \(\leq A\) 的套路将数分为 \(\leq A/2\) 的和 \(>A/2\) 的，容易发现 \(\leq A/2\) 的必选，\(>A/2\) 的要选不可能将 \(\leq A/2\)
的顶掉，然后数据结构随便做做即可。
[ICPC 2022 Jakarta R] Sharing Bread
Counting, math.
不想说什么了。
11.5
模拟赛，但是累死了，完全摆着打，T1 做了 inf 小时，T2 大模拟挂飞了，原因是无解漏判了，T3 做了 inf 小时最后 10min 写了个 \(O(n^4)\)，但是赛后随便做都是 \(O(n^3)\)
，什么东西。T4 感觉就是需要时间做，但是场上相当于开都没开。
CSP 出分了，\(100+100+68+50\)
，T3 好多假算都在反向挂分，虽然能够预料但是输出大样例可以获得 24 就是态度问题了吧。不是为什么有人嘴上说不在意 CSP 成绩却又明晃晃拿 CSP 成绩恶心人。