whqsing。

什么是 QOJ？QOJ 由谁在维护？

QOJ 是由我（Qingyu）搭建、开发并维护的在线评测系统（Online Judge）。QOJ 希望整理、分类并维护世界各地的算法竞赛题目、比赛信息与排行榜等数据，并为所有人提供题目练习或模拟训练的平台。

QOJ 的系统、题目与比赛的维护工作均主要由我进行。同时几位其他管理员会辅助参与 QOJ 的管理工作，他们分别是 flower, alpha1022 与 Qiuly。感谢他们愿意抽出宝贵的时间来参与到 QOJ 的管理工作当中。

QOJ 基于开源项目 Universal OJ 与 Universal OJ 社区版 进行二次开发，没有 vfk 与开源社区的劳动成果 QOJ 将不会存在，在此感谢整个 UOJ 开源社区对 UOJ 的开发与维护。

同时，感谢 AutumnKite, hehezhou, hydd, p_b_p_b, Qglin_ 为本站的设计提供了宝贵的建议。

注册后如何上传头像？

请使用 Gravatar。当然，你也可以直接在用户信息中修改头像，但是使用 Gravatar 仍然是我们最推荐的方式。

我忘记了我的密码，有没有方法找回？

请使用找回密码功能。

QOJ 是否允许修改用户名？

不允许。但是你可以向管理员申请修改昵称。

QOJ 的编译器信息是什么？

• Python2: Python 2.7.18
  • Python 会先编译为优化过的字节码.pyo文件。
• Python3: Python 3.10.9
  • Python 会先编译为优化过的字节码.pyo文件。
• C/C++: GCC 11.1.0
  • 编译命令为 g++ code.cpp -o code -lm -Ofast -DONLINE_JUDGE
  • 选择对应语言版本时会增加 -std=c++??
• Java 8/Java 11: openjdk version "11.0.16"
  • 编译命令为 javac code.java
• Pascal: fpc 3.0.4+dfsg-23
  • 编译命令为 fpc code.pas -O2

我想使用 Rust/Kotlin/C#/Go/... 编写程序，QOJ 有计划支持他们吗？

短期内没有。

QOJ 的评测机 CPU 是什么？

Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz

题目的时间限制与空间限制在哪里？

在题目标题的上方。

题目的附加文件在哪里下载？

在题目正文上方标签栏处。

是否对栈空间进行额外限制？

除非题目特殊声明，否则栈大小限制与该题的空间限制相等。

QOJ 的特殊题目标签含义是什么？

• Interactive：这是一道交互题。选手可能会使用 I/O 或其他方式与交互库进行交互。
• Output Only：这是一道提交答案题。选手不需要提交代码文件，只需要上传答案文件。
• Communication：这是一道通信题。选手可能需要提交多个程序，或同一个程序会被运行多次。
• Unavailable：题目不可用。可能是我们没有对应题目的数据或辅助测评程序，也可能是我们的硬件资源无法满足题目测评要求（例如在 100 个线程中并行评测的题目）。

Hack 功能是什么？

在 QOJ 中，所有拥有 validator 与 standard 的题目均支持 Hack。对于任意通过的提交记录，如果你发现其无法通过某一组测试数据，则你可以使用 Hack 功能尝试 Hack 此提交记录。如果你的 Hack 成功，该组数据将会被添加进入 extra test 并重测所有提交记录。

我不想公开我的提交记录，有没有什么方法？

你可以在个人信息 - 修改个人信息中选择 "不公开个人代码"。

注意：在以下情况中，"不公开个人代码"的选项无效。

1. 你在一场允许使用 Hack 功能的比赛当中提交了这份代码，且对方是对应比赛的参赛选手。
2. 你在一场比赛中提交了这份代码，且对方是对应比赛的管理员。
3. 对方是对应题目的管理员。

QOJ 是否支持虚拟参赛（Virtual Participation）？

目前 OI/IOI/ICPC 赛制的比赛均支持 VP。在点击开始按钮后，即可开始虚拟参赛。

目前 VP 暂不支持组队，此 feature 会在以后添加支持（soooooon）

QOJ 的 IOI 赛制有没有注意事项？

请注意，QOJ 的 IOI 赛制（包括 VP）中，每道题目的得分为所有提交记录的最高得分，而非所有子任务的最高得分之和。在未来我们会支持取所有子任务的最高得分之和作为题目得分，但现在仍不可用。

QOJ 的 ICPC 赛制有没有注意事项？

QOJ 的 ICPC 赛制将在最后一小时进行封榜，最后一小时其他队伍提交的结果将在比赛完成后可见。

QOJ 的测评环境与 Universal Cup 所使用的 DOMjudge 是否相同？

并不相同。二者的评测机运行在两台独立的服务器上。

在什么情况下，我参加比赛会被计算 Rating？

请注意：与 UOJ 不同，在 QOJ 中，只有满足以下情形才会被计入 Rating。

1. 你是对应比赛的正式选手，被移入非正式选手（用户名前带有星号）或 VP 参加的选手不会被计入 Rating。
2. 你满足对应比赛的计分要求：
   • （OI 赛制）：你提交了至少一份代码，且得到了非零的分数。
   • （IOI 赛制）：你提交了至少一份代码，且得到了非零的分数。
   • （ICPC 赛制）：你提交了至少一份代码，通过了对应题目的样例数据。

QOJ 的 Rating 有实际作用吗？

截至目前，在点评题目或比赛时，Rating 较高的用户的赞/踩具有更高的权重。除此以外没有任何实际作用。

我在 Universal Cup 中注册了队伍，能否使用 UCup 的用户信息登录 QOJ？

可以。你也可以使用 Universal Cup 的注册中获得的用户信息来登录 QOJ 并正常使用其他功能，但是无法接收与发送私信。

我在 Public Judge 中注册了账号，能否使用 pjudge 的用户信息登录 QOJ？

可以。

我在 Universal Online Judge 中注册了账号，能否使用 UOJ 的用户信息登录 QOJ？

不可以。QOJ 基于 UOJ 二次开发，但二者的实例无任何关系。

我在使用 QOJ 的过程中出现了问题，能不能联系你们？

你可以通过以下方式联系到我们：

1. 站内私信 Qingyu。
2. 发送邮件至 [email protected]

我在使用 Universal Cup 的过程中出现了问题，能不能联系你们？

请联系 Universal Cup 组委会。

我在使用 Public Judge 的过程中出现了问题，能不能联系你们？

请联系 Public Judge 组委会。

我在使用 Universal Online Judge 的过程中出现了问题，能不能联系你们？

请联系 UOJ 管理员。

• 组题人：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 中国国家集训队论文

09/29/2023

1. 添加对 Rust 的支持，采用的编译器版本为 rustc 1.66.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})$。由于常数上的差异，两种算法实际上均可通过。