cdw的博客

博客

Public Round #2 题解

2022-04-09 13:07:07 By cdw

划分

题目来源:Romanian Master in Informatics 2021, Day 1, Task "Gardening".

QOJ 链接:https://qoj.ac/problem/2808

官方题解:https://rmi.lbi.ro/rmi_2021/editorial.pdf

引理 1. 若存在正整数 k2×(2k+1) 的连续子矩形使得第一行全相同,且与第二行的第一个和最后一个元素相同,则不合法。

证明. 考虑对 k 归纳:当 k=1 时显然不合法,否则考虑第二行去掉第一个和最后一个元素,长度 2k1 为奇数,所以存在长为奇数 2k+1<2k+1 的相同元素构成的连续段,k=0 时显然不合法,否则以该连续段作为“第一行”应用该引理即得证。

推论 2. 若有解则 NM 均为偶数。

证明. 否则不妨设 M 是奇数,在外侧套一个矩形边框转化为 (N+2)×(M+2) 的情况,前两行满足引理 1 的条件,矛盾。

引理 3. 若有解则 KNM/4KNM/41

证明. 显然每个省至少有 4 个城市,且更多时至少有 12 个。

引理 4. 对于每一行,存在某个出现在这一行的省,使得这个省仅出现在这一行及以上或这一行及以下。

证明. 定义列集合 S闭合的当且仅当在这一行出现在这些列的省仅出现在这些列。考虑对所有闭合的列集合 S 证明该引理:对 |S| 归纳,当 |S|=2 时其中的省显然只能为 2×2 的正方形,从而成立;否则任选其中某个省,若其符合条件即得证,否则考虑其在这一行的“内部“ T,显然 |T|<|S|,由归纳假设得证。

例如当 S 是全集时,在下图中选择红色的省,那么绿色部分就是 T

CCWG__6N6DN5HN`IIZT_1C7.png

推论 5. 若有解则 Kmax

引理 6.N=MK\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 0i>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

背包

题目来源:

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)

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。