2023.11.14
最近总是感觉退役将近。也许是 CSP 糟糕透顶的发挥让我不再自信，虽然我或许也从未有过。
现在终于理解了当年看 yybyyb 大佬博客时他所描述的心情了啊。。。
和同学魔怔的时候还是会笑出来，但心中的阴霾却始终扫之不去。
为什么这样的日子总是转瞬即逝？
请目送我走完，这最后一段路。
Simu D
大概猜一下，两个人最后取到的会相当均匀。先考虑已经分好两人会怎么走。
显然后手可以不断复制先手的决策，但有一部分堆先手还是可以多拿一次 \(val\) 的贡献，于是按 \(val\) 降序排序以后，先手多取的贡献就是 \(val_1,val_3,val_5\dots\)，第二组石子里就是 \(val_2,val_4,\dots\)。
场上脑子短路没想下面这个 dp，爆搜还打错了，真的降至啊啊。
有一个显然的 \(\mathcal O((\sum a)^2)\) dp：先按 \(val\) 排序，\(f(i,j,0/1,0/1)\) 表示前 \(i\) 种石子第一组放了 \(j\) 个，目前两组的“特殊堆”奇偶性。
考虑怎么优化？注意到 \(\sum p\) 很小，大概是 \(\mathcal O(\sum p\times n)\) 或 \(\mathcal O((\sum p)^2)\) 之类的东西。
考虑特殊堆的刻画，只需要知道两堆石子 \(\bmod 2p_i\) 的值，而不需要剩下的部分。假设第一堆放的数量 \(\bmod 2p_i=r\)，那么 \(r\le a_i\bmod 2p_i\) 的时候有 \(\lfloor\frac{a_i}{2p_i} \rfloor\) 个大小为 \(2p_i\) 的组可以随便分配，反之有 \(\lfloor\frac{a_i}{2p_i} \rfloor-1\) 组。为了统一方便后面的讨论，我们认为组都只有 \(\lfloor\frac{a_i}{2p_i} \rfloor-1\) 个，第一种情况再考虑 \(r+2p_i\) 的插入即可。
于是现在我们的 dp 变成了 \(\mathcal O((\sum p)^2)\)，但还没完，我们不能保证这是合法的。我们还需要知道，冗余的那些 \(2p_i\) 的组能否凑出 \(\frac{\sum a}{2}\)。
这是一个比较经典的问题。我们缩成 \(\mathcal O(\sqrt{\sum p})\) 个本质不同的组，整体做一个 dp 即可。也可以 bitset 优化多重背包，反正怎么都能过。
我写的很拉，喜提最劣解和最长解。shaber。
ABC230F
这个操作很 shaber 啊，序列上这种 shaber 操作就去考虑不变量，想到基于前缀和就能发现这个东西就是在问有多少 \(s_n\) 结尾的本质不同子序列。因为值域挺大要用 hash table 或者 map 实现这个经典 dp。
[SDOI2012] 走迷宫
有向图连通性直接 tarjan scc 缩点，然后 scc 内部跑高消，外部因为是拓扑序计算已经知道了直接当常量，过程中判一下 INF 即可。
[牛客练习赛 118 F] The Closest Pair
静态区间查询，点对，神秘最值，buff 有点多，考虑支配对。
换个好看的形式。\(x\bmod y=x-\lfloor\frac{x}{y} \rfloor y\)，枚举 \(y\) 和 \(\lfloor\frac{x}{y} \rfloor\)，只有 \(\mathcal O(V\ln V)\) 种。以向右扩展为例，假设 \(a_i=y\)，对于两个满足条件的位置 \(j,k\)，显然有 \(a_j\bmod a_i>a_k\bmod a_i\) 并且 \((i,k)\) 不能比 \((j,k)\) 拉，所以 \(a_k\bmod a_i<a_j\bmod a_k\)，假设 \(a_j=px+r,a_k=px+q\)，那么就是 \(r>q,q<r-q\)，右边那个 \(r-q\) 在 \(p=0\) 的时候还能再紧不过没必要，此时我们发现 \(2q<r\)，于是每次有效值域区间缩小一半，有效点对 \(\mathcal O(V\ln V\log V)\)，再用 BIT 扫描线维护查询，过程中用线段树 / ST 表维护。3log，不过可以过。我用的 zkw 线段树，跑得挺快。。。吧。