Public NOIP Round #5 将在 2023 年 2 月 25 日 8:30 举行！

本次比赛只有提高组，进行 4.5 小时，有 4 道题，OI 赛制。题目难度约为 noip ，所有题目都有部分分。

本次比赛的组题人为 Qingyu ，搬题人为 p_b_p_b, ShanLunjiaJian, alpha1022, feecle6418。

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

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

Public NOIP Round #2 将在 2022 年 10 月 4 日 8:30 举行！

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

与上一次比赛不同的是，本次比赛将与 MarsOJ 合作。pjudge 上仍然会有常规模式的比赛，而 MarsOJ 则可以提供仿真 csp/noip 考场环境的云电脑，具体可以加入用户群（915426363）。

选手可以根据自己的训练需要来自由选择在 pjudge 或 MarsOJ 参赛。两边都是免费的。

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

本次模拟赛的组题人为 p_b_p_b ，搬题人为 Wu_Ren, hehezhou, Y25t, skip2004, p_b_p_b ，验题人待定。

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

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

• 搬题人：
  • A, B：p_b_p_b
  • C：ezoilearner
• 组题人：p_b_p_b
• 题解：p_b_p_b, ezoilearner

大凯的疑惑

题目来源：

• Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest, Problem I

QOJ 链接：https://qoj.ac/contest/448/problem/1462

正解不对拍，爆零两行泪。

$$\begin{aligned} (a+d)^k-a^k=\sum_{i=1}^k {k\choose i}d^ia^{k-i} \end{aligned}$$ 设 $f_i={k\choose i}d^i$ ，列出前后几项：$f_1=kd, f_2=k(k-1)d^2/2,\cdots,f_k=d^k$ 。

不难发现答案的质因子一定都是 $d$ 的质因子，对 $d$ 的每个质因子 $p$ 分别考虑。设 $C(x)=\max\{i\mid p^i|x\}$ ，即 $x$ 里面 $p$ 的次数。

引理：当 $i\le p^{C(k)}$ 时， $C({k\choose i})=C(k)-C(i)$ 。

证明：$C(k-t)=C(t), 1\le t<p^{C(k)}$ 。

因此就有 $C(f_i)=iC(d)+C(k)-C(i), 1\le i\le p^{C(k)}$ 。并且由于 $C(d)\ge 1$ ，所以可以感性理解得到 $C(f_i)$ 大致是递增的，最小值是 $C(f_1)$ 。并且不难证明，如果 $C(f_1)$ 是唯一的最小值，那么答案就是 $p^{C(f_1)}$ 。

如果这个感性理解是正确的，那么答案就是 $kd$ 中 $d$ 的所有质因子，即 $\gcd(d^{\infty},kd)$ 。

事实上这个感性理解的并没有太大问题，只是在 $i$ 特别小的时候需要修一下。当 $p=2,C(d)=1,2|k$ 时，$C(f_2)=C(f_1)=C(kd)$ ，所以答案要多乘一个 $2$ 。

道路重建

题目来源：

• 2021-2022 ICPC Asia Pacific - Yokohama Regional, Problem E
• Moscow Pre-Finals Workshops 2022 Day 4, Problem E

QOJ 链接：https://qoj.ac/contest/912/problem/3798

显然可以先把城市内的最小生成树求出来，只有这上面的边是有用的。进一步，按照边权从小到大的顺序合并连通块时，如果至少一边没有枢纽车站，那么这条边一定会被计入答案，也不需要考虑了。

进行这些预处理之后可以认为 $m=n-1$ 且所有火车站都是枢纽车站。

人脑模拟 kruskal 的过程：

• 在考虑到第一条高铁线路之前，每个城市都在按照相同的顺序合并，只是速度有快有慢。
• 按 $a$ 从小到大考虑每个城市。
  • 不妨假设 $\arg \min a_i=1$ ，且 $b_1<b_2$ 。
  • 显然城市 $1$ 连的边是城市 $2$ 连的边的超集。因此城市 $2$ 目前的每个连通块都会向城市 $1$ 连恰好一条高铁线路。
  • 连接之后，我们发现两个火车站 $i,j$ 连通当且仅当对应编号在城市 $1$ 中连通，而与这两个火车站实际在城市 $1$ 还是城市 $2$ 无关！并且城市 $2$ 里面也不会连接新的动车线路了。
  • 因此接下来可以令 $a_1:=a_2$ ，然后忽略城市 $2$ 继续做。

复杂度 $O(n\log n)$ 。

杜杜和DUDU

题目来源：

• Petrozavodsk Winter 2022. Day 6. 2022 ICPC Training Camp powered by Huawei — Day 1, Problem F

QOJ 链接：https://qoj.ac/contest/824/problem/2610

考虑按 $x$ 从小到大扫描线，维护哪些 $(x,y)$ 可达。

当我们扫完 $x\leq K$ 的时候，扫完的点有 $(x_1,y_1),\cdots,(x_q,y_q)$ .

定义 $g_y=\max(x_i|y_i\leq y)$ ,如果 $(x,y)$ 可达但 $x<g_y$ 那么 $(x,y)$ 没必要保留,因为 $(g_y,y)$ 不可达意味着 $(x,y)$ 不能一次到 $(g_y,y)$ ，注意按照定义一定存在 $(g_y,z),z\leq y$ 的点，所以 $(x,y)$ 到 $(g_y,y)$ 是有转移的，进一步这意味着 $(x,y)$ 不能一次转移到一个横坐标超过 $K$ 的点,因为这样的代价一定不少于 $(x,y)$ 到 $(g_y,y)$ 的代价。

我们需要设计的算法已经很明显了，扫的过程中我们维护一个序列 $seq$ , $seq_y=1$ 表示 $(g_y,y)$ 可达，反之不可达。假设我们现在扫完了小于 $K$ 的部分，现在要加入横坐标为 $K$ 的点，假设其中纵坐标最小的点是 $(K,z)$。

考虑可能的操作形式，一种是横坐标扩大到 $K$ ,但纵坐标不变，这种我们对于 $g_y$ 相同部分的 $y(y\geq z)$ 统一处理，按照势能分析这样的次数是 $O(n)$ 级别的，分析类似单调栈。

还有可能横纵坐标都加大，变成 $(K,z)$ ,这种只要对于每种 $g_y$ 维护可达的最大 $(g_y,y)$ .

在执行完上面两种转移后，我们还可能执行横坐标不变，纵坐标加大的操作，用线段树容易维护 $(K,y)$ 最多往上跳到哪。但我们是不是要对上面两种转移得到的 $(K,y)$ 都执行下这种操作呢。想一想，其实只要转移第一种转移每段转移后得到的最大 $y$ （更小的 $y$ 要么不会增加新的可达点，要么新增的和最大的 $y$ 一样）和第二种的 $(K,z)$ 就好了（如果 $(K,z)$ 可达的话）。

但其实因为我们可能会增加新的纵坐标，所以上面的分析不充分。假如我们新增了 $(K,h)$ ，其中 $h$ 是以前没有出现过的纵坐标，找到在已经出现过的纵坐标中 $h$ 的前驱 $p$，如果 $(K,p)$ 可达且 $(K,p)$ 到 $(K,h)$ 的转移合法，那么可以扩展 $(K,h)$ 了。

具体算法看 std 效果更佳哦。

Public Round #7 将在 2022 年 7 月 31 日 8:00 举行！比赛将进行 5 小时，共 3 道题，OI 赛制。

本次比赛的题目难度约为 NOI D1，所有题目都有部分分。

本次模拟赛的组题人为 p_b_p_b ，搬题人为 p_b_p_b, ezoilearner ，验题人为 superguymj, Qingyu 。

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

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

• 搬题人：
  • A：p_b_p_b
  • B：cdw
  • C：Qingyu
• 组题人：p_b_p_b
• 题解：p_b_p_b, cdw, Qingyu

DNA 匹配

题目来源：

• 2021-2022 ICPC Asia Pacific - Yokohama Regional, Problem H
• Moscow Pre-Finals Workshops 2022 Day 4, Problem H

QOJ 链接：https://qoj.ac/contest/912/problem/3801

都 2202 年了怎么还有输出实数的非计算几何题啊？怎么相对误差在 $0.05$ 以内都算对？

这么离谱的误差范围，不难想到这题应该想一些乱搞。

毛估估一下会发现容斥并不是个好方法。尽管取的 $s_i$ 变多之后概率会迅速变小，但是组合数会迅速变大，所以简单地在某个大小进行截断是无法通过此题的。

另辟蹊径，注意到有一档部分分保证 $ans\ge 0.01$ ，所以可以用蒙特卡罗法进行随机抽样来估计概率。

蒙特卡罗法的不足之处在于，当答案太小时很难抽中一个合法的 DNA 序列，于是估计结果总是为 0 。但是我们可以限制随机抽样的范围，来保证抽中的序列总是合法的。所以可以想到，我们可以只在合法的 DNA 序列中抽样。

先设置一个贡献的分配方式。对于每一个 DNA 序列 $t$ ，若其在所有 $m$ 个串中可以匹配 $k\ (k>0)$ 个，那么 $t$ 会给每个能匹配的 $s_i$ 带来 $\frac 1 k$ 的贡献。

我们对每个 $s_i$ 分别计算贡献。仍然使用蒙特卡罗法，但是显然只有能匹配 $s_i$ 的 DNA 序列才能对 $s_i$ 带来贡献，因此我们让抽取的 DNA 序列 $t$ 在匹配 $s_i$ 的序列中随机，最后再除掉匹配 $s_i$ 的概率。这样就解决了答案太小的问题。

也可以让 $t$ 只给第一个匹配的 $s_i$ 带来 $1$ 的贡献，做法是一样的。

区间数颜色

题目来源：

• Petrozavodsk Winter 2022. Day 2. KAIST Contest + KOI TST 2021, Problem H

QOJ 链接：https://qoj.ac/contest/820/problem/2559

考虑假如存在 $L_j\le L_i,R_i\le R_j,i< j$，那么 $i$ 一定比 $j$ 要早出现在答案里。

一开始，我们把区间按照左端点排序。

当一个区间包含的所有区间都已经加入答案之后，我们再把这个区间加入候选集合。一开始，我们先把不包含其他区间的区间加入候选集合。我们把候选集合里的区间按左端点排序，这样它们的编号也是有序的（事实上，你发现这样右端点也是有序的）。

考虑离散化之后，区间的端点把整个数轴划分成 $O(n)$ 个段，我们每次把某个区间加入答案，相当于覆盖掉某些段。那么一个段被覆盖后，包含这个段的区间在候选集合里是连续的一段。

我们对于每个区间维护一个 $\text{remain}_i$ 表示现在第 $i$ 个区间里没被覆盖的段长之和，对于不在候选集合里的，我们认为是 $+\infty$。

那么就是对标号在某个区间内的 $\text{remain}_i$ 减去这段的长度。我们可以用一个 set 维护哪些段没被覆盖，然后用一个树状数组维护一个区间内没被覆盖的段长之和，这样我们在把某个区间加入候选集合的时候也可以知道它的 $\text{remain}$。

考虑我们把某个区间加入答案后，我们就从候选集合删去它后，此刻可能有一些区间可以加入候选区间，那么找到候选集合里这个区间的前驱 $j$ 和后继 $k$，那么可以加入的区间一定包含于 $(L_j,R_k)$，那么我们需要它的编号比 $j$ 大，并且右端点比 $R_k$ 小，那么每次找到标号在 $(j,n]$ 里的区间里右端点最小的区间尝试加入，再用一棵线段树维护即可。

复杂度 $O(n\log n)$。

情报传递 2

题目来源：第１３回日本情報オリンピック　春季トレーニング合宿, Day 4, Task 漢字しりとり(Kanji Shiritori)

QOJ 链接：https://qoj.ac/contest/337/problem/1407

算法 1

通信题好难啊，还是弃疗吧。直接让 Spy 把 Participant 不知道的信息都发送过去咋样？

计算一下，一共需要发送 $K$ 条边的边权，总共需要 $K \cdot \left\lceil \log_2 W\right\rceil = 5 \times 54 = 270$ 个 bit。随后让 Participant 运行 Floyd 算法，记录过程中更新的最短路并复原该路径即可。

共需 $270$ 个 bit，可以通过子任务 1，得到 5 分。

算法 2

注意到其实 Participant 不需要知道这些边的边权，甚至不需要知道最后最短路的长度 - 他只需要知道方案就可以了！

注意到由于所有边权未知的边的起点均相同，又有所有边权均非负，这意味着我们不可能经过一个顶点超过一次，所以我们可以将最短路分为 $K+1$ 类：

• 第 $1 \leq i \leq K$ 类经过了第 $i$ 条未知边
• 第 $0$ 类没有经过任何未知边。

注意到对于第 $0$ 类，我们可以直接删掉所有未知边跑最短路，其余第 $i$ 类最短路一定形如 $S_j \to A_i \to B_i \to T_j$ 的形式，同样可以删掉所有未知边来跑。

因此，我们只需要让 Spy 预先跑出所有询问的答案，并将询问类型发送给 Participant 即可。

一共需要 $Q \cdot \left\lceil \log_2 (K+1) \right\rceil = 60 \times 3 = 180$ 个 bit，刚好可以在子任务 2 中获得 11 分，共获得 16 分。

算法 3

注意到算法 2 中，一组询问只需要发送一个 $0 \sim 5$ 内的数，却要使用 3 个 bit，有些愚蠢。我们可以仿照进制转换，将这个 $60$ 位的 $6$ 进制数直接转成 $2$ 进制数发送过去，然后再转换回来即可。

如果懒得写高精度，也可以直接用 8 个 bit 压 3 个数（$6^3 = 216 < 2^8 = 256$），这样需要 $20 \times 8 = 160$ 个 bit，在子任务 2 中获得 15 分，共获得 20 分。

如果写了高精度，那么 $6^{60} = 48873677980689257489322752273774603865660850176$，而注意到 $2^{156} = 91343852333181432387730302044767688728495783936$，因此我们只需要发送 $156$ 个 bit，在子任务 2 中获得 17.4 分，共获得 22.4 分。

当然事实上我们可以利用长度作为信息，只发送 $155$ 个 bit，获得额外的 0.6 分，这样就可以在子任务 2 中获得 18 分，共获得 23 分。

算法 4

我们设 $f(i, a, b)$ 表示对于第 $i$ 个问题，第 $a$ 种最短路和第 $b$ 种最短路哪个更短。

那么对于 Participant 而言，他只需要对所有 $0 \leq i < Q, 0 \leq a,b \leq 5$，都得到 $f(i,a,b)$ 的值，那么问题就解决了。

考虑对于以上三组询问中，方案 $1$ 比方案 $2$ 优秀，当且仅当 $d_1+e_1+f_1 < d_1 + e_2 + g_1$，即 $e_1 - e_2 < g_1 - f_1$。同理，我们可以发现，对每个 $0 \leq i < Q$，方案 $a$ 比方案 $b$ 优秀，都可以表示成不等式 $e_a - e_b \leq X_{i,b}-X_{i,a}$ 的形式。注意到双方事实上都知道 $X_{i,b} - X_{i,a}$ 的值，于是我们可以对所有 $\binom{6}{2} = 15$ 种不同的 $0 \leq a < b \leq K$，计算出 $X_{i,b} - X_{i,a}$ 的值并将他们排序。随后由 Spy 发送给 Participant 一个值 $R_{a,b}$，表示从大到小 $R_{a,b}$ 个 $X_{i,b} - X_{i,a}$ 是能满足 $e_a-e_b \leq X_{i,b}-X_{i,a}$ 的最后一个 $i$。这样我们便成功发送了 $f(i,a,b)$ 的值。

总共有 $15$ 个 $(a,b)$，每个需要发送一个 $0 \sim Q$ 内的值，共需 $\frac{K(K+1)}{2} \left\lceil\log_2 (Q+1)\right\rceil = 15 \times \left\lceil \log_2 61 \right\rceil = 90$ 个 bit。可以在子任务 2 中获得 43 分，共获得 48 分。

当然你也可以结合算法 3 中的优化方法，$61^{15} = 602486784535040403801858901 < 2^{89}$，因此只需要发送 $88$ 个 bit 即可，获得额外的 0.3077 分。

算法 5

注意到算法 4 的本质即为，我们不断选取 $a,b$，并比较有多少组询问中 $a$ 优于 $b$，基于此将所有询问分成两组。

Spy 将所有的限制均发送给了 Participant，但事实上双方可以预先商定策略，因此我们不妨固定选取 $a,b$，并考虑分组的过程：

注意到对于固定的 $a_i, b_i$，我们发送的本质即为 $m$ 的值。虽然参与排序的段很多，但由于 $m$ 一定恰好落在了一组询问区间中，因此事实上，只有一组询问区间的 $m$ 是有用的，其余的 $m$ 并不会划分出更多的区间：

注意到我们已经预先将询问排序，因此当在进行到第 $i$ 回比较时，在此回合参与比较的询问是一段连续的区间 $[L_i, R_i]$，考虑不发送 $m$ 的值，而是发送 $m-L_i$ 的值。这样的问题是我们不知道 $m$ 落在了哪一个区间中，因此我们考虑修改 $a,b$ 的顺序。若干个随机算法需要发送 $70 \sim 80$ 个 bit，可以得到 $55 \sim 78$ 分。

不妨假设在第一回，我们进行了询问 $(x, y)$，考虑在第二回进行 $(x, z)$。注意到由于我们已经确定了 $x$ 最优的范围，因此只有 $z \in [L_1, R_1]$ 时，$m_{xz}$ 的值才有意义，否则一定是要么整个区间被划给了 $x$（等价于 $x=R_1$），要么是整个区间被划给了 $z$（等价于 $x=L_0$）。

因此我们直接这样进行比较，就只需要发送 $m_i-L_i$ 的值。

我们可以通过一边预处理到此时的 $[L_i, R_i]$，一边计算出所需位数 $d$，就可以提取出接下来的 $d$ 位用于存储 $m_i-L_i$。

通过分析，发现当每段被划分的相等时，所需的代价最多，此时代价为： $$\sum_{i=1}^{K} i\left\lceil\log_2 \frac{Q+1}{i}\right\rceil$$ 总共需要 $64$ 个 bit，期望得分 $100$ 分。

Public Round #6 将在 2022 年 7 月 3 日 8:00 举行！比赛将进行 5 小时，共 3 道题，OI 赛制。

本次比赛的题目难度约为 NOI D1，所有题目都有部分分。

本场比赛有一道通信题，请不熟悉的选手预习题目特点和提交格式！

本次模拟赛的搬题人为 p_b_p_b, cdw, Qingyu，组题人为 p_b_p_b 。

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

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

• 搬题人：
  • A：he_____he
  • B：p_b_p_b
  • C：hehezhou
• 组题人：hehezhou
• 题解：hehezhou, p_b_p_b

双向奔赴

题目来源：

• XXI Open Cup named after E.V. Pankratiev. Grand Prix of Korea, Problem C

QOJ 链接：https://qoj.ac/contest/776/problem/3301

一个强连通分量一定可以由如下过程产生：

1. 初始有一个集合 $S$，包含其中的一个点。
2. 每次选择一条链 $u\rightarrow v_1 \rightarrow v_2\rightarrow\cdots\rightarrow v_k\rightarrow w$，其中 $u,w\in S$ ，将 $v_1,v_2,\cdots,v_k$ 加入到 $S$ 中。

对于 $(i,j)$ 的无向边，我们可以默认代价较小的那个方向的有向边一定出现，然后将代价同时减去这个较小值。我们可以状压 dp 这个过程，用 $d_S$ 表示集合变为 $S$ 的最小代价。定义 $f_{S',v,w}$ 表示目前考虑了一条 $u$ 到 $w$ 的链，同时这条链已经走到了 $v$ 点，还剩余 $v$ 到 $w$ 的部分没有完成， 表示 $S'$ 并上这条链中 $u$ 到 $v$ 的部分，此时的最小代价。可以直接枚举链上 $v$ 的下一条边转移。需要注意不能同时包含连接两个点的两个方向的有向边。时间复杂度 $O(2^nn^3)$。

循环移位

题目来源：

• Petrozavodsk Winter 2022. Day 7. Gennady Korotkevich Contest 6, Problem I
• XXII Open Cup named after E.V. Pankratiev, Grand Prix of Gomel, Problem I

QOJ 链接：https://qoj.ac/contest/825/problem/2624

经过打表，发现满足条件或不满足条件的排列都看不出任何性质。

那就只能暴力一点，用 $O(2^{n-1})$ 的时间枚举每个 $i$ 是否有 a[i]<a[1] ，以此获得一个大小关系树。然后再计算有多少个满足条件的排列也同时满足这个大小关系树。

注意到如果当前这个 a[i] 在之前已经被考虑过，那么必然有 a[i]>a[1] 。那么感性理解一下，随着 $i$ 增大，a[i] 从未被考虑过的概率越来越小，从而可能的大小关系树的数量会远小于 $2^n$ 。

写一个带剪枝的 dfs ，发现 $n=42$ 时只有 $\approx 10^9$ 种可能，因此直接暴力打表即可。

和平共处

题目来源：

• RuCode 2020 Division A+B Championship Round, Problem I
• XX Open Cup named after E.V. Pankratiev, Grand Prix of Moscow, Problem I

QOJ 链接：https://qoj.ac/contest/923/problem/4219

题解的做法几乎没有用到平面黑白点的任何性质。

利用一些二分图匹配的性质，不难发现题意等价于求这张二分图的字典序最小的最大匹配，字典序的定义为匹配白点集合的字典序，下面简称字典序最小最大匹配为最优匹配。

我们给出结论：如果能在 $T(n+m)$ 的时间复杂度内计算出左右部分别为 $n,m$ 个点的二分图的最小割以及方案，那么可以在 $T(n+m)\log {n}$ 的时间内计算出左部的最优匹配。这里最小割的定义为：设左部和右部分别为 $L,R$，一个割由左集和右集 $X,Y$ 组成，满足 $X\bigcap Y=\emptyset,X\bigcup Y=L\bigcup R$ 并且 $X\bigcap L$ 和 $Y\bigcap R$ 之间不存在边。割的大小定义为 $X\bigcap R+Y\bigcap L$，令 $X_l=X\bigcap L,X_r=X\bigcap R,(Y_l,Y_r)$ 同理。

具体的做法如下：考虑过程 $F(S_1,S_2,S_3)$ 表示你需要求出左部为 $S_1\bigcup S_2$，右部为 $S_3$ 的最优匹配，并且 $S_2$ 中所有元素小于 $S_1$ 中元素且一定在最优匹配中，答案就是 $F(L,\emptyset,R)$。

将 $S_1$ 按照元素大小划分成大小相同的两部分，元素较小和较大部分分别设为 $X,Y$。求出 $(S_2\bigcup X,S_3)$ 的一个最小割，左集和右集分别设为 $(A_l,A_r),(B_l,B_r)$。

引理 $1$：$(B_l\bigcup Y,B_r)$ 的最优匹配一定包含 $B_l$。

首先 $(B_l,B_r)$ 的最大匹配大小为 $|B_l|$，因此包含 $B_l$，注意到 $Y$ 中所有元素大于 $B_l$ 中元素，由匈牙利算法可得，$(B_l\bigcup Y,B_r)$ 的最优匹配包含 $B_l$。$\square$

引理 $2$：$(X\bigcup S_2,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l,B_r)$ 的最优匹配组成。

两者之间的边只存在于 $A_r$ 和 $B_l$ 之间，这些边不可能成为匹配边，否则这个匹配大小达不到 $|A_r|+|B_l|$。

引理 $3$：$(S_1\bigcup S_2,S_3)$ 的最优匹配由 $(A_l,A_r)$ 和 $(B_l\bigcup Y,B_r)$ 的最优匹配组成。

考虑在 $(X\bigcup S_2,S_3)$ 的最优匹配的基础上，将 $Y$ 中元素逐个加入，模拟找增广路的过程，由于 $Y$ 中元素较大，这样得到的结果就是最优匹配。

每次找到的增广路不可能包含 $A$，因为 $A_l$ 只和 $A_r$ 相连，$A_r$ 所有点均已匹配且匹配点均在 $A_l$，一旦增广路走到 $A$ 就无法出来且找不到未匹配点。因此每个点加入后，$A$ 内部的匹配不会改变。$\square$

对 $(A_l,A_r)$ 的求解直接调用 $F(A_l\bigcap S_1, A_l\bigcap S_2, A_r)$。对 $(B_l\bigcup Y,B_r)$ 的求解调用 $F(Y,B_l,B_r)$。注意到每次递归，每个点恰好会递归至一侧，并且 $S_1$ 的大小减半。递归树仅有 $\log n$ 层，复杂度 $T(n+m)\log n$。

考虑求出一组最小割：这可以贪心解决，具体的，先求匹配，将所有点按照 $x$ 轴排序并枚举，加入黑点时将 $y$ 坐标加入集合，加入白点时找集合中最大的不超过当前白点 $y$ 坐标的黑点，匹配两个点并将黑点从集合中删去，如果找不到则认为匹配不上。然后从所有未匹配的白点开始 bfs，将所有走到的黑点以及他们对应匹配的白点不断加入队列，这可以通过线段树优化建图完成，因此 $T(n)=O(n\log n)$。

总复杂度 $O(n\log^2 n)$。

• 搬题人：
  • A, B, C：hehezhou
• 组题人：hehezhou
• 题解：hehezhou

因为忘记宣传了，pjudge 复活的第一场比赛竟然没什么人打……后面还会有比赛，希望大家帮忙宣传宣传 >_<

赌徒

题目来源：

• Petrozavodsk Summer 2021 Day 7: MIPT Contest, GP of Dolgoprudny, Problem G
• XXII Open Cup named after E.V. Pankratiev, Grand Prix of Dolgoprudny, Problem G

QOJ 链接：https://qoj.ac/contest/697/problem/1880

两面一定是 $1$ 或出现过的数字，因此可以离散化。

如果不考虑买硬币的代价，两面是独立的，先求出一面是 $a$ 时的收益 $S_a$，这可以简单通过前缀和得到。

接下来需要求出 $\max_{a,b}\{S_a+S_b-ab\}$，考虑固定 $a$，发现只有在凸包上的 $b$ 有用，反之亦然。因此只保留凸包上的点，继而可以双指针。

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

猜猜看

题目来源：

• Petrozavodsk Summer 2021. Day 1. Kyoto U Contest, Problem J

QOJ 链接：https://qoj.ac/contest/691/problem/1813

不难发现两次询问 $1$ 的用途是确定询问 $2$ 无法区分的 $1,2$ 和 $n-1,n$。

当 $n=4$ 时，可以通过 $4$ 次询问来得到两个较小的数和两个较大的数。

当 $n$ 更大时，不妨考虑增量法，逐个点加入，维护出 $1\sim i$ 中的最小值及次小值的下标 $l_1,l_2$，最大值及次大值的下标 $r_1,r_2$，次小值 $L$ 和次大值 $R$。注意你暂时无法区分 $l_1,l_2$，$r_1,r_2$ 同理。

先询问 $x=Q_2(l_1,r_1,i+1)$，接下来有若干情况：

1. $L\lt x\lt R$，说明 $a_{i+1}=x$。
2. $L=x$，说明 $a_{i+1}\lt a_{l_1}=x$，将 $l_1$ 更新为 $i+1$ 并询问出新的 $L$，$R=x$ 同理。
3. $x\lt L$，说明 $a_{i+1}\lt a_{l_2}=L$，将 $l_2$ 更新为 $i+1$，$L$ 更新为 $x$，$R\lt x$ 同理。

最后使用两次操作 $1$ 区分 $l_1,l_2$ 及 $r_1,r_2$ 即可。

第 $2$ 类询问次数 $2n-4$。

到底有没有九

题目来源：

• Petrozavodsk Summer 2021 Day 7: MIPT Contest, GP of Dolgoprudny, Problem B
• XXII Open Cup named after E.V. Pankratiev, Grand Prix of Dolgoprudny, Problem B

QOJ 链接：https://qoj.ac/contest/697/problem/1875

算法 1

如果尝试直接求出第 $n$ 个 $x$ 满足 $x\times (10^k-1)$ 不包含 $9$ 并没有比较好的转化，但是可以考虑求出第 $n$ 个 $x$ 满足 $x$ 的十进制表示不包含 $9$ 并且 $x$ 是 $10^k-1$ 的倍数，答案即为 $\frac{x}{10^k-1}$。

考虑逐位确定答案，答案的位数是 $O(k+\log n)$ 的，因此可以将问题转化为 $O(k+\log n)$ 次询问形如 $\overline{x_1x_2x_3\cdots x_k??\cdots ?}$ 的数有多少种方案将 $?$ 替换为 $0\sim 8$ 使得这个数是 $10^k-1$ 的倍数。

一个数是 $10^k-1$ 的倍数当且仅当从低往高位，每 $k$ 位划为一段，所有段的和是 $10^k-1$ 的倍数。

因为段数很少（设为 $l$），不妨先枚举这个和，即 $[i(10^k-1)]_{i=0}^{l}$。接下来按照在段中的位置，从低往高数位 dp 即可。

时间复杂度：$O(\text{poly}(\log n+k))$，视实现而定。

std 的复杂度为：$O(\log^4 n+k^2)$ 。

算法 2

一个暴力。

把 $x\times (10^k-1)$ 拆分为 $x\times 10^k$ 和 $x$ 相减。

不难发现，如果无脑从低到高 DP ，需要记录低位的 $k$ 个位置分别选了什么。

直接二分答案，然后暴力 DP ，复杂度 $O(10^k(k+\log n)^2)$ 。

算法 3

另一个暴力。

考虑 $k$ 较大怎么办。设 $y=x\times (10^k-1)$ ，那么 $y_i$ 只和 $x_i,x_{i-k}$ 以及是否有退位有关。（这里 $x_i,y_i$ 分别表示 $x,y$ 十进制下的第 $i$ 位。）

除了退位以外，不同的 $i\bmod k$ 是独立的！

毛估估一下，答案长度应该不会比 $k+\log n$ 大多少。所以可以把 $x$ 每 $k$ 位分一段，设分成了 $l$ 段。

那么可以先枚举 $2^l$ 种段间退位的情况，然后所有段一起从低到高 DP ，记录目前的退位情况即可。

复杂度大概是 $O(4^l(k+\log n)^2)$ 吧。

算法 4

把算法 2 和算法 3 拼起来即可。

• 搬题人：
  • A：cdw
  • B：Qingyu
  • C：p_b_p_b, Qingyu
  • D：p_b_p_b
  • E：hehezhou
• 组题人：chenkuowen01
• 题解：cdw, Qingyu, p_b_p_b, hehezhou

简单数据结构

题目来源：

• Petrozavodsk Winter 2022. Day 2. KAIST Contest + KOI TST 2021, Problem A
• XXII Open Cup, Grand Prix of Daejeon, Problem A

QOJ 链接：https://qoj.ac/problem/2552

$u_x+v_x\ge u_y+v_y$ 当且仅当 $u_x-u_y\ge v_y-v_x$，以 $u_x-u_y$ 和 $v_y-v_x$ 分别作为下标，用线段树维护。时间复杂度 $\mathcal O(Q\log Q)$。

情报传递

题目来源：第 14 回日本情報オリンピック　春季トレーニング合宿 (JOISC 2014/2015), Day 3, Task 道案内 (Navigation)

QOJ 链接：https://qoj.ac/problem/1212

算法 1

对每个点记录其到终点的距离 $d_i$。容易发现，如果此时我们所在的点 $S$ 的 $d_S=0$，则我们所在的点即为终点，否则一定是前往 $d[\cdot]$ 值最小的点。

该算法所需 $m\leq n$，期望得分 $0.00008$ 分。

算法 2

容易注意到 $d[\cdot]$ 的编码是连续的，即对于任意条边 $(x,y)$，定有 $|d_x-d_y| = 1$，因此 $S$ 的邻居中一定恰好有一个点满足 $d[\cdot] = d[S] - 1$。注意到我们只需要记录 $d[\cdot ] \bmod 3$ 的值，即可得到对应的点是哪一个，因此我们只需要记录每个点到终点的距离模 $3$ 的值即可。

该算法所需 $m=2$，期望得分 $44.44444$ 分。

算法 3

注意到我们的目标是向终点走，因此如果我们把这棵树视为以 $T$ 为根的一棵有根内向树，则我们只需要找到每个点所对应的唯一的出边。

由于在询问过程中我们唯一能确定的信息即为起点 $S$ 出边所到的点的编号，因此我们尝试来使用编号对每条边随意定向，例如记 $\mathrm{dir}(x,y) = \begin{cases} x \to y & x < y \\ y \to x & \mathrm{otherwise}\end{cases}$。

此时有一些边的定向正确，一些边的定向不正确。我们为 $T$ 随意赋予一个标号，并从 $T$ 开始 DFS 整棵树。在对 $X$ DFS 时，如果接下来访问到的点 $Y$ 的定向不正确（即 $Y < X$，初始定向为 $Y \to X$），则我们将 $Y$ 的标号置为与 $X$ 不同，否则将其标号置为与 $X$ 相同。

这样，当一条边的两端点被赋予的标号相同时，这条边的方向即为 $\mathrm{dir}(x,y)$，否则即为其取反后的方向。我们便可以在询问过程中复原出边的方向。

该算法需要 $m=1$，期望得分 $100.0$ 分

运算符

题目来源：

• Benelux Algorithm Programming Contest 2021, Problem G
• United Kingdom and Ireland Programming Contest 2021, Problem G
• Petrozavodsk Winter 2022. Day 4. Almost Northern Contest

QOJ 链接：https://qoj.ac/contest/822/problem/2286

运算符太多了，胡乱询问肯定是问不出来的。所以考虑从后往前依次确定。

容易想到一个 $O(n)$ 的暴力做法：在尝试确定 $\text{op}_k$ 时，令 $a_0=\cdots=a_{k-1}=0,a_k=\cdots=a_n=1$ 即可。

如何能够一次多确定几个呢？一种思路是使用奇奇怪怪的 $k$ 进制编码，但是为了不被 $\bmod {(10^9+7)}$ 扰乱，能确定的位数是比较有限的。

更好的做法是尝试充分利用 $10^9+7$ 种返回值：因为 $10^9+7\approx 2^{30}$ ，所以只要随机 $16$ 个数放在最后，就会有比较大的概率能通过返回值唯一确定最后 $15$ 个操作符。在询问前预处理出一组合法的 $16$ 个数即可。

仙人掌

题目来源：

• Petrozavodsk Winter 2022 Day 7: ICPC Camp Day 2, Gennady Korotkevich Contest 6, Problem E
• XXII Open Cup, Grand Prix of Gomel, Problem E

QOJ 链接：https://qoj.ac/contest/825/problem/2620

先使用 tarjan 算法把仙人掌上的有向环缩起来，获得一个 DAG 。

考虑在一般的 DAG 上求传递闭包大小会遇到的问题：如果直接使用 $dp_x=1+\sum_{(x,v)\in E} dp_v$ ，那么每个点会被计算路径条数次。

但是仙人掌并没有比树多太多边，也就是说它非常稀疏，那么被多算的次数就不是很多。

设 $f_x$ 表示 $x$ 能到达的点数（不算重），那么仍然考虑 $f_x=1+\sum_{(x,v)\in E}f_v$ 会多算什么。注意 $f_v$ 都是正确的，因此只会有一些点被算了两次，把它们减掉就行了。

哪些点被算了两次呢？只有在 $x$ 所在的一个环恰好可以被拆成两条路径 $x\to v_1\to \cdots\to y,x\to v_2\to \cdots\to y$ 时，$f_y$ 会被算两次。因此只要对于每一个这样的环，把 $f_y$ 减去即可。

复杂度 $O(n)$ 。

2048

题目来源：Petrozavodsk Summer 2021. Day 4. Shanghai ICPC Camp 2021 Onsite Day 1 by PKU

QOJ 链接：https://qoj.ac/contest/694/problem/1849

请注意原题的题意有误。

考虑题意等价于这个过程：维护一个栈，如果栈的大小达到 $n$ 游戏结束，否则每次按照分布随机一个 $x$，尝试插入 $x$，与栈顶相同则弹出栈顶并尝试插入 $x+1$，以此类推。

考虑类似这么设计 $dp$ 状态：一个大小限制为 $i$ 的栈，栈底已经有了一个 $j$，当栈大小达到限制或栈底变为 $j+1$ 时，得分的期望以及栈底变为 $j+1$ 的概率。

这么设计状态的好处是：对于某个栈，截止到栈被填满或当前栈顶对应元素变化时，概率以及得分期望仅与栈顶元素以及剩余空位数有关，而与剩余元素无关。

那么考虑转移，重新具体地设计状态：设状态 $A_{i,j},B_{i,j}$ 表示大小为 $i$ 的空栈不断操作，某一时刻栈中只有元素 $j$ 的概率，以及此时总得分期望，$C_{i,j}$ 表示大小为 $i$ 的空栈，不断操作后栈被填满，并且栈底为 $j$，此时总得分期望，$D_{i,j}$ 表示大小为 $i$ 的栈，栈底已经填了 $j$，不断操作直到栈被填满，此时总得分期望。注意这里的期望均指条件成立前提下的期望乘上条件被满足的概率。

这么设计状态实际上对应了三种情况：接下来填入一个较小元素最终栈底被合并，接下来填入一个较小元素最终栈被填满，接下来填入一个较大元素最终栈被填满。

那么转移实际上就比较简单了：

• $A_{i,j}=p_j+A_{i,j-1}A_{i-1,j-1}$

• $B_{i,j}=A_{i,j-1}B_{i-1,j-1}+B_{i,j-1}A_{i-1,j-1}+A_{i,j-1}A_{i-1,j-1}2^{j}$

• $C_{i,j}=B_{i,j}(1-A_{i-1,j})+A_{i,j}(\sum_{k=0}^{j-1}C_{i-1,k}+\sum_{k=j+1}p_k D_{i-1,k})$

• $D_{i,j}=\sum_{k=0}^{j-1}C_{i-1,k}+\sum_{k=j+1}p_k D_{i-1,k}+A_{i-1,j}(D_{i,j+1}+2^{j+1})+B_{i-1,j}$

最终答案即为 $\sum_i p_i D_{n,i}$。

简单前缀和优化即可做到 $O(n^2+nm)$。

Public Easy Round #1 将在 2022 年 4 月 23 日 8:00 举行！比赛将进行 5 小时，共 5 道题，OI 赛制。

著名 OIer jiangly 曾经说过，“你不过 T1 你过啥题啊 你不过题你打锤子啊”。为了训练选手迅速通过 T1 的能力（以及过不掉 T1 时调整心态的能力），本次比赛的题目难度均为省选 T1-T1.5 ，并且大多数题目不设部分分。

本次模拟赛的搬题人为 cdw, p_b_p_b ，组题人为 hehezhou ，验题人为 AutumnKite, chenkuowen01 。

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

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