whqsing。

• 组题人：Qingyu
• 搬题人：
  • 黑白点：flower, Qingyu
  • 博弈：Qingyu
  • 地雷：flower, p_b_p_b
  • 桥桥桥：Qingyu
  • 游戏：Qingyu
  • 知识：alpha1022, Qingyu
• 题解：flower, Qingyu, LeafSeek, alpha1022

黑白点

Source:

• Xmas Contest 2022. Problem H. Happy Game

特别感谢 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]。

• https://qoj.ac/problem/5241

算法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$。

桥桥桥

• Source: Potyczki Algorytmiczne 2020, Runda 5, Trzy drogi [A]
• https://qoj.ac/problem/1395

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

• 取出 $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$ 是否合法。

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

游戏

Source:

• Canadian Comuputing Olympiad 2022. Day 2. Problem 3. Good Game
• https://qoj.ac/problem/4273

算法一

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

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

1. 如果不删空连续段，则这次操作可能会让这个 2 变为 1 或 2。
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 2021. Problem H. Homework From Zhejiang

特别感谢 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 中国国家集训队论文

03/19/2025

1. You can now upload the avatars directly on "modify profile" page. Gravatar is still supported and recommended to use.

01/13/2025

1. We updated the compilers and judging environment. More details can be found here

12/10/2024

1. The scoreboard now shows SE ("average hardness").

10/11/2024

1. The contest list now shows an estimated difficulty for the contests.

08/14/2024

1. Updates for the scoreboard of ICPC-style competitions
2. The Battle of Giants and External Scoreboard pages now refresh automatically.

05/12/2024

1. 更新 Python 3 版本为 Python 3.12.3。
2. 更新 DMD 版本为 DMD64 D Compiler v2.108.1。
3. 更新 rustc 版本为 rustc 1.75.0 (82e1608df 2023-12-21)。

04/28/2024

1. 增加了对 IOI 赛制比赛中关于子任务取最大值规则的支持。现在在 QOJ 上进行的 IOI 赛制的比赛将会使用标准的 IOI 评分规则（即，每个子任务的得分为所有提交记录该子任务得分的最大值；每个题的得分为所有子任务的得分之和。）
   • 同时，在 IOI 赛制的比赛中会存在 “My Score” 选项卡，展示当前你的得分。

04/24/2024

1. 修复了 Virtual Contests 时提交时间可能显示不正确的 bug。
2. 现在比赛的管理员可以设置每道题目提交次数限制与提交间隔限制。

01/16/2024

1. 更新 GCC 版本为 GCC 13.1.0。
2. 更新 Python 3 版本为 Python 3.12.1。

12/25/2023

1. 添加对 D 的支持，采用的编译器版本为 DMD64 D Compiler v2.106.0，编译选项为 -O -release -inline -boundscheck=off

09/29/2023

1. 添加对 Rust 的支持，采用的编译器版本为 rustc 1.70.1，编译选项为 rustc -o answer -C opt-level=3 answer.code
2. 将提交记录的代码高亮库更换为 highlight.js

09/11/2023

1. 主站的评测机数更改为 5 台。每台评测机的 CPU 均为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。其中评测机 #1 的内存为 32 GiB，其余两台评测机的内存为 16 GiB。
2. 修改了沙盒中的部分实现。由于此前编写的 judger 有部分不兼容新的沙盒，因此目前所有使用了自定义 judger 的题目均被暂时隐藏。他们将在确认兼容性后重新公开。

08/28/2023

1. 增加了对可任意选择 Time Window 开始时间赛制的支持。
2. 增加了对包含多个固定的 Time Window 的赛制的支持。
3. 增加比赛管理员可以为某个用户单独延长比赛时间的特性。
4. 比赛管理员现在可以取消用户的报名。
5. 修复了在 Time Window 结束后的提交仍然会被算入比赛提交的 bug。
6. 不再禁止用户选择开始时间比当前时间更早的 Time Window。
7. 比赛结束后的提交现在也可以在比赛提交记录中查看。

08/22/2023

1. 主站的评测机数更改为 3 台。每台评测机的 CPU 均为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。其中评测机 #1 的内存为 32 GiB，其余两台评测机的内存为 16 GiB。

08/10/2023

1. QOJ 开始记录评测记录的历史信息！

08/04/2023

1. 在注册 Virtual Contests 时会弹出确认列表。
2. 修复了在 VP 时可以查看题目统计信息的 bug。
3. 修复了在 IOI 赛制的 VP 时可以查看测试点详细信息的 bug。

06/14/2023

评测机所使用的 CPU 由 Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz 更换为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。

04/27/2023

1. 在 VP 时 Attachments 会默认隐藏题解。
2. 在 VP 时禁止查看比赛中其他人的提交记录。

03/21/2023

Category 增加显示每个子类别比赛与题目数。

03/19/2023

进行了一些微小的更新。

03/04/2023

1. 对应比赛的管理员可设置在比赛进行时排行榜的显示范围（是否显示正式选手/Virtual 选手，以及每类 Ghosts 的范围）
2. 对应比赛的管理员可导出比赛的 Standings 文件（.dat / TestSys 格式）
3. 在导入 Polygon 格式的题目时，使用标准校验器的题目将默认配置 use_builtin_checker，而不再使用独立的 checker。
4. 检验数据正确性不再要求配置 Main Correct Solution。

02/25/2023

1. 修复了无开始时间的比赛 VP 后不会滚榜的 bug。
2. 修复了 Category 对比赛排序时产生的问题。

02/18/2023

进行了一些微小的更新。

02/13/2023

进行了一些微小的更新。

02/03/2023

1. ICPC 赛制现支持设定封榜。
2. 修复了部分通信题出现 Dangerous Syscalls 的问题

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

万能的 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_b 与 Qingyu，搬题人为 alpha1022, flower, hehezhou, p_b_p_b, Qingyu。

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

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

• 搬题人：
  • 咖啡, 画图：Qingyu
  • 治病, 拓扑序计数：feecle6418
  • 序列：Wu_Ren
  • 水果：p_b_p_b
• 组题人：Qingyu
• 题解：alpha1022, feecle6418, Wu_Ren, p_b_p_b

咖啡 (Div. 2 Only)

来源：

• Nordic Collegiate Programming Contest 2022. Problem C. Coffee Cup Combo
• https://qoj.ac/contest/1024/problem/4990

Tutorial by alpha1022.

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

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

画图 (Div. 2 Only)

来源：

• All Ireland Programming Olympiad 2017 National Finals. Problem C. Paint bucket
• https://qoj.ac/contest/11/problem/48

Tutorial by alpha1022.

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

治病 (Div. 1 + Div. 2)

来源：

• Petrozavodsk Winter 2020. Day 4. Yandex Cup 2020. Problem B. Bad Doctor
• http://qoj.ac/contest/444/problem/686

Tutorial by feecle6418.

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

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

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

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

来源：

• Petrozavodsk Winter 2020. Day 4. Yandex Cup 2020. Problem C. Topological Ordering
• http://qoj.ac/contest/444/problem/687

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)

来源：

• Petrozavodsk Winter 2021. Day 4. PKU Contest (Common Contest 1). Problem H. Longest Loose Segment
• http://qoj.ac/contest/532/problem/894

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)

来源：

• (Singapore) National Olympiad in Informatics 2022. Problem E. Fruits
• http://qoj.ac/contest/919/problem/3875

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 月 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。

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

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

• 搬题人：
  • 数字：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)

来源：

• Petrozavodsk Winter 2020. Day 4: Yandex Cup 2020. Problem H. Delete the Points
• https://qoj.ac/contest/444/problem/692

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

• 搬题人：
  • 就这：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$ 的值，然后先把这些物品选掉之后再贪心即可。
• 放弃分析，直接先按照性价比排序贪心选，然后在每种价值物品的边界附近进行小背包。大概和前一种是等价的。

• 搬题人：
  • DNA 匹配 2：Qingyu
  • 情报传递 3：Qingyu
  • 别急 2：Qingyu
  • 旅程：flower
  • 染色：Qingyu
  • 运算符 2：feecle6418
  • 匹配求和：Qingyu
• 组题人：Qingyu
• 验题人：feecle6418, flower, gyh20, test12345UOJ 缺投！

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）

来源：

• QOJ 141（https://qoj.ac/problem/141 ）

本题修改自 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$ 是若干环与链的并。

注意到由于 $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})$。由于常数上的差异，两种算法实际上均可通过。

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

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，验题人待定。

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

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