251025 以前 x 天

P7078 [CSP-S 2020] 贪吃蛇

70 分是容易的。要想做到线性需要发现性质：只要吃完之后不变成最小值就吃，这样生成的蛇的体力具有单调性，可以用线性数据结构进行维护。

P8069 [BalticOI 2002] L Game © Edward de Bono (Day2)

倒序进行转移，如果一个节点的胜负已经确定（能到达一个必败节点或者只能到达必胜节点），就将它入队。这样做完，最终都没有入队的节点就是所有平局的点（因为总能到达另一个平局点）。

P6845 [CEOI 2019] Dynamic Diameter

单修边权，全局直径。需要注意到在 dfn 序上修改一条边 \((u,v)\)（假设 \(u\) 是 \(v\) 的父亲）不会影响包含于 \(v\) 子树内的区间，也不会影响和 \(v\) 子树不交的区间。因此直接把 dfn[v] 和 dfn[v]+sz[v]-1 update 一下即可。时间 \(O(n\log^2n)\)。

P7124 [Ynoi2008] stcm

拍到 dfn 序上，考虑用分治法处理，由于区间之间要么无交要么包含，因此跨过分治中点的所有区间都具有包含关系，可以 \(O(n)\) 扫一遍做完，总次数 \(O(n\log n)\)。

在区间通过包含关系形成一棵树时，并且不方便合并和删除（只能插入和撤销），可以用启发式合并凑出区间，可以用分治凑出区间补。

qoj8704. 排队

用平衡树维护括号序，因为知道左右括号各自的节点编号因此可以很方便的分离出子树。

用结构体存平衡树可以显著减小常数（Cache）。

P3653 小清新数学题

把三次根号以内的所有质数筛出来，然后拿它们把 \([L,R]\) 筛一遍，现在每个数要么剩两个大于三次根号的质数，要么剩一个质数。这两种情况用 Miller-Rabin 判出来，对于两个质数的情况用 sqrt 判一下两个质数是否相同即可。

由于 \(E(\omega(n))\to \ln\ln n\)（反正自己拿质数表累乘一下也知道上界不会太大），因此复杂度是 \(O(\sqrt[3]{V}+(R-L)\ln\ln V)\)

P10681 [COTS 2024] 奇偶矩阵 Tablica

神仙题

发现按行或者列都不好 dp。注意到我们本质不关心行和列的顺序（可重集排列），只关心数量，因此设有 \(a\) 行为 \(1\)，\(b\) 行为 \(2\)，\(c\) 列为 \(1\)，\(d\) 列为 \(2\)，满足 \(a+b=n,~c+d=m,~a+2b=c+2d\)。

考虑对一组 \(a,b,c,d\) 计数。考虑组合意义，将行看成 \(a+2b\) 个有颜色小球，要将它们分配给列，每列至少拿一个，至多拿两个，不能拿两个相同颜色的小球。先 \(\binom{n}{a}\binom{m}{c}\) 钦定哪些行和列是 \(1\) 和 \(2\)。然后考虑把 \(a+2b\) 个小球可重集排列，方案数是 \(\frac{(a+2b)!}{2^b}\)，再按顺序分配给每列。发现这样有两个问题：交换一列拿的两个小球会算重成两种方案，并且可能拿两个相同颜色的小球。

算重的问题直接除以 \(2^d\) 就可以。颜色重复的问题考虑容斥，钦定 \(d\) 列中有 \(k\) 列拿了相同颜色的小球，稍微组合数算一下即可，式子是 \(O(n^2)\) 的。