https://blog.hydd.cf/p/ioi2022/

Day2 T3 Thousands Islands 待填。

Catfish Farm

第 $i$ 列哪些鱼被抓住，只和第 $i$ 列堤的高度，以及 $i-1/i+1$ 列中较高堤的高度有关。

容易想到按列 dp，这样第 $i$ 列就有两种情况，较高的列是 $i-1/i+1$。

这个较高没有必要，仅仅多加了限制，所以可以每个 $i$ 自由选择 $i-1/i+1$，这样如果选的不是较高的答案只会更小。

我开始想的是，对于选择 $i-1$ 的，记录第 $i$ 列的高度；对于选择 $i+1$ 的，记录这列抓的鱼最高的高度。这样状态就表示算完了前 $i$ 列的答案，当前是选择 $i-1/i+1$。

其实不用这样，题目要求我们每一列选择一个堤的高度，就按照题目来，状态改为表示固定完了前 $i$ 列堤的高度，当前是选择 $i-1/i+1$。选择 $i+1$ 的答案在 $i+1$ 时再计算。

具体来说，记 $dp(i,j,0/1)$ 表示前 $i$ 列，堤恰好不覆盖这一列从下往上第 $j$ 条鱼，当前选择 $i+1/i-1$（当前列贡献 未计算/已计算）。对于前一列选当前列/这一列选前一列的，要算上增加的贡献。

https://qoj.ac/submission/44615

Prisoner Challenge

比较大小，容易想到在二进制下按位比较。$x$ 需要记录当前存的是第几位，当前位为 $\varnothing/A$ 的当前位的值是多少。

每次，如果当前记录的是 $A$，就拿 $B$ 这一位比较，如果相同跳到下一位，否则返回；记录的是 $\varnothing$，就把 $A$ 这一位记录进去。

这样次数太多（大概是 $3\log n$），但是用 $B$ 比较完相同后，你其实可以知道 $B$ 下一位的信息，把 $B$ 下一位信息存进去。可以发现，比较是按照位数 $B,A,B,A$ 交替，不需要记录里面存的是 $A/B$，现在只需要记录位数和当前位的值，大概是 $2\log n$。

一种思路是换进制，$k$ 进制应该是 $k\lceil\log_k n\rceil$，但还是不能通过。

二分和从高到低贪心填是几乎等价的。按照同样思路，可以改为每次把值域范围分成 $k$ 份，看是否在同一个值域区间，次数是 $f(n)=f(\lceil \frac n k\rceil)+k$，没区别。

题目保证了两个数不同，故如果当前数为 $1$ 或 $n$ 就直接返回，把剩下的范围再分成 $k$ 份，也就是 $f(n)=f(\lceil \frac {n-2} k\rceil)+k$。

把这个式子拿去 $dp$，对于不同的 $n$，$k$ 不固定，$f(n)=\min_k f(\lceil \frac {n-2} k\rceil)+k$，这样算出来 $f(5000)$ 恰好为 $20$。就按照 dp 出的方案选 $k$ 即可。

https://qoj.ac/submission/45397

Radio Towers

先考虑固定 $D$，对于选择的两个信号塔 $i,j$，中间要存在一个塔 $k$，$H_k\geq \max(H_i,H_j)+D$。

可以发现只有相邻的两个选择的信号塔才需要判断。

对每个 $i$，找到左右第一个 $k$，满足 $H_k\geq H_i+D$，分别记作 $L_i,R_i$。

$i,j$ 之间要有满足条件的塔，就要求 $R_i\leq L_j$（$i,j$ 中较大的对应的位置一定满足 $k$ 的条件），也就是区间 $[L_i,R_i)$ 两两不交。

同理易证区间只会有包含和不交两种情况（$D\geq 0$），对于两个位置 $i,j$，不妨假设 $H_i\geq H_j$，若 $R_i>L_j$，则区间 $[L_j,R_j)$ 都不满足条件，即 $R_i\geq R_j$。

不考虑询问的区间限制，$D$ 增加时，$L$ 只可能减小，$R$ 只可能增大，且根据证明，只有 $H$ 大的包含 $H$ 小的，故只会一些不是包含关系的区间变成了包含关系。

按照 $D$ 从小到大，每次把所有包含其它区间的区间全部删去（维护 $i$ 对应区间包含相邻某个的最小时刻），剩下的区间个数就是当前 $D$ 能选的数量。

有询问给定的区间限制 $l,r$ 时，把当前 $D$ 所有剩下的 $i$ 在 $[l,r]$ 内的个数求出来，但这样可能两边各少 $0/1$ 个区间（一个 $i$ 在 $[l,r]$ 内的，包含了一个在 $[l,r]$ 外的被删除了，实际上这个 $i$ 可以选）。

如果求出来的个数不为 $0$，看其中最小的 $L$ 和最大的 $R$，看 $[l,L),(R,r]$ 内是否还能选。要求区间内 $x\lt y,H_x-H_y$（或 $H_y-H_x$）的最大值，类似于 $ST$ 表的方法预处理即可。

https://qoj.ac/submission/45344

Digital Circuit

必须有一个叶子节点到根一路都是黑色，但是直接计数会算重。

要每一种方案对应唯一的叶子节点（相当于添加了限制条件）。

树的形态固定，由于根节点为黑色，说明儿子里至少有 $p$（参数）个是黑色，那么选择其中的第 $p$ 个黑色儿子，往下走。

最终会走到一个叶子节点，则设这种方案对应这个叶子节点。

现在考虑每个叶子节点 $x$，算对应到它的方案的数量。首先它到根的都必须是黑色，此外其它点的参数毫无关系，因为固定其它点的参数后其它点的颜色固定后，要求对应到的是 $x$，则 $x$ 到根路径的所有的参数是唯一确定的。

对每个叶子节点预处理出到根路径外的点的参数选择的方案数。线段树支持区间取反操作，维护所有黑色叶子节点的方案数之和即可。

https://qoj.ac/submission/45436

Rarest Insects

把不同的数放在不同的列，这个东西很像一个柱形图（？）

一种思路是每次删掉一行（删掉所有出现过的数各一次，需保证数量始终为 $1$），次数是行数（最多数出现次数）$\times n$。

另一种思路是每次删掉一列（删掉某种数的所有出现，需保证数量每次必须加 $1$），次数是列数（数字种数）$\times n$。

两种各做 $\sqrt n$ 次后一定能删完（数字总数为 $n$）。这样是 $O(n\sqrt n)$ 次。没什么优化空间。

第一种思路其实可以扩展成每次删掉 $r$ 行，需保证数量始终不超过 $r$ 即可。

求出数字种类数 $c$。考虑二分答案（上界 $\frac nc$），用第一种思路来 check 当前答案 $mid$，是 $O(n\log n)$ 次。

这个可以继续优化，如果 check 成功了（加入了 $mid\times c$ 个数），已经加入的数之后就不需要加了；如果 check 失败了，未加入的数之后也不可能加。

这样每次数量接近减半（有个上取整），次数共 $2n$ 左右。再加上外面求种类数的 $n$，总次数 $3n$ 左右。

这样一交得了 99.89 分，再加点优化，比如已经达到 $mid\times c$ 之后的就不需要尝试加入了，再 shuffle 一下序列防止被卡，就通过了。

不知道有没有不用随机化严格在 $3n$ 内的做法？

https://qoj.ac/submission/45454