- 搬题人：
- A, B：cdw
- C：p_b_p_b
- 组题人：cdw
- 题解：cdw，p_b_p_b
划分
题目来源：Romanian Master in Informatics 2021, Day 1, Task "Gardening".
QOJ 链接：https://qoj.ac/problem/2808
官方题解：https://rmi.lbi.ro/rmi_2021/editorial.pdf
引理 1. 若存在正整数 $k$ 和 $2\times(2k+1)$ 的连续子矩形使得第一行全相同，且与第二行的第一个和最后一个元素相同，则不合法。
证明. 考虑对 $k$ 归纳：当 $k=1$ 时显然不合法，否则考虑第二行去掉第一个和最后一个元素，长度 $2k-1$ 为奇数，所以存在长为奇数 $2k'+1 < 2k+1$ 的相同元素构成的连续段，$k'=0$ 时显然不合法，否则以该连续段作为“第一行”应用该引理即得证。
推论 2. 若有解则 $N$ 和 $M$ 均为偶数。
证明. 否则不妨设 $M$ 是奇数，在外侧套一个矩形边框转化为 $(N+2)\times(M+2)$ 的情况，前两行满足引理 1 的条件，矛盾。
引理 3. 若有解则 $K\le NM/4$ 且 $K\ne NM/4-1$。
证明. 显然每个省至少有 $4$ 个城市，且更多时至少有 $12$ 个。
引理 4. 对于每一行，存在某个出现在这一行的省，使得这个省仅出现在这一行及以上或这一行及以下。
证明. 定义列集合 $S$ 是闭合的当且仅当在这一行出现在这些列的省仅出现在这些列。考虑对所有闭合的列集合 $S$ 证明该引理：对 $|S|$ 归纳，当 $|S|=2$ 时其中的省显然只能为 $2\times 2$ 的正方形，从而成立；否则任选其中某个省，若其符合条件即得证，否则考虑其在这一行的“内部“ $T$，显然 $|T|<|S|$，由归纳假设得证。
例如当 $S$ 是全集时，在下图中选择红色的省，那么绿色部分就是 $T$。
推论 5. 若有解则 $K\ge\max(N,M)/2$。
引理 6. 当 $N=M$ 时 $K\ne N/2+1$。
证明. 由引理 4 知恰好有两行存在两个省满足引理 4 的条件，这两个省只能为 $2\times 2$ 的正方形，矛盾。
可以通过构造证明结合上述引理即为有解的充要条件：选取合适大小的矩形边框放在一角，其外部全填 $2\times 2$ 的正方形，递归到内部做。
史莱姆
题目来源：International Zhautykov Olympiad 2022, Computer Science, Day 1, Problem 2.
官方题解：https://qoj.ac/files/tutorials/IZhO2022/IZhO-draft.pdf
算法 1
显然按从小到大的顺序吃。
设排序后的序列为 $b_1,\cdots,b_m$，考虑 $b_i$ 能否吃掉 $b_j$：设 $\mathit{pre}_i$ 是前缀和，当 $i<j$ 时为 $b_j+k-\mathit{pre}_{j-1}\le 0$，$i>j$ 时为 $b_j+k-\mathit{pre}_{j-1}\le b_i$。
对于后者只需判断 $\mathcal O(\log V)$ 个 $b_j-\mathit{pre}_{j-1}$ 上升（即 $b_j>2b_{j-1}$）的特殊位置，用可持久化线段树维护，每次找出这些位置；对于前者，先求出不满足条件的最大的 $j$ 在哪两个特殊位置之间，然后直接二分即可。时间复杂度 $\mathcal O((n+q\log V)\log n)$，期望得分 $85$。
算法 2
from jiangly，期望得分 $100$。
背包
题目来源：
- 2021 KAIST RUN Spring Contest Problem H
- Problem Set: https://kaist.run/contest/2021-spring/problemset.pdf
- Petrozavodsk Winter 2022 Day 2: KOI TST + KAIST Contest Problem K
- XXII Open Cup, Grand Prix of Daejeon, Problem K
CF 链接：https://codeforces.com/gym/103627/problem/K
QOJ 链接：https://qoj.ac/problem/2562
直接考虑暴力：设 $dp_{x,i,w}$ 表示在 $x$ 子树内断掉 $i$ 条边，且现在 $x$ 所在的连通块的权值之和为 $w$ ，是否可行。用树形背包容易得到一个 $\mathcal O(nKR^2)$ 的做法。
注意到 $i$ 固定时除了 $x$ 所在的连通块以外的连通块的权值之和都在 $[L,R]$ 中，所以只有 $R-L+1$ 种，所以 $w$ 只有 $\mathcal O(K(R-L))$ 种取值。这样容易得到一个 $\mathcal O(nK^3(R-L)^2)$ 的做法。
由于 $dp$ 的取值只有 01 ，所以显然可以用 bitset 维护，做到 $\mathcal O(nK^3(R-L)^2/w)$ 。
引理 1. 如果 $dp_{x,i,w_1}=dp_{x,i,w_2}=dp_{x,i,w_3}=1$ ，且 $w_1<w_2<w_3$ ，且 $w_3-w_1\le R-L$ ，那么将 $dp_{x,i,w_2}$ 置为 $0$ 也不会改变最终答案。
证明. 设 $x$ 所在连通块最终的权值为 $W$ 。考虑如果使用了 $(x,i,w_2)$ 这个组合，那么把它换成 $(x,i,w_1)$ 或 $(x,i,w_3)$ ，则可以获得 $W-(w_2-w_1)$ 或 $W+(w_3-w_2)$ 。由于 $w_3-w_1\le R-L$ ，这两者也必然有至少一个是合法的，所以总是可以不考虑 $(x,i,w_2)$ 这个组合。
由引理 1 ，在 $w$ 的 $\mathcal O(K(R-L))$ 种取值中，只需要保留 $\mathcal O(K)$ 个为 1 的位置。所以复杂度为 $\mathcal O(nK^3)$ 。