在这场比赛中暴露了自己的真实水平(指只会做 Div.2 的 ABC ),被所有人打爆了.
A - Acacius and String
枚举 abacaba 出现的位置,其他 ? 用 d 填充,检查是否合法即可.
B - Dubious Cyrpto
显然最多只会有一种物品拿超过 $1$ 个,枚举这种物品即可.
C - Choosing flowers
枚举 $a$ ,检查 $n=\lfloor\frac m a\rfloor,\lceil \frac m a\rfloor$ 是否合法.
D - New Passenger Trams
只用考虑 ban 掉的区间的右端点 $+1$ 为关键点或左端点 $-1$ 为关键点的 $O(n)$ 个区间即可.
E - Inverse Genealogy
$n$ 是偶数无解, $n = 1$ 时 $k = 0$ 才有解.
$n$ 是 $\ge 3$ 的奇数时，$k > (n - 3) / 2$ 无解，$(n + 1)$ 是 $2$ 的幂且 $k = 1$ 无解，不是 $2$ 的幂且 $k = 0$ 无解.
$n = 9$ 且 $k = 2$ 无解.
其余情况都有解,构造方案时为两个儿子分配有解的 $n,k$ ,变成子问题继续处理.
F - Chess Strikes Back
将棋盘分成 $nm$ 个 $2\times 2$ 的正方形,那么就需要在每个正方形内放恰好一个国王.
若一个正方形左上角的格子被 ban 掉了,称它为 L 类小正方形,若右下角被 ban 掉了,称它为 R 类正方形.
一个正方形可以既是 L 类也是 R 类,也可以都不是.
若一个 L 类正方形在一个 R 类正方形的左上方(可以在同一行或同一列),就无解,因为此时这两个正方形的路径上一定会出现两个相邻的国王,其余情况都是有解的.
于是问题转化为如何判定是否存在这样的一对正方形,每次修改可能会加入 / 删除一个 L 类 / R 类正方形.
记 $S_L,S_R$ 为 L,R 类正方形的集合,用 set 维护 $a_x=\min \lbrace y \ |\ (x,y) \in S_L\rbrace, b_x=\min \lbrace y\ |\ (x-1,y) \in S_R\rbrace$ .
有解可以转化为对任意 $i>j$ ,有 $a_i>b_j$ 成立,用线段树维护区间的 $\min a_i,\max b_i$ ,合并区间时 check 是否合法.