乙模复四-2023-03
质量检查
注意到每个样品只有两个，这表明我们对于每个物品，只能先一块一块得测，如果显示有杂物，就只能一个一个测。
设 \(g(x)\) 为测 \(x\) 个得期望步数。
\(g(x)=1+x(1-(1.0-k)^x)-(1.0-k)^{x-1}k\)
即：先整体测一次，有 \((1-(1.0-k)^x)\) 会出现其中有杂物品，这时候只能每个都单独测一遍。等等，我们真的要测完吗，如果前 \(x-1\) 个都没有杂物，那最后一个肯定就有杂物，那么减去 \((1.0-k)^{x-1}k\)。
我们三分一下块的个数 \(x\)，就有答案函数 \(f(x)=g(n/x)\times (x-n\bmod x)+g(n/x+1)\times (n\bmod x)\)
这是单峰的。
电路
拓扑序板子。
铁路建设
随机化题目。
先生成最小环为 \(k\) 的最少边的图。然后随机加边。
mt19937 的种子为 1919，改了就不能过。
字符串移位
50 分，可以写一个平衡树。
100 分，写一个可持久化平衡树。
甲模复四-2023-02
我们出题团队出的题！
防御
缩点后 DAG 上跑支配树。
u 在支配树上的父亲，即它的原图上所有接了它的点在支配树上的 LCA。
星酱与雷达
树形 DP。
设两个 DP，分别 \(v\) 及其子孙……\(v\) 及其弟弟森林……。
空战
可以发现两个序列的结尾怎么样，都没什么影响，直接 DP 即可。
终末旅行
发现儿子有序的有根树等价于括号序列。
于是直接平衡树加线段树分治，用并查集维护连通性。
乙模复四-2022-13
质因数个数
筛 \(\sqrt n\) 以内的质数，需要判 \(n\) 自己是不是质数。
也可以从小到大枚举 \(\sqrt n\) 以内的质数，每次除到不能除为止（质因数分解）。
全排列的价值
打表找规律。
也可以推式子，\(f(n)=n\times f(n-1)+\frac{(n-1)n}{2}\times(n-1)!\)
砍竹子
发现一个竹子很快就没了，把每个竹子的所有状态都存下来，用大根堆维护。
重复的数
莫队模板题。