Qingyu的博客

博客

Tags
None

Public CTS Round #1 题解

2023-01-07 10:16:08 By Qingyu
  • 组题人:Qingyu
  • 搬题人:
    • 黑白点:flower, Qingyu
    • 博弈:Qingyu
    • 地雷:flower, p_b_p_b
    • 桥桥桥:Qingyu
    • 游戏:Qingyu
    • 知识:alpha1022, Qingyu
  • 题解:flower, Qingyu, LeafSeek, alpha1022

黑白点

Source:

特别感谢 Xmas Contest 的举办者 hos_lyric 与本题的作者 maroonrk 允许我们使用本题并提供了测试数据。

算法1

枚举选手选点,状压dp即可。

时间复杂度$O(2^n n^3)$,可以通过$subtask 1$,期望得分$6$。

算法2

考虑枚举先手的选点 $rt$,考虑第 $1$ 次只能染黑一个点的操作是第 $i$ 次。 那么有机会染的点是 $dis(rt, u) \le i$ 的点 $u$。如果令 $cnt_i$ 表示距离 $rt$ 小于等于 $i$ 的点(不包括 $rt$)的数量。如果有 $2i - cnt_i \ge 1$,那么一定满足这个选这个点的时候只能选他一个点。

如果最后只剩一个白点,也显然只能选一个点。

更具体的说,考虑最少的选 $1$ 的次数。那么答案至少为 $\displaystyle \left\lfloor\frac{n+\max_{i=0}^{maxd}2i-cnt_i}{2}\right\rfloor$,其中 $maxd$ 为距离的最大值。

接下来是一个构造,可以达到上界: 先拎出来最短路树,变成树上的情况。如果一个边两个端点都为黑点,我们认为他的边权是 $0$,否则是 $1$。 每次找到 距离 $rt$ 最远的点 $u$,把 $rt$ 到 $u$ 路径上的第一个白点染黑,除此之外如果还可以染,选择距离 $rt$ 最远且不在 $u$ 所在的白点导出子图的连通块里的点 $v$,将 $rt$ 到 $v$ 的路径第一个白点染黑。

可以证明每次上述式子会减少 $1$,方法是考虑 $cnt_i \ge 2$ 的时候,这个位置一定不会成为 $\max$,所以没有被的选的白连通块虽然 $dis$ 没有减少 $1$,但是除了$dis$为全局最大值(因为满足距离 $rt$ 最远的点的太多了),其他点与其 $dis$ 相同的点至少有 $2$ 个,因此不会不会成为 $\max$。而没有被选的全局最大值,如果前面至少有一个 $cnt_i\ge 3$,那么也不会成为最大值,否则对应了最后只剩一个点的情况。

时间复杂度 $O(nm)$,可以通过 $subtask 1, 2$,期望得分:$16$。

算法3

考虑加速刚刚的过程。把刚刚的构造方法对应成,把 $rt$ 到距离 $rt$ 最远的点 $x$ 路径上除了 $rt$ 的每个点,和不在路径上的点匹配,要求每个点能和他的匹配的必须不在他的子树里。

这样在路径上没有匹配的点就是 必须一次只能染黑一个的点。

因为 $x$ 只可能是树直径端点之一,令其为 $p, q$。因此我们考虑对于所有的 $i$ 计算以 $i$ 为跟是如果距离最远点是 $p/q$ 的答案,取 $\max$ 即可。

不妨只考虑 $p$,把树变成以 $p$ 为根的有根树。令 $f_u$ 表示最少使用 $1$ 的数量(不考虑$u$子树内点),$size_u$ 表示 $u$ 子树大小。

计算答案需要把子树内的点考虑进去,这些点可以根 $u$ 到 $p$ 上任意一点匹配,因此有 $ans = \max(f_u - size_u - 1, 0)$。

转移也是同理,每次把在 $fa_u$ 子树里,不在 $u$子树里的点加入,这些点可以与除了$fa_u$ 和 $u$ 的所有点匹配。

因此做两边 树形dp 即可,时间复杂度$O(n)$,可以通过 $subtask 3$,期望得分:$18$。

算法4

与算法3类似,考虑如何特殊处理环的问题。因为需要把最短路树拎出来,所以需要在环上断边。

先把环拎出来后,$p$ 对应在环上的点设为 $x$,那么可能被断掉的是 $x$ 在环上连的两个边。预处理出前缀和后缀的size之和,直接转移即可。

时间复杂度 $O(n)$,可以通过 $subtask 3, 4$,期望得分:$31$。

算法5

算法4带来的启发是,每次经过一个环长为 $len$ 的环,至少会带来 $\left\lceil\frac{len}{2}\right\rceil -1$ 的点可以用来和当前所有路径上的点匹配,而路径长度最多增加 $\left\lfloor\frac{len}{2}\right\rfloor$。这里我们认为的情况是环上初始有一个黑点,而取到上述式子的情况就是只有一个环不挂其他点的情况。注意到这两个式子之差最多为 1。

考虑由环组成的一个点双,也满足两者之差最多为1。假设要从点双的 $x$ 走到 $y$, 于是可以不需要考虑 $x,y$ 最短路上除了 $y$ 的节点有没有匹配(一定有匹配)。而判断 $y$ 能不能匹配上等价于,以及能匹配多少 $y$ 之后的点。设这个点双里 $x,y$ 最短路径长度为 $w$,点数为 $s$,那么能匹配 $s - 1 - 2w$ 个点,上式为 $-1$表示 无法匹配 $y$。 同样的这里认为 $x$ 已经是黑点了。

因此考虑建立圆方树,将 $p$ 设为根。与上文唯一的不同是,这个点双里的点,可以连向其他没用的点双(向兄弟子树里连)。 注意到转移需要查询的最短路长度 $x, y$ 满足 $x$ 为圆方树上,方点的父亲节点,$y$ 为方点的儿子节点。因此是单源最短路的形式,可以把每个点双挖出来之后 bfs。

我们令 $p', q'$ 为圆方树上,将边权视为 $1$ 的直径。算法5中提到过,每个点双最多会使染色一个点的次数加$1$。那么考虑 $u$ 到 $p$ 和 $p'$ 的最短路树上 $lca$ 以后的部分。因为 $p$ 到 $lca$ 距离(也就是最多有多少点没匹配)小于等于 $lca$ 到 $p'$ 的点数,因此可以把这些点匹配过去,是足够的,所以 $lca$ 之后不会产生任何贡献。

时间复杂度 $O(n)$,可以通过所有数据,期望得分 $100$。

博弈

Source: Кубок трёх четвертьфиналов 2019. Subregional 1. Moscow.

注意到,对于给定的 $(x, T)$,若先手希望 $x$ 最终尽可能大,而后手希望 $x$ 最终尽可能小,则一轮后 $T$ 变为 $T - 2\varepsilon$,$x$ 变为 $x + \varepsilon$。最终,$x$ 将会停在 $x + \frac{T}{2}$。

我们首先考虑二分答案,这样问题就变为了,$[0, n]$ 被划分成了若干段,有一些段 Min 获胜,有一些段 Max 获胜,问最后会停在哪一段。注意到对于 Max 而言,如果有一段的长度大于了 $A$,我们直接停在这一段中 Max 便直接取胜。否则,每一段在 $x-T$ 坐标系上构成了一块三角形区域,每个三角形是某一方的必胜区域。

现在,考虑最靠下的一个三角形区域,由于其不交 $y = A$,因此在这一部分区域内的胜负态可以合并为一块大的区域,如果某策略试图停留在这段区域,则另一方总可以将其移动到边界处,因此,此处形如 ABA 的胜负区域可被等效替代为一胜负态为 A 的三角形区域,故我们可以直接合并这整个区域为一个大的等腰三角形。我们可以使用 std::set 来维护所有的三角形并维护胜负态。

时间复杂度为 $O(n \log n \log \epsilon^{-1})$。

地雷

本题加强自 Potyczki Algorytmiczne 2022, Runda 4 的 Miny [A]。

算法1

预处理出每个点能到达的点,每次 bitset 优化 bfs 即可。

时间复杂度 $O(\frac{n^3}{w}+n^2)$,可以通过 $subtask 1$,期望得分$9$。

算法2

建出点分树,每个点能到达的点是距离重心 $rt$ 的一个前缀,前缀和优化即可获得 $n$ 个点 $O(n \log n)$ 的图。

缩强连通后,用 bitset 优化即可。

时间复杂度 $O(\frac{n^2\log n}{w} + n^2)$,可以通过 $subtask 1, 2$,期望得分 $14$。

算法3

我们希望点分治后,能求出来每个跨过 $rt$ 的点对 $(u,v)$ 求出 $u$ 能不能炸到 $v$。

但问题是,有可能存在 $u$ 先炸到当前点分树子树外,获得了了一个巨大的半径,再炸回来炸到了 $v$。于是有可能出现点分树上只考虑 $lca(u, v)$ 的子树(下文子树均指代点分树上子树),无法从 $u$ 炸到 $v$,但是考虑 $lca(u, v)$ 的某些祖先的子树能炸过去的情况。

因此我们接下来有两个思路:

  1. 我们在 $rt$ 处理爆炸路径经过 $rt$ 的点对 $(u, v)$,这意味着 $(u, v)$ 可能在 $rt$ 为根的同一子树。
  2. 我们仍然在 $rt$ 处计算所有跨过$rt$ 的 $(u, v)$ 能不能到达,但是为此我们需要预处理处一些连通块外的信息。

对于第一种思路,这种想法意味着一个点对会被统计多次,最直观的想法是用 bitset 去重即可。

令 $f(rt, x)$ 表示从 $x$ 开始炸只考虑 $rt$ 子树内只炸到 $rt$,能给 $rt$ 炸到多少半径(就是炸到 $rt$ 之后半径的余量,也就是 $\max r_u - dis(u, rt)$,$x$能炸到 $u$),如果无法找到 $rt$ 为 $-1$,也就是说要么 $f(rt,x)=-1$,要么 $f(rt, x) \ge r_{rt}$。

令 $g(rt, x)$ 表示从 $rt$ 开始炸,只能在 $rt$ 子树里,初始至少有多少的半径能炸到 $x$。

如果 $u$ 能走到 $v$,那么有 $f(rt, x) \ge g(rt, y)$。

从下往上考虑点分树。求 $g(rt, x)$ 的方法是逐渐增大 $rt$ 的初始半径,考虑哪些点直接被 $rt$ 一下炸死。对于每个被一下炸死的点$x$,需要考虑他怎么炸别人。也就是说找到 $v$ 使得 $dis(u, v) \le r_u$。可以通过点分树的方法做到,就是对于每个重心 $rt$,求出每个点到他的距离的 dis,rank 并且按照 dis排序,可以在 $O(n\log^2 n)$ 的时间复杂度内做到。

求 $f(rt, x)$ 即 $\max r_u - dis(u, rt)$。因为是取 max,所以不担心重复计算,也就是可以考虑出,对于 $u$ 的每个 点分树上祖先$rt'$,$u$ 经过 $rt'$ 能到达的点 $v$ ,这些 $v$ 能炸到 $rt$ 的余量。因此只需要 对 $f, g$ 双指针时,维护 $g$ 的当前前缀,对$rt$ 在点分树上每个祖先的贡献。

考虑到 bitset 的 or 操作,每次只有 $rt$ 点分树大小的点可能是1,因此 bitset 下标变成 点分树的dfn序 之后是一个区间里可能会有1。手写 bitset ,每个点可以做到时间复杂度 $O(\frac{n}{w}+\frac{n}{2w}+\frac{n}{4w} \cdots)$。

如果 $w=1$,可以直接使用的bitset的count,时间复杂度 $O(\frac{n^2}{w})$,否则为 $O(n^2)$。可以通过 $subtask 3, 4$,期望得分 $31$。

算法4

对于第二种思路,我们需要修改定义为:

令 $f(rt, x)$ 表示从 $x$ 开设炸,可以炸到任意点,能给 $rt$ 炸到多少半径。

令 $g(rt, x)$ 表示从 $rt$ 开始炸,可以炸到任意点,初始至少有多少的半径能炸到 $x$。

我们在点分树上从上向下做,假设对于 $rt$ 的所有祖先,$f(rt, x), g(rt, x)$ 都已经求出。

对于$f(rt, x)$ 我们需要枚举从点分树$rt$子树外炸回来时,是从哪个点分树的祖先的炸出去的,假设为 $rt'$。那么已知 $f(rt', x)$,如果存在一个点 $y$ 满足 $g(rt', y) \le f(rt', x)$ 那么从 $x$ 炸出去能回到 $y$,$y$ 对$f(rt, x)$的贡献为 $r_y - dis(y, rt)$。也就是说处理出 $g$ 的一个前缀对 $rt$ 贡献的 max 即可。因为刚刚的情况是经过了 $y$ 中转的,注意特判从外面一步炸回 $rt$ 的情况。

对于$g(rt, x)$ 几乎类似,同样枚举是从哪个点分树祖先炸出去的,假设为 $rt'$。那么如果有 $f(rt',y) \ge g(rt', x)$,那么 $y$ 对 $rt$ 的贡献为 $dis(rt, y)$,同样双指针一遍即可。一样要特判从 $rt$ 一步炸到外面的情况。

对于全局的重心的 $f, g$,可以通过用 算法3 的方法处理出来。

需要精细实现,否则会多 $\log$。因为枚举 $rt, rt'$ 之后 如果双指针之前不能多 sort。我的处理方法是将点分树按层处理,每个点的点分树子树,被当前层的儿子们划分了。所以需要每个点预先排序好,每层的时候处理一下划分。

时间复杂度 $O(n\log^2 n)$,可以通过所有数据,期望得分 $100$。

桥桥桥

注意以下判定图联通性的方法:

  • 取出 $G$ 的任意一棵生成树 $T$
  • 对于所有非树边 $e$,随机一个 $[0, 2^{64})$ 内的权值 $w(e)$
  • 对于所有树边 $e$,定义其权值 $w(e)$ 为所有覆盖它的非树边的权值的异或和。

则我们可认为,删去 $E' \subseteq E$ 后图不联通等价于 $E'$ 存在子集 $F \subseteq E'$ 满足 $F$ 的边权异或和为 $0$。

首先,我们考虑所有删除一条边后图已经不联通的方案,这可以通过求出所有的桥边来得到。我们预先处理出这些边的方案,这一部分是容易的。接下来,我们假设不会选择这些边。

注意到,当我们假设一条边不能被选时,我们总是可以认为这条边一定在最终的图中,因此我们在这一步后,将图中所有桥边对应的两端点缩为同一个点,在这一步操作后,整张图将变为一张边双连通图。

其次,我们考虑,如果一个顶点 $x$ 的度数为 $2$(上述操作后,图中必定不会存在 $0$ 度点与 $1$ 度点),那么我们删去 $x$ 相连的两条边以及任意一条其他边,图一定变得不联通。我们同样算出这样的贡献并预先处理,随后我们便可以删去顶点 $x$。

在上述操作后,图变成了一张边双连通,且每个点度数 $\ge 3$ 的图。

此时,我们求出新图的一棵 DFS 树 $T'$,并考虑应用上述方法。注意到我们选择的三条边有以下四种情况:

  • 选择了 $0$ 条树边,$3$ 条非树边。
  • 选择了 $1$ 条树边,$2$ 条非树边。
  • 选择了 $2$ 条树边,$1$ 条非树边。
  • 选择了 $3$ 条树边,$0$ 条非树边。

首先,我们特判掉所有选择两条边后图一定不联通的方案,将这些方案特判掉。这是非常容易的,只需要找到所有 hash 值相等的边。

对于第一种情况,这样的方案一定不合法,因为 $T'$ 一定足以使得图联通。

对于第二种情况,我们枚举删去的树边,此时一定包含了至多两条跨过它的非树边,这样的情况是平凡的。

对于第三种情况,我们枚举删去的非树边,注意到特判掉所有两条边即合法的方案后,选择的两条树边必定呈祖先-后代关系,且选择的非树边为 $e_1, e_2$ 跨过边的差中唯一的边,这种情形仍然容易处理。例如,我们可以自底向上用并查集维护所有可行的链,并check每个对应的 $e_A$ 是否合法。

cts-2a.png

对于第四种情况,由于我们不会选择树边,因此我们可以缩掉所有的非树边,并在缩完非树边的图上接着做。由于图中每个点的度数至少为 $3$,因此 $|E| \geq \frac{3}{2} |V|$,故被缩掉的边数至少为 $|E| - |V| + 1 \ge \frac{1}{2}|V|$。在缩完边后,我们重新执行上述算法即可。由于缩边只会被缩 $O(\log m)$ 轮,因此总的时间复杂度可以保证。

游戏

Source:

算法一

首先,题意等价于可以删除任意长度大于 $1$ 的同色连续段。因此考虑将原串划分为极长同色连续段后,长为 $1$ 的记作 1,长度大于 $1$ 的记作 2,则原串转化为一个 12 串。

考虑操作对 12 串可能的影响,一次操作只可能影响到某个 2 对应的连续段:

  1. 如果不删空连续段,则这次操作可能会让这个 2 变为 12
  2. 否则连续段被删空,如果 2 处于开头或结尾,则 2 消失。
  3. 否则 2 处于中间,2 会被删除且前后的元素会被合并,即 ?2? 会被转化为 2

不难发现,2 优于 1,因而 1 操作不考虑。而 3 操作可以放到所有 2 操作结束后做。因此题意等价于给你一个 12 串,可以将 ?2? 转化为 2,问串能不能转化为全 2。进一步的,串能不能转化为 $1$ 或 $2$ 个 2,取决于初始串长。

由于任意时刻,串中的每个字符都对应了原串中某个长为奇数的区间。若 12 串的长为偶数,则考虑最后剩下两个 2 对应的区间,这个串可以被删空等价于可以将串划为两个长为奇数的部分,两个部分分别可以被删空。

因此我们只需考虑串长为 $2k+1$ 的情况,一个简单的情况是第 $k+1$ 位为 2,此时只需将两边不断删除即可。若第 $k+1$ 位不是 2,一个直观的想法是找到左右最近的两个 2,然后删除中间部分同时调整两侧长度,将问题转化为 $k+1$ 位为 2 的情况,例如 11211211111 首先调整为 1122111,然后变为 11211,即简单的情况。可以发现按照这个思路,原串可以被合并至 2 等价于两侧最近的 2 中间不包含超过 $k$ 个 1。而对于包含超过 $k$ 个 1 的情况,由于一次操作最多消除一个 1,且头尾一定会剩下 2,序列会转化为 21(...1)2,显然无解。

对于奇数情况的判断是简单的,对于偶数情况寻找划分点也可以做到线性,因此总复杂度为 $O(n)$。

算法二

by LeafSeek

称能被删空的串合法,否则不合法。关键结论:串 $S\texttt{AA}T$ 合法当且仅当 $ST$ 合法或 $S\texttt{A}T$ 合法。

首先证明如果 $S\texttt{A}T$ 合法,那么 $S\texttt{AA}T$ 一定合法。考虑消除中间 $\texttt{A}$ 的那一步,如果删了 $2$ 个就改成 $3$ 个,删了 $3$ 个就改成 $4$ 个(分两步各删 $2$ 个)。实际上容易说明连续任意 $\geq2$ 个相同字符均可被消除。

然后证明如果 $S\texttt{AA}T$ 合法,那么要么 $ST$ 合法,要么 $S\texttt{A}T$ 合法。首先注意到中间的两个 $\texttt{A}$ 一定是一起被消的。如果是分别被消的,和这两个 $\texttt{A}$ 相匹配的两边各还要有至少 $1$ 个 $\texttt{A}$,一共是 $\geq2$ 个,可以让这 $\geq2$ 个自己消除,将中间的两个 $\texttt{A}$ 调整成一步删 $2$ 个的操作。考虑它们一起被消的那一步,如果是删了 $2$ 个的情况可归入 $ST$,删了 $3$ 个的情况则可归入 $S\texttt{A}T$。

考虑这么一个过程:对于一个串 $S$,每次找到 $S$ 中最靠前的 $\texttt{AA}$ 或 $\texttt{BB}$,你需要决定将 $\texttt{AA}$ 变成空还是变成 $\texttt{A}$。那么 $S$ 能删空当且仅当存在一种决定方式,使得最后得到空串。

不妨设原串 $=S\texttt{A}$,考虑任一种合法的决定方式(不一定要最后删空),一定是先决定 $S$ 里面的东西,之后再决定最后一个 $\texttt{A}$。决定完 $S$ 里面的东西剩下的结果一定是 $\texttt{AB}$ 交替的,根据其首尾分别是 $\texttt{A}$ 还是 $\texttt{B}$ 可以分为 $4$ 类。

所以可以动态规划,我们用首尾和长度表示一个 $\texttt{AB}$ 交替的串。考虑转移,每次加入一个字符,维护当前串可以被删成的 $\texttt{AB}$ 交替串的集合。比如说 $\texttt{ABABA}$,加入 $\texttt{A}$ 之后可以变成 $\texttt{ABAB}$ 或者 $\texttt{ABABA}$ 中的一种;又比如 $\texttt{ABAB}$,加入 $\texttt{A}$ 之后只能变成 $\texttt{ABABA}$。必须特殊考虑空串,空串不属于 $4$ 类中的任何一类。直接维护这个集合即可做到 $\mathcal{O}(\dfrac{n^2}w)$。

接下来是未经证明的猜测:串 $S$ 能删成的结果,在确定了首尾之后,其可行长度的取值范围一定是一段区间。这里区间指的是 $[L,R]$ 内所有奇偶性与 $L$ 相同的整数。比赛的时候对拍观察动态规划中集合的模样可以做出上述猜测。于是只需维护能否删空、$4$ 个区间存不存在以及其左右端点,容易做到 $\mathcal{O}(n)$。

还原方案也可以做到 $\mathcal{O}(n)$:先回溯转移的过程,维护一个栈,确定每个字符是新弹入栈中还是与栈顶消除。对每个字符,开一个 $\texttt{vector}$ 保存它作为栈顶负责消除的字符的下标,包括 $\texttt{A(A)}$ 变 $\texttt{A}$ 和 $\texttt{BA(A)}$ 变 $\texttt{B}$ 两种情况。可以看出每个 $\texttt{vector}$ 的大小都 $\geq2$。最后直接 $\text{Dfs}$ 即可还原出方案。

知识

Source:

特别感谢 Xmas Contest 的举办者 hos_lyric 与本题的作者 maroonrk 允许我们使用本题并提供了测试数据。

先来考虑对于给定的一个点数为 $N$ 的有向图 $G$ 如何计算其各个点为根的外向生成树权值和。

定义 Laplacian 矩阵

$$ L_{ij} = \begin{cases} \sum_{(k,i) \in E} w_{ki}, & i=j \\ -w_{ij}, & (i,j) \in E \\ 0, & \text{otherwise} \end{cases} $$

根据 Matrix-Tree 定理,以 $u$ 为根的外向生成树权值和即为 $L_{uu}$ 处的主余子式。 也就是说,我们需要计算 $L$ 的伴随矩阵 $L^*$ 的对角线。

注意到 Laplacian 矩阵并不满秩,因此其伴随矩阵的秩不超过 $1$。因此,存在列向量 $x,y$ 使得其伴随矩阵 $L^* = xy^{\mathsf T}$。

而注意到 $L$ 所有行向量之和为全 $0$ 向量,从而可以证明其同一列的所有代数余子式相等,因此 $L^*$ 的各列向量相等,$y$ 可以取全 $1$ 向量。

那么,我们只需要算出 $x$ 即可获得对角线上的值。

而根据 $AA^* = |A| I$,可知 $L x y^{\mathsf T} = 0$,也就是 $L x=0$。据此,我们可以解出一个非平凡的 $x$,但其与真正的 $x$ 相差常数倍。

幸运的是,这是容易处理的。我们只需要取一个非 $0$ 的位置计算出对应的余子式即可。

而题意中给出的就是两张图的 Cartesian 积。不妨记作 $G = G_1 \mathop\square G_2$。
为了刻画其 Laplacian 矩阵,我们引入 Kronecker 积

$$ A \otimes B = \begin{bmatrix} a_{11} B & a_{12} B & \cdots & a_{1m} B \\ a_{21} B & a_{22} B & \cdots & a_{2m} B \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} B & a_{n2} B & \cdots & a_{nm} B \end{bmatrix} $$

其中 $A$ 是 $n\times m$ 矩阵。

令 $L^{(1)},L^{(2)}$ 分别为 $G_1, G_2$ 的 Laplacian 矩阵,易得 $G_1 \mathop\square G_2$ 的 Laplacian 矩阵为 $L = L^{(1)} \otimes I_N + I_M \otimes L^{(2)}$。

接下来,我们注意到,若我们对 $L^{(1)}, L^{(2)}$ 求出了各自的 $x^{(1)}, x^{(2)}$,则有 $L (x^{(1)} \otimes x^{(2)})=0$。因此我们也只需要定出相差的系数即可。

我们考虑通过其和,也就是伴随矩阵的迹来定出这个系数。

设 $L^{(1)}, L^{(2)}$ 有特征值 $\lambda_1, \lambda_2, \dots, \lambda_M$ 和 $\mu_1, \mu_2, \dots, \mu_N$,则 $x^{(1)}, x^{(2)}$ 的和即为 $L^{(1)}, L^{(2)}$ 的特征多项式的 $1$ 次项系数乘 $(-1)^{M-1}$ 和 $(-1)^{N-1}$。

注意到 $L^{(1)}, L^{(2)}$ 必有 $0$ 这个特征值,不妨设 $\lambda_1 = \mu_1 = 0$,则这个值就是 $\lambda_2 \lambda_3 \cdots \lambda_M$ 和 $\mu_2 \mu_3 \cdots \mu_N$。

因此 $x^{(1)} \otimes x^{(2)}$ 的和即为 $\lambda_2 \lambda_3 \cdots \lambda_M \mu_2 \mu_3 \cdots \mu_N$。

而可以证明,$L$ 的特征值为 $\lambda_i + \mu_j$ $(i=1,2,\dots,M, j=1,2,\dots,N)$(证明见 [1])。因此,相差的系数即为 $$ \prod_{i=2}^M \prod_{j=2}^N (\lambda_i + \mu_j) $$

而我们知道特征值是特征多项式的根,因此我们借助 Resultant,可以得到这个乘积的值为 $\operatorname{res}\left(\frac{|tI-L^{(1)}|}t, \frac{|tI+L^{(2)}|}t\right)$。

而对于 Resultant 的计算,由于这部分并非瓶颈,可以直接 $O((N+M)^3)$ 计算行列式。

事实上,根据 wiki 上的结论,我们可以用多项式 Euclid 实现其求算。暴力实现就是 $O(NM)$ 的。 然而 wiki 上的结论疑似有误,其算法具体实现可以参考 std。

[1] 潘佳奇,浅谈线性代数与图论的关系,IOI 2021 中国国家集训队论文

QOJ 更新日志

2023-01-06 20:27:29 By Qingyu

01/09/2023

更新编译器信息如下:

  • Python2: Python 2.7.18
  • Python3: Python 3.10.9
  • C/C99/C11/C++/C++98/C++11/C++14/C++17/C++20/C++23: GCC 11.1.0
  • Java 8/Java 11: openjdk version "11.0.16"
  • Pascal: fpc 3.0.4+dfsg-23

01/05/2023

由于 QOJ 遇到了一些问题,于今日回滚至 2023/01/04 的备份。

所有发生在 2023/01/04 12:00(UTC +8)至 2023/01/05 18:00(UTC +8)的数据变更均被丢失,为带来的不便感到抱歉。

Public CTS Round #1 公告

2023-01-02 23:12:06 By Qingyu

万能的 p_b_p_b 说:要有 CTS Round,于是 pjudge 有了 CTS Round。

大家 2023 年新年快乐!作为 pjudge 在 2023 年复活后的第一场比赛,Public CTS Round #1 将在 2023 年 1 月 7 日与 1 月 8 日 8:30 举行!

比赛将分为两日进行,每场比赛时间为当日上午 08:30 至 13:30,共 5 小时。每场比赛均为 IOI 赛制,且包含三道题目。

本次比赛的题目难度可参考 CTS 2022。 比赛的组题人为 p_b_p_bQingyu,搬题人为 alpha1022, flower, hehezhou, p_b_p_b, Qingyu

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public NOIP Round #4 题解

2022-11-20 15:28:33 By Qingyu
  • 搬题人:
    • 咖啡, 画图:Qingyu
    • 治病, 拓扑序计数:feecle6418
    • 序列:Wu_Ren
    • 水果:p_b_p_b
  • 组题人:Qingyu
  • 题解:alpha1022, feecle6418, Wu_Ren, p_b_p_b

咖啡 (Div. 2 Only)

来源:

Tutorial by alpha1022.

不妨采用贪心策略:能喝则喝。

从左往右扫描,维护当前手中有几杯咖啡即可。

画图 (Div. 2 Only)

来源:

Tutorial by alpha1022.

采用深度优先搜索或广度优先搜索得出 $(x,y)$ 所在的连通块并染色即可,需要保证每个格子不被重复访问。

治病 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

首先我们要算出,如果不忽略任何医生,尼特花费的钱数。根据题意我们知道,对于某种药片,尼特吃这种药片的时间就是所有医生药方里的时间的并集,也就是给出一些区间让你求并。这是经典问题,按照左端点从小到大排序,维护当前最大的右端点即可。

如果忽略某个医生,只需要找到只被这一个医生覆盖的 (药片,时间) 二元组,把这些二元组的贡献减掉。对每种药片分开考虑,也就是对每个区间,求出只被这一个区间覆盖的位置的总长度。首先用差分求出每个位置被覆盖了多少次,找出只被覆盖一次的位置,把这些位置的权值赋值成 1,对权值做前缀和,然后求出每个区间内的位置的权值之和,就是只被这一个区间覆盖的位置的总长度。

所有差分、前缀和都需要在离散化之后的坐标上进行,瓶颈在于离散化,总时间复杂度为 $O((\sum K)\log (\sum K)+n+m)$。

拓扑序计数 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

设 $f(S)$ 表示按照拓扑序从前往后的顺序加点,初始为空集,到已经加入 $S$ 这个点集,这一段的加点方案数。设 $g(S)$ 表示按照拓扑序从后往前的顺序删点,初始为全集,到现在还剩下 $S$ 这个点集,此时删除顺序的方案数。$f,g$ 都可以在 $O(2^nn)$ 时间内简单地 dp 求出。

对于给定的 $u,v$,$u$ 在 $v$ 前,就是要,拓扑序加入 $v$ 那一刻,$u$ 已经在拓扑序里了。所以,$ans_{u,v}=\sum [u\in S,v\notin S]f(S)g(S\cup \{v\})$(枚举加入 $v$ 之前一刻,有哪些点加入了拓扑序)

直接实现该算法的时间复杂度为 $O(2^nn^2)$,但 $S$ 的枚举有 $1/4$ 的常数,已经可以过。

当然,上述算法还可以继续优化到 $O(2^nn)$:枚举 $S,v$,相当于 $\forall u\in S$,$ans_{u,v}$ 都加上一个定值。因此瓶颈在于:“给出 $a_{0}\sim a_{2^n-1}$,对所有 $u$ 求出 $\sum_{u\in S}a_S$”。可以用下面的方法:

for i from n-1 downto 0:
    for j from 2^i to (2^{i+1}-1):
        ans[i]+=a[j]
        a[j-2^i]+=a[j]

最后 $ans_u$ 就是答案。因此我们把 $O(2^nn)$ 的循环优化到了 $O(2^n)$。(但是实际上速度仅仅变快了不到一倍)

序列 (Div. 1 Only)

来源:

Tutorial by Wu_Ren.

由于答案有可二分性,直接获得 $O(nm\log n)$ 做法。

下面是正解:

考虑每次建出小根笛卡尔树,并且在笛卡尔树上 dp

我们对于每个节点,维护子树内 $a_i$ 最大值 $mx$,区间长度 $sz$,最长合法子段长度 $len$。

假设 $u$ 的两个儿子为 $lc,rc$,那么考虑合并 $lc,rc$ 的信息来得到 $u$ 的信息。

$mx,sz$ 的合并是显然的。考虑 $len$ 的合并,首先,假如合法子段不经过 $u$,那么就是 $len_u\leftarrow \max(len_{lc},len_{rc})$。假设存在 $u\in[l,r]$ 使得 $[l,r]$ 是合法子段,那么假设 $\max\limits_{i\in[l,u-1]} \{a_i\}\ge \max\limits_{i\in[u+1,r]} \{a_i\}$,此时我们可以发现,如果 $l>u-sz_{lc}\land r>u$,那么 $[l-1,r-1]$ 也是合法的。

那么就可以知道,我们可以认为跨越 $u$ 的合法子段要么一个端点是 $u$,要么一个端点是 $u-sz_{lc}$ 或 $u+sz_{rc}$。

这里可以发现,假如 $[l,u]$ 是合法子段且 $l>u-sz_{lc}$,那么 $[l-1,u-1]$ 也是合法子段,所以说一个端点是 $u$ 且另一个端点不是 $u-sz_{lc}$ 或 $u+sz_{rc}$ 的情况一定不优于 $\max(len_{lc},len_{rc})$。

那么我们只需要考虑一个端点在 $u-sz_{lc}$ 或 $u+sz_{rc}$,并且过 $u$ 的情况了(也就是说,我们只需要考虑至少把一颗子树完全包含的情况),这个转移是显然的。

复杂度 $O(nm)$。

水果 (Div. 1 Only)

来源:

Tutorial by p_b_p_b.

为了方便,先把 $a_i\ne -1$ 且无论如何都无法成为前缀最大值的水果删掉。

为了方便,再把水果的美味度修改一下,使得没有确定位置的水果的美味度是 $1,2,\cdots,m$ ,而确定位置的水果的美味度则是夹在中间的小数。

设 $a_1,\cdots,a_n$ 是读入的方案,$A_1,\cdots,A_n$ 是最终的方案。

放弃思考,直接设 $dp_{x,v}$ 表示确定了 $A_1,\cdots,A_x$ ,且其中最大值小于 $v+0.99$ ($v$ 是整数),考虑如何转移。

  • 如果 $a_x\ne -1$ ,那么有两种选择
    • 让 $a_x$ 成为最终的前缀最大值,那么从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移。
    • 扔掉 $a_x$ ,从 $dp_{x-1,v}$ 转移。
  • 如果 $a_x=-1$ ,再分两种
    • $a_1,\cdots,a_{x-1}$ 的最大值小于 $v$ ,那么这里肯定应该贪心放 $v$ ,从 $dp_{x-1,v-1}+c_v$ 转移。
    • 否则这里只能被迫开摆,随便放个以后不用的小的,从 $dp_{x-1,v}$ 转移。(注意因为我们做过预处理,所以这里总是可以保证不超过 $v$ 。)

于是就获得了一个非常垃圾 $O(n^2)$ 做法,下面考虑优化。

  • 对于 $a_x\ne -1$ ,注意到 $dp_{x,0},\cdots,dp_{x,m}$ 单调不降,因此一定是一个前缀从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移,而其他地方直接把 $dp_{x-1,v}$ 拉过来。因此只要二分分界点就可以直接前缀赋值。
  • 对于 $a_x=-1$ ,显然只有一个合法状态会从 $dp_{x-1,v}$ 转移,剩下的都从 $dp_{x-1,v-1}+c_v$ 转移。不过这个怎么维护呢?

设 $S_i=\sum_{j=1}^i c_j$ 表示 $c$ 的前缀和。另外设 $pre_x$ 表示 $a_1,\cdots,a_x$ 有几个 $-1$ 。

对每个 $dp_{x,v}$ 维护一个二元组 $f_{x,v}=(x',y)$ ,表示 $dp_{x,v}=S_v-S_{v-(pre_x-x')}+y$ ,那么就做完了:从 $dp_{x-1,v-1}+c_v$ 转移,就等价于 $f_{x,v}=f_{x-1,v-1}$ 。而其他转移也都是简单的单点或区间赋值。

暴力线段树就能维护了。还可以再好看一点,用双端队列来维护二元组的连续段,但其实区别不大。

Public NOIP Round #4 公告

2022-11-13 02:21:21 By Qingyu

Public NOIP Round #4 将在 2022 年 11 月 20 日 8:30 举行!

比赛分为普及组和提高组,普及组进行 3.5 小时,提高组进行 4.5 小时。普及和提高分别有 4 道题,OI 赛制,其中普及组和提高组有两题相同。

与上一次比赛相同的是,本次比赛将与 MarsOJ 合作。pjudge 上仍然会有常规模式的比赛,而 MarsOJ 则可以提供仿真 csp/noip 考场环境的云电脑,具体可以加入用户群(915426363)。 选手可以根据自己的训练需要来自由选择在 pjudge 或 MarsOJ 参赛。两边都是免费的。

本次比赛的题目难度约为 CSP-J / noip ,所有题目都有部分分。

本次模拟赛的组题人为 Qingyu ,搬题人为 Qingyu, Wu_Ren, p_b_p_b, feecle6418

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public NOIP Round #3 题解

2022-10-22 14:38:11 By Qingyu
  • 搬题人:
    • 数字:gyh20
    • 因子:Wu_Ren
    • 移除石子:feecle6418
    • 抓内鬼:p_b_p_b
    • 异或序列:feecle6418
    • 数圈圈:feecle6418
  • 组题人:hehezhou
  • 题解:gyh20, Wu_Ren, feecle6418, p_b_p_b

数字 (Div. 2 Only)

来源:AtCoder Beginner Contest 182 (https://atcoder.jp/contests/abc182/tasks/abc182_c)

Tutorial by gyh20.

做法 $1$:

直接搜索每一位是否删掉,时间复杂度可以做到 $2^{\log n}\log n$ 或者 $2^{\log n}$,这里的 $\log$ 是以 $10$ 为底的,可以通过。

Submission #56492 - Public Judge (pjudge.ac)

做法 $2$:

我们知道,一个数字能被 $3$ 整除,当且仅当其所有数位之和是 $3$ 的倍数,所以我们一定不会删数位是 $3$ 的倍数的这些位,同时也不会删三个 $\bmod 3$ 相同的位,同时也不会同时删 $\bmod 3=1$ 的和 $\bmod 3=2$ 的,这样我们就知道答案不超过 $2$。

于是求出所有数位上有多少个 $\bmod 3=1$,多少个 $\bmod 3=2$,分类讨论一下即可。

Submission #56801 - Public Judge (pjudge.ac)

因子 (Div. 2 Only)

来源:

  • Petrozavodsk Summer 2020. Day 5: JAG Summer+ Opening Contest. Problem B. Non-Trivial Common Divisor
  • ACM-ICPC Japan Alumni Group Summer Camp 2019. Problem B. Non-Trivial Common Divisor
  • https://qoj.ac/contest/505/problem/1336

Tutorial by Wu_Ren.

容易知道 $k$ 取某个质数最优,开个桶统计每个质数的答案即可,复杂度 $O(\sum \sqrt{a_i}+\omega (a_i))$。

移除石子 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

算法一

对于前三个测试点,可以从左往右删,第 $i$ 次输出 $(4i,4i,4i-2,4i-2)$。

对于第四、五个测试点,可以从下往上删,按照纵坐标顺序,第 $i$ 次删掉排在第 $2i-1$ 位、第 $2i$ 位的点即可。

结合起来期望得分 $50$。

算法二

大胆猜想一定有解。

算法一中的讨论指引我们从边上开始删。

将所有点按照横坐标从小到大排序,相同的按照纵坐标从小到大排序。不妨在该顺序中从后往前删。设在该顺序下,最后一个点为 $X$,倒数第二个点为 $Y$,倒数第三个点为 $Z$。

但是不一定合法,我们分类讨论几种情况:

  1. $X,Y$ 都是横坐标最大的点,这时靠右放个正方形,可以删掉 $X,Y$。

  2. 横坐标最大的点只有 $X$。

    1. $Y$ 的纵坐标小于或等于 $X$ 的纵坐标,则放一个以 $Y$ 为左下顶点的很大的正方形。

    2. $Y$ 的纵坐标大于 $X$ 的纵坐标。

      1. $Z$ 的横坐标等于 $Y$ 的横坐标,$Z$ 的纵坐标大于 $X$ 的纵坐标。

        这时以 $YZ$ 为一边放一个正方形就可以删掉 $Y,Z$:

      2. $Z$ 的横坐标等于 $Y$ 的横坐标,$Z$ 的纵坐标恰好等于 $X$ 的横坐标。

        这时以 $YZ,ZX$ 中短的一边作为正方形的一条边,比如下图中 $YZ\le ZX$,就这样画:

        注意,为了防止 $YZ=ZX$ 时把 $XYZ$ 三个点恰好都框住,需要把正方形偏移 0.5 个单位,这也是题目允许输出小数的原因。

      3. 不是以上两种情况,则以 $(x_Y,y_X)$ 为左下角作一个很大的正方形即可:

瓶颈在于排序,时间复杂度为 $O(n\log n)$,期望得分 $100$。

如果某些情况讨论漏了,可以得到 $90$ 分,因为数据随机时很难覆盖所有情况。

抓内鬼 (Div. 1 + Div. 2)

来源:

  • Noric Collegiate Programming Contest 2021. Problem C. Customs Control
  • Petrozavodsk Winter 2022. Day 4: Almost Northern Contest. Problem C. Customs Control
  • https://qoj.ac/contest/822/problem/1774

Tutorial by p_b_p_b.

算法一

$k=1$ 。

不难想到一个简单策略是只在点 $1$ 处放一个 uoj 壮丁,其他地方都放 pjudge 壮丁。这种策略只会在 $1$ 和 $n$ 有边时失败,但此时唯一的最短路就是从 $1$ 一步走到 $n$ ,因此只要 $n\ge 3$ 就可以在 $1,n$ 都放 pjudge 壮丁,就解决了。

算法二

$u_i\in \{1,n\}$ 或 $v_i\in \{1,n\}$ 。

同样先特判掉 $1,n$ 有边的情况,然后不难发现只要给 $1$ 和 $n$ 分配不同来源的壮丁,剩下的点随便分,就一定可以掐断所有路线。或者如果 $k=0$ 或 $k=n$ 也是显然有解的。

算法三

一般情况。

沿用算法二,先给 $1,n$ 分配不同来源的壮丁,不妨假设 $1$ 的壮丁是 P 而 $n$ 的壮丁是 U 。

可以发现,如果存在边 $(1,x)$ ,并且 $x$ 的壮丁也是 P ,那就相当于把 $x$ 从图里删掉了。这是因为从 $1$ 不能一步走到 $x$ ,而其他拐一个弯再到 $x$ 的走法不可能是最短路。存在边 $(y,n)$ 且 $y$ 的壮丁是 U 的情况同理。

因此只需要把 pjudge 壮丁贪心分配给 $1$ 旁边的点。那么要么是把 $1$ 旁边的点都删完了,要么是剩下的 uoj 壮丁可以把 $n$ 旁边的点删完。总之 $1$ 和 $n$ 肯定有一个是周围的点被删完了。

异或序列 (Div. 1 Only)

来源:

  • Petrozavodsk Winter 2021. Day 8: Belarusian SU Contest, Yandex Cup 2021. Problem C. Brave Seekers of Unicorns
  • XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem C. Brave Seekers of Unicorns
  • https://qoj.ac/contest/536/problem/1085

Tutorial by feecle6418.

算法一

从小到大加入数来 dp。暴力一点,既然要求连续三个的异或和不为 $0$,就记录序列的最后两个位置 $x,y$ 分别是什么,加入 $z$ 的时候要求 $x,y,z$ 异或和不为 $0$。

时间复杂度 $O(n^3)$,期望得分 $40$ 分。

算法二

注意到性质:如果连续三个位置 $a_i,a_{i+1},a_{i+2}$ 违反了题目的限制,那 $(a_{i-1},a_i,a_{i+1})$ 就不可能违反限制了。

设 $f(n)$ 表示以 $n$ 结尾有多少个合法的序列。使用容斥:$f(n)=1+\sum _{i < n}f(i)-C$,$C$ 是在 $n$ 处第一次违反限制的序列数。$C$ 怎么算?如果一个序列 $[\dots,x,y,n]$ 在 $(x,y,n)$ 第一次违反限制,枚举 $y$,如果 $x=(y\operatorname{xor}n) < y$,$C$ 就应该加上 $f(x)$。

时间复杂度 $O(n^2)$,期望得分 $60$ 分。

算法三

对于 $\sum_{i < n}f(i)$ 这部分,可以用前缀和优化。

对于 $C=\sum_{y < n}[(y\operatorname{xor}n) < y]f(y\operatorname{xor}n)$,考虑满足条件的 $y$ 有何性质:实际上只要 $y$ 的二进制最高位和 $n$ 相同就有 $(y\operatorname{xor}n) < y$ 了。此时,枚举最高在哪一位 $y$ 和 $n$ 不同,则比这一位低的位可以任取,这样 $(y\operatorname{xor}n)$ 就属于一段特定的区间。因此我们把上述求和拆成了 $O(\log n)$ 段区间求和,同样可以前缀和。

时间复杂度 $O(n\log n)$,期望得分 $100$ 分。

数圈圈 (Div. 1 Only)

来源:

  • Petrozavodsk Winter 2021. Day 8: Belarusian SU Contest, Yandex Cup 2021. Problem F. Border Similarity Undertaking
  • XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem F. Border Similarity Undertaking
  • https://qoj.ac/contest/536/problem/1088

Tutorial by feecle6418.

算法一

枚举每种情况,再暴力判断条件是否满足。

可通过子任务 $1$,期望得分 $5$。

算法二

预处理从 $x$ 开始往右、往下最长的一段连续相同字符,再暴力枚举,这时可以 $O(1)$ 判断了。

时间复杂度 $O(n^2m^2)$,可通过子任务 $1,2$,期望得分 $15$。

算法三

子任务 $3$ 中,只需要求有多少个矩形,这很容易 $O(1)$ 计算。

子任务 $4$ 中,注意圈的大小肯定不大,因此小范围内枚举即可。结合前述期望得分 $40$。

算法四

考虑对矩阵分治,每次选择长的一边割开,然后计算经过中线(中线长度等于短的一边长度)的“圈”数量。不妨假设是竖着切的。

在下图中,我们对每一对 $(u,v)$ 求出左边的 匚 和右边对称的形状数量,最终乘起来即可。因为两边是对称的,下面就只描述怎么求 匚 数量了。

设 $L_u$ 表示 $u$ 往左,相同字符至多能延伸到第几列;$D_{x,y}$ 表示 $(x,y)$ 往下,相同字符至多能延伸到第几行。则我们要求的是 $$ \sum_{i=\max(L_u,L_v)}^{mid} [D_{i,u}\ge v] $$ 若 $L_u\ge L_v$,就是求: $$ \sum_{i=L_u}^{mid} [D_{i,u}\ge v] $$ 因为 $L_u$ 是固定的,所以这里可以用一个桶存下所有的 $D_{i,u}$,做个后缀和就可以 $O(1)$ 求出了。

否则,我们发现 $[D_{i,u}\ge v]$ 等价于 $[U_{i,v}\le u]$($U$ 表示向上延伸最远能到第几行),所以做法是一样的。

时间复杂度 $O(nm\log nm)$,因为递归有 $\log nm$ 层,设短边长 $x$ 长边长 $y$,每层用 $x^2+xy\le 2xy$ 也即 $O(xy)$ 的时间处理了询问,加起来每层是 $O(nm)$。可以通过本题得到 $100$ 分。

当然,如果固定 $u$ 将 $\{D_{i,u}\}$ 看成一个序列,上面就是问序列的某个后缀里有几个数 $\ge x$,用树状数组容易优化到 $O(\log n)$ 单次询问。时间复杂度 $O(nm(\log nm)^2)$。也可以通过本题得到 $100$ 分。

Public NOIP Round #2 题解

2022-10-04 13:34:02 By Qingyu
  • 搬题人:
    • 就这:Y25t
    • 保序回归问题:Y25t
    • 恰钱:skip2004
    • 排序:Wu_Ren
    • 图同构:hehezhou
    • 找零:p_b_p_b
  • 组题人:p_b_p_b
  • 题解:p_b_p_b, Wu_Ren, Y25t, nantf

就这 (Div. 2 Only)

来源:

  • 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem A. Constructiveforces
  • Кубок Трёх Четвертьфиналов 2021. Problem A. Constructiveforces

Tutorial by Y25t

其实只用保证每个长为 $m$ 的子串中恰好有 $k$ 个 1 就合法了,一种简单的构造是:

for(int i=0;i<n;i++) std::cout<<(i%m<k);

保序回归问题 (Div. 2 Only)

来源:

  • 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem E. Positive Thinking
  • Кубок Трёх Четвертьфиналов 2021. Problem E. Positive Thinking

Tutorial by Y25t

当 $\prod y_i> 0$ 时,取 $x_i=y_i$,答案为 $0$。

当 $\prod y_i= 0$ 时,设 $\{y_i\}$ 中 $0$ 的个数为 $c$,那么至少要 $c$ 的代价才能使乘积非 $0$。而先把 $c-1$ 个 $0$ 变成 $1$,然后剩下那个 $0$ 根据情况变为 $1$ 或 $-1$ 即可取到这个下界。

当 $\prod y_i< 0$ 时,考虑 $\{y_i\}$ 中绝对值最小的位置,不妨设为 $j$。当 $y_j> 0$ 时将其变为 $-1$,否则将其变为 $1$,这样能使 $\prod y_i$ 反号,花费代价为 $|y_j|+1$,容易证明这是下界。

这些情况均可线性判断。

恰钱:(Div. 1 + Div. 2)

来源:

  • The 2022 ICPC Asia Regionals Online Contest (I)

Tutorial by p_b_p_b

如果你会数位 dp 那么可以直接往里套,显然是能做的。

否则,你也可以毛估估一下:

  • 当 $\text{ctz}(x)\le 5$ 时 $\text{ppc}(x)$ 也很小,这样只会有 $O((\log r)^4)$ 个合法的 $x$ 。
  • 否则这样的 $x$ 只有 $r/2^5$ 个,也不会太多,把合法的留下就更少了。

所以可以写个爆搜得到所有合法的 $x$ ,然后每次询问时二分。爆搜只需要 dfs+剪枝 即可。

最后,你也可以每次询问时枚举 $\text{ctz}(x)$ ,然后进行一些神秘贪心或调整,也可以通过此题。

排序:(Div. 1 + Div. 2)

来源:

  • Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest. Problem C. StalinSort Algorithm

链接:https://qoj.ac/problem/1456

tutorial by Wu_Ren

考虑 dp,设 $f_i$ 为当前子序列结尾为 $a_i$ 并且保证最终子序列包含 $a_i$ 的情况下,当前子序列长度的最大值。

那么考虑 $f_i+1$ 贡献到 $f_j$ 的条件,设 $nx_i$ 为 $\min\{j\mid j>i\land a_j>a_i\}$,那么就是 $j\in[nx_i,nx_{nx_i})\land a_j>a_i$。

为了干掉 $a_j>a_i$ 这个条件,我们可以按 $a_i$ 从小到大枚举 $i$ 进行转移,这样就可以忽略这个条件。具体的,按 $a_i$ 从小到大枚举 $i$,用 $f_i$ 更新答案,然后用 $f_i+1$ 更新在 $[nx_i,nx_{nx_i})$ 中的 $f_j$。

注意,假如 $a_0=0$,那么 $f_i$ 的初值是 $[i\in[nx_0,nx_{nx_0})]$。

用线段树辅助转移,复杂度 $O(n\log n)$。

图同构:(Div. 1 Only)

来源:

  • 2021“MINIEYE杯”中国大学生算法设计超级联赛(6). Problem 1007. Power Station of Art
  • Petrozavodsk Summer 2021. Day 6. Xi'an JTU Contest 1, Grand Prix of Xi'an. Problem G. Power Station of Art
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Xi'an. Problem G. Power Station of Art

链接:https://qoj.ac/problem/1869

Tutorial by nantf

对相邻两个点 $u,v$ 操作时,相当于将两点同时反色,然后交换颜色。于是可以看成每个点的颜色跟着点权形成的二元组在移动,从起点到终点如果经过了偶数条边(经过多次算多次)则最终颜色不变,否则最终颜色需要反色。

每个连通块独立,以下分别考虑每个连通块,有两种情况。

1. 该连通块为二分图

则无论如何移动,只要确定了每个二元组的起点和终点,则颜色是否被反色只与起点与终点是否在二分图的同一部有关。

分别考虑每种点权,则要求 $A$ 图和 $B$ 图的 左部黑点+右部红点 数量相等、右部黑点+左部红点 数量相等。这是一个必要条件。构造说明这也是充分条件。

任取这个连通块的一棵生成树,任取一个叶子,不妨设其在 $B$ 图中为左部黑点或右部红点,则任取 $A$ 图中一个点权相同的左部黑点或右部红点(由和相等一定存在),将其一路交换过来,以后的过程就可以在两张图中都忽略这个叶子。最后所有点都可以归位。

2. 该连通块不为二分图

也即该连通块一定存在奇环。

此时在确定每个二元组的起点和终点后,颜色是否被反色还不好确定。

再注意到,所有二元组经过的边数之和为偶数。则要求两图黑点奇偶性相同,红点奇偶性相同,且对于每种点权,两图的总点数相等。这是一个必要条件。构造说明这也是充分条件。

首先若整个连通块就是一个奇环,可以用下述的方法使得点权不变的前提下,相邻两个点 $x,y$ 的颜色反转。

  • 将 $x$ 上的二元组沿反方向交换一圈到 $y$ 点,然后将原本 $y$ 上的二元组沿反方向交换一圈到 $x$ 点。

那么先任意交换至点权对应,由黑点红点奇偶性不变,容易用该操作使得颜色也对应。

然后对于任意一个连通块,固定一个奇环,任取这个连通块的一棵生成树(要求奇环上至多一条边不属于该生成树),任取一个不在奇环上的叶子。任取 $A$ 图中一个点权相同的点一路交换过来,若仅沿树边交换会导致颜色不对,则交换到该叶子后再一路交换到奇环,绕奇环交换一圈,再原路返回,颜色就是正确的。最后只会剩下这个奇环的点没有归位,用上一种情况的做法即可。

直接按上述过程判断即可,时间复杂度 $O(n+m)$。

找零:(Div. 1 Only)

来源:

  • 京都大学プログラミングProgrammingコンテストContest 2021. Problem F. One Yen Coin
  • Petrozavodsk Winter 2022. Day 1. Kyoto U Contest 2. Problem F. Flatland Currency.
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Kyoto. Flatland Currency.

链接:https://qoj.ac/problem/2544

Tutorial by p_b_p_b

可以发现,虽然纸币有不同面额,但我们其实只关心面额为 $1$ 的纸币数。剩余的钱具体是用哪些纸币表示出来,对后续操作没有影响。

因此也不难发现每次只会购买一个物品,不会出现打包购买的情况。

所以一个价格为 $a_i$ 的物品的价值就是 $5\lceil a_i/5\rceil-a_i$ ,我们需要做一个背包问题。但是价格实在是太高了。

注意到价值很小,所以可以把价值放进状态里。设 $dp_{i,j}$ 表示考虑了前 $i$ 个物品,获得的价值为 $j$ ,所需的最小代价,这样就可以把复杂度优化到 $O(n^2)$ 。

然后有多种继续优化的方法:

  • 注意到如果价值相同,那么一定是按价格从小到大选。所以可以设 $dp_{i,j}$ 表示考虑了所有价值 $\le i$ 的物品,获得的价值为 $j$ ,所需的最小代价,然后利用决策单调性在 $O(n\log n)$ 的时间内从 $dp_i$ 转移到 $dp_{i+1}$ 。
  • 注意到价值的 $\text{lcm}$ 是 $12$ ,所以可以把每种价值的物品分别先打包成价值为 $12$ 的包裹,然后按照价格从小到大选包裹。这样的一个问题是最优解的价值并不一定是 $12$ 的倍数,但是可以枚举价值为 $1,2,3,4$ 的物品选的个数模 $12,6,4,3$ 的值,然后先把这些物品选掉之后再贪心即可。
  • 放弃分析,直接先按照性价比排序贪心选,然后在每种价值物品的边界附近进行小背包。大概和前一种是等价的。

Public Easy Round #3 题解

2022-09-22 16:44:28 By Qingyu
  • 搬题人:
    • DNA 匹配 2:Qingyu
    • 情报传递 3:Qingyu
    • 别急 2:Qingyu
    • 旅程:flower
    • 染色:Qingyu
    • 运算符 2:feecle6418
    • 匹配求和:Qingyu
  • 组题人:Qingyu
  • 验题人:feecle6418, flower, gyh20, test12345
    UOJ 缺投!

DNA 匹配 2(50 Points)

来源:

  • infO(1) Cup 2017 National Round. Problem 2, DNA

链接:https://qoj.ac/contest/998/problem/4713

算法 1

题目好难啊,不太会做,干脆输出随机数吧!

期望得分 $1 \sim 2$ 分。

算法 2

我们接着输出随机数,由于是 bitand,所以我们考虑随机的时候让每个数的 popcount 大一些,例如要求每个数 popcount 至少为 $14$。

期望得分 $10 \sim 30$ 分。

算法 3

考虑将 $2000$ 个数分成两组 $A, B$,每组包含 $1000$ 个数。将第一组的二进制表示下 $0 \sim 9$ 位钦定为 $1$,$10 \sim 19$ 位设为随机数。将第一组的二进制表示下 $0 \sim 9$ 位设为随机数,$10 \sim 19$ 位钦定为 $1$。并假设任意两个数两两不同。

此时,注意到任取一对 $x \in A, y\in B$,$x \operatorname{and} y$ 恰好包含了 $y$ 的前 $10$ 位与 $x$ 的后 $10$ 位,这至少包含了 $1000\times 1000 = 10^6$ 种不同的结果。

期望得分 $50$ 分(满分)。

情报传递 3(50 Points)

来源:

  • ByteDance-Moscow Workshops Camp 2022. Shuffle Contest. Problem M, Multiple Communications

链接:https://qoj.ac/contest/997/problem/4675

算法 1

题目好难啊,不太会做,那就干脆把所有数都发过去吧!

需要 $NL$ 个 bit,可以通过子任务 1,获得 $5$ 分。

算法 2

如果 $x, y$ 均均匀独立随机生成,那么其前 $\ell$ 位相等的概率为 $2^{-\ell}$。因此,对于子任务 $3$,在数据随机的情形下,我们可以给每个串直接截取前 $30$ 位发送过去,并在询问时只使用 $C$ 的前 $30$ 位。

需要使用 $30N$ 个 bit,可以通过子任务 1 与子任务 3,获得 $10$ 分。

算法 3

算法 2 存在的问题是,我们可以刻意钦定一些位,使得每个串在这些位上均相等。为了避免攻击,我们可以给每个位 $i$ 附上一个 $[0,2^{30})$ 内的随机权值 $w_i$。根据 Schwartz–Zippel lemma,发生碰撞的概率即为 $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}$。

需要使用 $30N$ 个 bit,期望得分 $50$ 分(满分)。

别急 2(75 Points)

来源:

  • ByteDance-Moscow Workshops Camp 2022. Shuffle Contest. Problem B, Broken Connection

链接:https://qoj.ac/contest/997/problem/4664

观察

注意到我们发送过去后顺序会被随机打乱,因此我们可以认为我们只能传递每种数的数量。

问题可以转化为我们可以发送 $10$ 个非负整数变量 $x_0,x_1,\cdots, x_9$,且需要保证 $\sum_{i=0}^9 x_i \le L$。

算法 1

注意到我们要传递一个 $10$ 位 $10$ 进制数,我们不妨考虑用 $x_i$ 来表示第 $i+1$ 位的值。这样在最坏情况下需要使用长为 $100$ 的字符串,得分 $7.5$ 分。

在此基础上可以进行一些常数优化,例如给每一位随机一个排列 $p_{0\cdots 9}$,转而使用 $p_i$ 来表示,这样期望情况下每一位只会用到长为一半的字符串,可以获得更多的分数。

算法 2

注意到对于方程 $x_1+\cdots+x_n = m$,我们可以使用隔板法来计数其非负整数解的数量 $f(n,m) = \binom{m+n-1}{n-1}$。因此,我们可以快速的求出一个局面的字典序。注意到当 $L=50$ 时,$\binom{50+10-1}{10-1} = 12565671261 > 10^{10}$,因此我们直接使用解的字典序来编码 $X$ 即可。

期望得分 $75$ 分(满分)。

旅程(75 Points)

来源:

  • Natjecanje timova studenata informatičara hrvatskih sveučilišta 2012. Problem G. Restorani

链接:https://qoj.ac/contest/433/problem/4852

算法 1

可以把题意中 $u$ 对 $v$ 喜欢,建成 $u$ 到 $v$ 的有向边。那么 $u$ 推荐 $v$ 就等价于,可以从 $u$ 走到 $v$。

先缩点后,对于每个scc考虑决策。

  1. 不经过这个 scc,代价是 0。
  2. 经过 $k$ 个此 scc 的点,其中 $1$ 个点的代价 $y_u$,剩下 $k-1$ 个点的代价是 $x_u$。

因此考虑预处理 $f_{u,i}$ 表示在第 $u$ 个 scc 经过 $i$ 个点的最代价。

令 $g_{u,i}$ 表示从第 $u$ 个 scc 开始走,经过 $i$ 个点的最小代价,转移是枚举 $u$ 的出边,和 $u$ 里走过了多少点,时间复杂度 $O(n^3)$

染色(75 Points)

来源:

本题修改自 Hong Kong Olympiad in Informatics 2014 Senior Group(香港電腦奧林匹克 2014 高級組)中的 Dividing the Cities(城市分配)一题。

算法 1

题目好难啊,不太会做,直接把整个方案给发送过去吧。

每个颜色需要占用 $3$ 个 bit,共需 $3N$ 个 bit,期望得分 $2$ 分。

算法 2A

如果 Bob 自力更生,自己寻找染色方案,那么是非常困难的。但是对一张图 $2$ - 染色非常简单:我们只需要 DFS 一遍即可。

我们不妨将颜色两两配对,对于颜色 $c$ 我们发送颜色 $\left\lfloor c/2\right \rfloor$。此时,我们需要将每一种颜色 $c'$,区分为 $2c'$ 与 $2c'+1$。这相当于我们要将这种颜色的点进行 $2$ - 染色,我们只需要 DFS 整张图即可线性完成。

这样,每个颜色只需要占用 $2$ 个 bit,共需 $2N$ 个 bit,期望得分 $24.85$ 分。

算法 2B

我们考虑另一个角度。如果这张图中,某个点的度数小于 $8$,那么我们可以直接删去这个点:将其余部分的染色方案复原后,他至多只有 $7$ 个邻居,因此总有一种颜色它可以直接使用。

这样,我们可以不断地删去图中度数小于 $8$ 的点,直到所有点的度数都至少为 $8$。由于一条边至多对度数之和贡献 $2$,因此剩余的点数不可能超过 $M/4$ 个。

这样,我们只需要发送 $M/4$ 个点的信息,共需 $3M/4$ 个 bit,期望得分 $30.92$ 分。

算法 3

同时使用算法 2A 与算法 2B,共需 $M/2$ 个 bit,期望得分 $75$ 分(满分)。

运算符 2(125 Points)

来源:

  • Petrozavodsk Winter 2021. Day 8. Belarusian SU Contest, Yandex Cup. Problem A. Belarusian State University
  • XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem A. Belarusian State University

链接:https://qoj.ac/contest/536/problem/1083

算法 1

可以发现,二元 01 运算一共只有以下几种:

  • 恒 0 / 恒 1。这时可以通过重新对下标赋值,将其转为 AND 运算。
  • $f(x,y)=x$ 或 $f(x,y)=y$,或 $f(x,y)$ 等于 $x$ 或 $y$ 取反。这时可以通过重新对无关一边的下标赋值 1,将其转为 AND 运算。
  • 等价于,或把 $x$ 取反后等价,或把 $y$ 取反后等价,或均取反后等价 AND/XOR。

进行适当操作后,直接在每位上分别运用通常的 AND/XOR 卷积的处理方式即可。可以证明,AND 与 XOR 运算在每一位上不会互相干扰。

时间复杂度 $O(2^nn)$。

匹配求和(200 Points)

来源:

  • Petrozavodsk Winter 2020. Day 9. Yuhao Du Contest 7. Problem F. Fast as Ryser
  • XX Open Cup named after E.V. Pankratiev, Grand Prix of Zhejiang. Problem F. Fast as Ryser

链接:https://qoj.ac/contest/449/problem/2068

算法 1

设 $E_0 = \{ (1, 2), (3, 4), \cdots \}$,则注意到对任意 $E' \subseteq E$,$E'$ 是匹配当且仅当 $E' \cup E_0$ 是若干环与链的并。

image-per-3.jpg

注意到由于 $2i-1$ 与 $2i$ 必须在同一个集合内,因此集合总数只有 $O(2^{n/2})$ 种。因此我们可以在 $O(2^{n/2} \cdot n^2)$ 的时间复杂度内计算出对所有 $S$ 将其划分成环/链的方案数。例如,对于链,我们可以记 $dp[mask][i]$ 表示已经经过的 block 的集合为 $mask$,现在位于点 $i$ 的贡献之和。对于环,我们可以直接枚举最大的点当作环的起点,由于 $\sum_{i\le n} 2^i = 2^{n+1}-1$,因此复杂度仍为 $O(2^{n/2} \cdot n^2)$。

划分完成后,我们可以使用 SOS DP(时间复杂度 $O(n \cdot 3^{n/2})$)或子集 exp(时间复杂度 $O(n^2 \cdot 2^{n/2})$)来计算最终将图划分成若干环/链的方案数。

总的时间复杂度为 $O(n \cdot 3^{n/2})$ 或 $O(n^2 \cdot 2^{n/2})$。由于常数上的差异,两种算法实际上均可通过。

UOJ 缺投!

Public Easy Round #3 公告

2022-09-19 22:47:41 By Qingyu

提示:根据验题人的反馈,我们删去了一道题目并调整了分数分布。

Public Easy Round #3 将在 2022 年 9 月 25 日 08:00 举行!比赛将进行 5 小时,共 7 道题,OI 赛制。

在四个月后,又一场 PER 与大家见面了。与此前不同的是,我们调整了 Easy Round 的难度,增加了若干道签到题。题目的难度分布在 NOIP T1 至省选 T2,欢迎所有水平的选手来参加!

本次比赛中可能会包含若干道提交答案题、交互题与通信题。如果你不熟悉这些类型的题目,你可以使用 PTR #1、PER #1、PER #2 与 PR #6 中的题目来作为练习。

特别地,本场比赛每道题目的权重不同。题目的分数分布为 $50 + 50 + 75 + 75 + 75 + 125 + 200$,其中每道题目都可能包含一个或多个子任务,每个子任务中可能会有不同的评分方式。

本场比赛的组题人为 Qingyu,搬题人为 Qingyu, flower, feecle6418, Wu_Ren,验题人待定。

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public NOIP Round #1 题解

2022-09-10 21:22:33 By Qingyu
  • 搬题人:
    • 一维围棋:Wu_Ren
    • 斜二等轴测图:Wu_Ren
    • 盒子里的糖果:hehezhou
    • 冲塔:p_b_p_b
    • 波特分组:feecle6418
    • 别急:Y25t
  • 组题人:p_b_p_b
  • 验题人:syzf2222, Zeardoe, Dualqwq, yllcm
  • 题解:hehezhou, Wu_Ren, p_b_p_b, Y25t

一维围棋 (Div. 2 Only)

来源:

  • ACM-ICPC Japan Alumni Group Summer Camp 2019. Problem A, AiGo
  • Petrozavodsk Summer 2020. Day 5: JAG Summer+ Opening Contest. Problem A, AiGo

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

tutorial by Wu_Ren

枚举哪个位置去放棋子,首先如果上面已经有棋子就不能放,然后向左向右如果都是连续一段白再接一段黑,那么也不能放,否则一定能放。放了之后向左向右分别扫一遍即可知道占领了多少黑棋。

复杂度 $O(n)$ 或 $O(n^2)$。

斜二等轴测图 (Div. 1 + Div. 2)

来源:

  • 2018 Multi-University Training Contest 3. Problem B, Visual Cube
  • Petrozavodsk Summer 2020. Day 3: Songyang Chen Contest 3. Problem B, Visual Cube

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

tutorial by Wu_Ren

按照题意模拟即可,复杂度 $O(T(a+b)(b+c))$。

盒子里的糖果 (Div. 2 Only)

来源:

  • Petrozavodsk Summer 2021. Day 4: Shanghai ICPC Camp 2021 Onsite Day 1 by PKU. Problem F, Interval Shuffle

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

tutorial by hehezhou

算法一

令 $dp_{i,j}$ 表示 $i$ 次操作后,$a_j$ 的最大值。

那么有: $$\begin{cases}dp_{i,j}=dp_{i-1,j}&j\in[1,l_i)\bigcup(r_i,n]\\ dp_{i,j}=\max(dp_{i-1,j}+1,\max_{k\in [l_i,r_i]}dp_{i-1,k})&j\in[l_i,r_i]\end{cases}$$

即只需考虑 $i-1$ 步时的最大值即可推出 $i$ 步后的最大值。构造某位的最大值只需按照 dp 转移式逆推即可。

时间复杂度 $O(n^2)$。

算法二

考虑用线段树优化上述过程:

  1. 计算 $\max_{k\in [l_i,r_i]}dp_{k}$ 即为一次查询区间最大值。
  2. 更新 $dp$ 值可以表示为一次区间加和一次区间取 $\max$。

这是一个经典线段树问题,可以在 $O(n\log n)$ 的时间复杂度内解决。

冲塔 (Div. 1 + Div. 2)

来源:

  • National Olympiad in Informatics 2022. Problem 3, Towers

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

tutorial by p_b_p_b

先不管“每列只能冲至多两个塔”的限制,直接先把每行最左和最右的塔都冲掉。

这时候当然可能会出现某一列超过两个塔了。但是往好处想:如果超过两个塔,是不是说明中间那个塔就不需要冲了呢?

因此可以每次找到最靠右的一列,使得这一列有超过两个塔,然后把中间的那些塔全都往左移动一位。

不难发现每次这样操作之后仍然满足每个塔都被覆盖,并且 $O(n)$ 次操作之后就不会存在冲了超过两个塔的列了。

用 set 维护,复杂度 $O(n\log n)$ 。

波特分组 (Div. 1 Only)

来源:

  • Petrozavodsk Winter 2020. Day 7: Gennady Korotkevich Contest 5. Problem F, Flip
  • XX Open Cup named after E.V. Pankratiev, Grand Prix of Gomel. Problem F, Flip

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

tutorial by feecle6418

设 $S=\sum k$。

算法一

直接枚举每枚硬币哪面朝上,时间复杂度 $O(q2^{2n})$,可以通过第一个子任务,期望得分 $9$。

算法二

考虑先枚举每一种情况,用子集和变换预处理每种输入哪些会有贡献,时间复杂度 $O(2^{2n}n+S)$,可以通过前两个子任务,期望得分 $25$。

此外,可能存在一些高复杂度算法,可以通过前三个子任务。

算法三

首先,给定一种分组状态,它出现的概率是多少?设最后一个分到 A 组的人编号为 $i_A$,最后一个分到 B 组的人编号为 $i_B$,则概率为 $2^{-\min(i_A,i_B)}$。

对于每组询问,不妨假设全分在 A 组,枚举 $\min(i_A,i_B)=p$ 的值,计算分组方案数:

  • $p=b_k$,此时分组方案数为 $\binom{b_k-k}{n-k}$。
  • $p$ 位置分在 B 组,不妨设 $b_i < p < b_{i+1}$,则分组方案数为 $\binom{p-i-1}{n-1}$。对于固定的 $i$,$p-i-1$ 构成区间,恰当预处理前缀和可以 $O(1)$ 求出。
  • $p>b_k$ 且 $p$ 位置在 A 组,则分组方案数为 $\binom{p-k-1}{n-k-1}$。对于每种出现的 $k$,分别 $O(n)$ 预处理该式与概率的乘积的后缀和即可。

因为不同的 $k$ 只有 $\sqrt S$ 个,所以时间复杂度 $O(n\sqrt S+S)$,期望得分 $100$。注意边界。

本题也存在线性做法。

别急 (Div. 1 Only)

来源:

  • XXII Open All-Siberian Programming Contest named after I.V. Pottosin Final tour, II day. Problem 11: Captivating process
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Siberia. Problem 11: Captivating process

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

tutorial by Y25t

建两张有向图 $F,G$,对所有 $1\le i\le n$ 在 $F$ 中连有向边 $(i,f_i)$,在 $G$ 中连边 $(i,g_i)$。那么它们分别形成基环内向森林。

对于一个点 $u$ ,若它能沿着 $F$(或 $G$)中唯一出边走若干步能回到 $u$,则称它为 $F$(或 $G$)中的环点,否则称它为 $F$(或 $G$)中的树点。定义 $dep^F_u$ 为在 $F$ 中 $u$ 第一次走到环点所需步数。若 $u$ 在 $F$ 中是环点,则 $dep^F_u=0$,同时定义 $l^F_u$ 为 $u$ 所在环的长度,$d^F_u$ 为 $u$ 在其所在环上的编号(满足 $0\le d^F_u< l^F_u$ 且 $d^F_{f_u}\equiv d^F_{u}+1\pmod{l^F_u}$)。类似地定义 $dep^G,l^G,d^G$。

对于一块石板 $(x,y)$,不妨设 $dep^F_x\le dep^G_y$。考虑将时间分为 $[0,dep^F_x),[dep^F_x,dep^G_y),[dep^G_y,+\infty)$ 三段,分别判断是否会裂开。

$[0,dep^F_x)$

在这段时间里,$x$ 为在 $F$ 中的树点,$y$ 为在 $G$ 中的树点。

该石板会在这段时间中裂开,当且仅当存在点 $u$ 使得以下三个条件同时满足:

  • $dep^F_x-dep^F_u=dep^G_y-dep^G_u$,即 $dep^F_u-dep^G_u=dep^F_x-dep^G_y$。
  • 在 $F$ 中 $u$ 是树点,且为 $x$ 的祖先。
  • 在 $G$ 中 $u$ 是树点,且为 $y$ 的祖先。

于是将询问离线后在 $G$ 的树部分进行 dfs。用 std::set 或动态开点线段树维护 $2n$ 个线段集合 $S_i(-n\le i\le n)$。在进入一个点 $u$ 时,在 $S_{dep^F_u-dep^G_u}$ 中插入线段 $[dfn^F_u,dfn^F_u+sz^F_u-1]$(其中 $dfn^F,sz^F$ 为在 $F$ 中的 dfs 序和子树大小),回溯时撤销。对于询问 $(x,y)$,在进入 $y$ 后判断 $S_{dep^F_x-dep^G_y}$ 中是否有线段覆盖了 $dfn^F_x$ 即可。

该算法加一些简单特判后可通过子任务 7。

$[dep^F_x,dep^G_y)$

在这段时间里,$x$ 为在 $F$ 中的环点,$y$ 为在 $G$ 中的树点。

该石板会在这段时间中裂开,当且仅当存在点 $u$ 使得以下三个条件同时满足:

  • $d^F_u-d^F_x\equiv dep^G_y-dep^G_u\pmod{l^F_u}$ 即 $d^F_u+dep^G_u\equiv d^F_x+dep^G_y\pmod{l^F_u}$。
  • 在 $F$ 中 $u$ 是环点,且与 $x$ 在同一环中。
  • 在 $G$ 中 $u$ 是树点,且为 $y$ 的祖先。

于是可以用类似的 dfs 进行求解。

该算法加一些简单特判后可通过子任务 6。

$[dep^G_y,+\infty)$

在这段时间里,$x$ 为在 $F$ 中的环点,$y$ 为在 $G$ 中的环点。

该石板会在这段时间中裂开,当且仅当存在点 $u$ 使得以下三个条件同时满足:

  • $d^F_u-d^F_x\equiv d^G_u-d^G_y\pmod{\gcd(l^F_u,l^G_u)}$
  • 在 $F$ 中 $u$ 是环点,且与 $x$ 在同一环中。
  • 在 $G$ 中 $u$ 是环点,且与 $y$ 在同一环中。

std::set 维护三元组即可简单判断。

该算法可直接通过子任务 5。

结合以上三个算法即可通过本题。

共 36 篇博客
  • 1
  • 2
  • 3
  • 4