cdw的博客

博客

Tags
None

Public Easy Round #1 题解

2022-04-23 13:02:23 By cdw
  • 搬题人:
    • A, D, E:p_b_p_b
    • B, C:cdw
  • 组题人:hehezhou
  • 验题人:AutumnKite, chenkuowen01
  • 题解:AutumnKite, cdw, chenkuowen01, hehezhou

捉迷藏

题目来源:

  • 京都大学プログラミングProgramming コンテストContest 2021, Problem L
  • Petrozavodsk Winter 2022, Day 1, Kyoto U Contest, Problem L
  • XXII Open Cup, Grand Prix of Kyoto, Problem L

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

为方便叙述,我们先假设树以 $v$ 为根。我们称距离 $v$ 为 $d$ 的点为“候选点”。令 $h=\lfloor\frac{d-1}{2}\rfloor$。

考虑一条从 $v$ 出发的最长链,B 的策略一定是沿这条链走 $h$ 步。假设 B 走到了 $u$,则 A 此时一定在 $u$ 的某棵存在“候选点”的子树中。

接下来 B 的策略有两种:

  • 往回走,即回到 $u$ 的父亲。
  • 往 $u$ 的某棵不存在“候选点”的子树中走。

然后找到最长的路径一直走即可。显然这个过程中 A 一定追不到 B。

考虑从 $v$ 出发的最长链一定是到直径的某个端点,所以我们可以分别以直径两个端点为根,上述过程可以简单的维护。

时间复杂度 $O((n+q)\log n)$。

新问题

题目来源:Romanian Master in Informatics 2020, Day 1, Task "Floppy".

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

算法 1

记录单调栈的弹出和压入。

算法 2

按先序遍历的顺序记录笛卡尔树的每个结点是否有左右儿子。

括号序列

题目来源:Romanian Master in Informatics 2021, Day 2, Task "NoM".

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

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

考虑容斥,设 $f_i$ 表示有序地选择 $i$ 个位置的有序对使得每对的下标之差均为 $M$ 的倍数的方案数,然后选择 $i$ 个括号放进这些位置,其他 $2(N-i)$ 个元素任意排列,所以答案为 $\displaystyle\sum_{i=0}^N(-1)^i(2N-2i)!\binom Nif_i$,而 $\displaystyle f_i=\left[\frac{z^i}{i!}\right]\prod_{j=0}^{M-1}\sum_{k=0}^{\lfloor n_j/2\rfloor}\frac{n_j!}{(n_j-2k)!}\cdot\frac{z^k}{k!}$,其中 $n_j$ 表示 $[1,2N]$ 中模 $M$ 的余数为 $j$ 的数的个数。

暴力计算多项式乘法,时间复杂度 $\mathcal O(N^2)$,若使用 FFT 计算则时间复杂度 $\mathcal O(N\log N)$。

子序列

题目来源:Petrozavodsk Winter 2022. Day 3. Kazakhstan Contest, Task G

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

解法一

by chenkuowen01

考虑先进行一次 $dp$,$f(i)$ 表示原数列中以 $i$ 为结尾的最长上升子序列长度。

$dp$ 转移大致为: $f(i)=\max_{j\lt i\land a_j\lt a_i} f(j)+1$

这部分可以采用树状数组优化,复杂度为 $\Theta(n \lg n)$

考虑一张 $n+2$ 个点(结点编号依次为 $0\cdots n+1$)的图 $G=(V,E)$ 以如下方式建边:

  1. 若$j\lt i,a_j\lt a_i,f(j)=f(i)-1$,则加一条边 $(j,i)$。
  2. 若$f(i)=1$,则加边 $(0,i)$。
  3. 若$f(i)$ 为最大值,则加边 $(i,n+1)$。

现在问题转化为要删去若干个结点,使得不存在合法的从$0$到$n+1$的路线

可以把问题转化为最小割模型,但显然使用最大流方法无法满足效率的要求。

这个图虽然不是平面图,但我们可以从平面图最小割得到一些启发。我们考虑按某种顺序依次截断从$0$到$n+1$的通路,尝试进行dp。

$g(i)$ 表示对于每个 $x$,不存在 $j(j\le i,f(j)=f(i))$使得存在 $j$ 到 $x$ 的路径或 $x$ 到 $j$ 的路径。不存在经过 $x$ 的通路的最少需要删除的点数。

令 $last(i)=\max_{(j,i)\in E} j$

$next(i)=\max_{(i,j)\in E} j$

$h(i)=\max_{j< i\land f(j)=f(i)} j$(没有则视为$-1$)

然后考虑转移:

对于 $0$ 和 $n+1$,这两个点不能删除,转移是显然的。

对于剩余的点转移有两种选择,一种是不删除,一种是删除。

对于不删除的情况,若原先就不存在经过这个点的通路,则可直接转移到 $h(i)$,即 $g(h(i))=\min(g(h(i)),g(i))$。

否则有两种情况,一种是去前面截断通路,一种是去后面截断通路,即:

$g(last(i))=\min(g(last(i)),g(i))$

$g(next(i))=\min(g(next(i)),g(i))$

对于删除的情况,转移只有一种:

$g(h(i))=\min(g(h(i)),g(i)+1)$

$g(-1)$ 即为答案。容易发现这个转移是有后效性的,所以可以转化为最短路模型。本题边权只有0和1,所以可以采用 01bfs(如果你不知道这个算法也可以采用 dijkstra)。

这部分复杂度为 $\Theta(n)$ 或 $\Theta(n\lg n)$ 。

所以整体的复杂度为 $\Theta(n\lg n)$

解法二

by hehezhou

往最小割的方向继续思考。

把每个点拆成入点和出点,并在之间连一条权值为 $1$ 的边,即可将模型转为最小割,即最大流。

这张图最大流的组合意义即为:最多能选出不交的最长上升子序列数量。

实际上,每次选择下标字典序最小的最长上升子序列并删去是正确的。

可以将图看作一个分层图,每层的点有序,并且每层每个点向下一层的一个区间连边,连边区间具有单调性,这和原问题是等价的。

记第 $i$ 层第 $j$ 个点为 $(i,j)$,则下标字典序最小的最长上升子序列等价于这样标号后,字典序最小的路径。

首先证明一个结论:存在一个最优方案,所有路径边不交,即不存在两条路径,分别存在 $(i,x_1)-(i+1,y_1)$ 和 $(i,x_2)-(i+1,y_2)$ 两条边,满足 $x_1\lt x_2$ 且 $y_1\gt y_2$。

否则可以将路径替换为 $(i,x_1)-(i+1,y_2)$ 和 $(i,x_2)-(i+1,y_1)$,后面的部分同样交换,由于出边区间的单调性,这样仍然合法,并且交点个数变少,不断重复即可得到一个不交的方案。

将路径按照字典序排序,每次考虑求出某个最优方案中字典序最小的路径。

直接挑选字典序最小的合法路径,这一定在某个最优方案中。

这是因为在这条路径上方(同层点中编号更小的)的点要么无法从起点到达,要么无法到达终点,是无用的点,可以删去。在删去这些点并重标号以后,这条路径就是 $(1,1)-(2,1)-(3,1)-\cdots$。

由于存在一个最优方案的路径不交,这个最优方案的所有路径至多有一条(即方案中字典序最小的)和找出的路径有交,将这个最优方案的第一条路径替换为找出的这条路径,仍然是一个合法的最优方案。

因此不断找出字典序最小的路径并删去,可以得到某个最优方案。

考虑怎样快速的进行这个过程:

首先求出每个点出边的左右端点,每次找路径使用 $\text{dfs}$ 算法。

$\text{dfs}(x,y)$ 需要尝试求出从 $(x,y)$ 出发的,只包含未被删去的点的,字典序最小的路径。

每层点删去的一定是一个前缀,因此可以 $O(1)$ 求出出边区间剩余的部分,并从小到大枚举,继续进行 $\text{dfs}$。

如果枚举完所有出边后,仍未找到一条合法路径,那么这个点无用(无法到达终点),可以被删去。如果此时同层上方有未被删去的点,说明这些点无法从起点到达,一并删去,保持了前缀的性质。

否则一路回溯就找到了一条路径,这个点同样会被删去。

因此每个点只会进行一次 $\text{dfs}$,并且所有点至多被 $\text{dfs}$ 内枚举一次,总复杂度 $O(n)$。

算上求最长上升子序列的部分,总复杂度 $O(n\log n)$。

平均分

题目来源:Petrozavodsk Winter 2022. Day 3. Kazakhstan Contest, Task H

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

我们形式化一下问题:分成三个组,和分别为 $x,y,z$,$x\le y\le z$,最小化 $z-x$。

考虑 meeting in the middle,两侧分别爆搜三个组,这部分复杂度为 $\Theta(3^{\lceil n/2\rceil})$。

设爆搜出来的一组方案三个和为 $x_0,y_0,z_0$,由于和是固定的,我们只需要保留一个二元组 $(x_0-z_0,y_0-z_0)$。

考虑左右合并的部分,对于一个左侧二元组 $(a,b)$ 和一个右侧二元组 $(x,y)$,能合并的条件为: $ a+x\le b+y\le 0$,最大化 $a+x$。

这是一个类似二维偏序的问题,可以排序后使用树状数组求解。

总复杂度 $\Theta(3^{\lceil n/2\rceil}\times n)$

Public Round #2 题解

2022-04-09 13:07:07 By cdw
  • 搬题人:
    • A, B:cdw
    • C:p_b_p_b
  • 组题人:cdw
  • 题解:cdwp_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$。

CCWG__6N6DN5HN`IIZT_1C7.png

推论 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$。

背包

题目来源:

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)$ 。

共 2 篇博客