• 搬题人
  • 饼干：Wu_Ren
  • 消愁：hehezhou
  • 养鸡：flower
• 组题人：p_b_p_b
• 题解：别急，别急，flower

饼干

来源：

• Petrozavodsk Summer 2020 Day 5: JAG Summer 2019+, Problem L
• https://qoj.ac/contest/505/problem/1346

Tutorial by Wu_Ren.

考虑如果仍然需要补魔，那么先施法再补魔一定比先补魔再施法更劣。

那么我们每次一定是，先施法然后补满，直到某次我们施法完之后，把魔补到剩下消耗的总和，然后依次施完。

那么这个过程就相当于我们每个魔咒变成 $a_i$ 个物品，第 $j$ 个物品权值是 $j$，然后我们有 $m$ 次机会把某个魔咒里权值最小的那个物品删去，我们称这个为操作一。

我们要求最后权值和最小。

然后吃饼干就是有 $k$ 次机会把某个魔咒里权值最大的那个物品删去，我们称这个为操作二。

仔细分析一下，我们就是每次对最大的 $a_i$，使用 $a_i$ 次操作一（不足就全用了）。等所有操作一用完后，贪心地使用操作二即可。

复杂度 $O(n\log n+m)$ 或 $O(n\log n)$。

消愁

来源：

• Petrozavodsk Summer 2021 Day 3: GP of IMO, Problem J
• https://qoj.ac/contest/693/problem/1839

别急

养鸡

来源：

• Petrozavodsk Summer 2022. Day 7. HSE Koresha Contest, Problem A
• https://qoj.ac/contest/1016/problem/4878

Tutorial by flower.

显然是个二分图最大流的模型，接下来用用流的语言的来描述问题。

首先有个贪心做法。每次从 $n$ 扫到 $1$ 遇到一个区间的 $r$ 就加入这个区间，然后对于每个点尽量流 $l$ 最大的。

当 $l, r$ 递增的时候。可以发现上述贪心做的事情是，先加入的区间尽量先流，与 $l$ 具体啥样无关。如果从$n$担心到$p$，再从 $1$ 贪心到$p-1$。两侧的用到的区间是一个前缀和一个后缀。如果总和不爆那就不会冲突，也就是说答案是 $\min(lmaxflow + rmaxflow, \sum_{l_i \le p \le r_i} f_i)$。其中 $f$ 是区间的流量

计算 $rmaxflow$ 可以用 hall 定理，令 $s_i = \sum_{l_j \le p \le r_j \le i} f_j - \sum_{j = p}^{i} a_p $，其中 $a$ 是右侧一个点的流量。

那么答案就是所有区间流量和减去 $\max s_i$，用线段树维护即可。

考虑贪心在做的事情是保证右侧为最大流的情况下，尽量的选 $l$ 最大的，只要我们求出了每个点右侧的情况，那么把每个区间的剩余流量扔左侧跑个最大流即可。

考虑一个 $s_i$ 的含义是：$p$ 到 $i$里至少要浪费 $s_i$ 的区间的流量扔到左侧。把$s$的前缀最大值位置拎出来是 $i_1, i_2, \cdots, i_k$。

考虑 $p$ 到$i_k$ 里优先级最小（$l$ 最小）的区间假设在位置 $x$。令 $i_t \le x$ 且$t$最大，那么这个前缀要浪费$s_{i_t}$而总共要浪费$s_{i_k}$，那么就直接给这个区间的左侧部分增加 $\min(f, s_{i_k} - s_{i_t})$ 的流量，因为这些一定是被浪费的。

考虑直接线段树暴力维护上述过程，下面证明操作次数不超过$O(n\log n)$。

需要对于$s$ 数组做的事情是后缀加和把最大值和降低为非严格最大值。

考虑在线段树的结构，势能为有多少个节点的区间最大值来自右子树（如果相等认为在左子树）

那么每次操作都会使得使能少$1$（$i_k$, $i_t$ 在线段树的 lca），后缀加只会影响$\log n$个区间的相对顺序。 算上线段树操作的时间复杂度是 $O(n\log^2 n)$。

Public Round #8 将在 2023 年 3 月 19 日 8:00 举行！咕咕咕了大半年之后， PR 又回来了！

比赛将进行 5 小时，共 3 道题，OI 赛制。

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

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

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

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

• 搬题人
  • 青鱼和序列：p_b_p_b
  • 青鱼和怪兽：Qingyu
  • 青鱼和区间：alpha1022
  • 青鱼和游戏：ShanLunjiaJian
• 组题人：Qingyu
• 题解：alpha1022, Qingyu, ShanLunjiaJian, p_b_p_b

青鱼和序列

来源：

• 2022 China Collegiate Programming Contest (CCPC) Guilin Site， Problem C
• https://codeforces.com/gym/104008/problem/C

Tutorial by p_b_p_b.

注意到使用操作二会使得序列变成回文串，于是接下来使用操作一和操作二就没有任何区别了。

因此直接枚举第一次使用操作二是在第几轮，以及特判每次都用操作一的情况，即可得到答案。

事实上还可以注意到，只要用过操作二，无论操作序列如何，最终答案都相等，所以枚举也可以省去。

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

青鱼和怪兽

来源：

• Petrozavodsk Summer 2014. Day 4. Moscow SU SG Contest, Problem J

TBD

青鱼和区间

来源：

• CSAcademy Round #35, Counting Quests
• https://csacademy.com/contest/round-35/task/counting-quests/

Tutorial by alpha1022.

题意就是要求用询问区间区分出每道题目。

记覆盖 $i$ 的区间集合为 $S_i$，则所求即 $S_i$ 互不相同，但这并不好直接计算。

接下来我们注意到一个重要性质：对于任意方案，不会存在 $i_1 < i_2 < j_1 < j_2$ 使得 $S_{i_1} = S_{j_1} \ne S_{i_2} = S_{j_2}$。

这个性质使我们联想到括号序列。因此，考虑如下的构造：维护指针 $i$，初始时 $i=1$，每次取 $\max \{ j \mid S_i = S_j \}$，并令 $i=j+1$。注意到，所有区间要么是在某个 $[i+1, j-1]$ 内部，要么是以某个 $i$ 为左端点，某个 $j$ 为右端点。并且，我们至少可以保证可以将每个数区分到某个区间中。

注意到，若确定了分段方案 $[i_1, j_1], [i_2, j_2], \dots, [i_k, j_k]$，则段内的区间可以任意选取，而跨过段的区间选择的方案数就是我们所要求的答案：选择若干 $[1, k]$ 的子区间区分出所有 $k$ 道题的方案数。

因此我们考虑一个容斥：用 $2^{\binom{k+1}2}$ 减去不能区分出所有题目的方案数，同时维护一个背包数组用来计量分段的方案数，由此即可递推得到答案。时间复杂度 $O(n^3)$。

这还是一个生成函数的复合方程，借助拉格朗日反演可以做到 $O(n \log n)$。

青鱼和游戏

来源：

• Polish Olympiad in Informatics 2016, Not Nim
• https://szkopul.edu.pl/problemset/problem/M5CruI5eCu8elnNFHuiXBrvV/site/

Tutorial by ShanLunjiaJian.

算法0

显然青鱼的每一步都会清空一堆。

我们计算青鱼的步数$x$，那么答案就是$2x-1$。

首先考虑一下这个游戏会如何进行。青鱼一旦操作一堆$(x,y)\rightarrow (x,0)$，缺头鱼必然跟着把这一对摊平成$(\lfloor\frac{x}{2}\rfloor,\lceil\frac{x}{2}\rceil)$。如果一对堆都空了，缺头鱼不得不把一步用到别的某对堆$x^\prime,y^\prime$，那么假设$x^\prime\leq y^\prime$，他必然会把这对堆变成$x^\prime+1,y^\prime-1$。

我们将青鱼把一对中大的拿走这个操作称为拿，缺头鱼把一对中有一个$0$的摊平称为摊，缺头鱼把两堆大小相同的一对搞的不同称为炸。如果只有拿和摊，可以发现答案就是$2\sum\limits_i(\lg a_i+1)-1$。炸可能减少步数，并且可以发现如果减少了只可能是减少一步。

看看二进制，设一对是$a,a$，如果$a$的二进制表示全$1$，那么一轮炸-拿-摊可以把$a$的长度减少$1$，如此一直进行$a$的长度次就能在这一对上减少一步，但一旦中断就不可能再减少一步了。如果$a$中有$0$，那么先使用若干轮拿-摊直到全$1$，此时仍然可能减少一步，因此这样做必然不劣。

于是青鱼在一开始会把每一对都搞成全$1$的形状，然后两鱼每次都会选择最长的那一对操作，缺头鱼如此选择是因为最长的最不容易产生作用，青鱼则要逼缺头鱼往短的上走，这个还是比较自然的。青鱼一旦先手操作一堆就会操作干净，因为它上面不可能再省下步数了，而缺头鱼先手操作一堆会让这一堆长度减少$1$。最后每一堆长$1$的都能贡献，不过如果青鱼先手则有一堆不行。

此时我们可以对于每个前缀连续$1$个数求出它的出现次数，然后对着这个数组模拟，复杂度$O(q(n+\log v))$。结合两个答案只跟区间长度相关的特殊性质，可以通过前$6$个测试点。

算法1

当然可以用数据结构维护这个出现次数！前缀和可以通过测试点$7,8$，BiT简单卡卡常可以通过测试点$9,10,11$。

这个做法空间是$O(n\log v)$的，为了砍掉这个$\log v$，我们对底层按$\log v$大小分块，维护块间的BiT，时间复杂度不变而空间变为线性，可以通过$12,13,14$，提交记录，卡卡常大概能过$15,16$。使用avx可能可以直接草过去。

算法2

观察模拟的代码。这是搬题人写的一份代码 :

const int B=40;

inline int query(int l,int r)
{
    int c[B+1]={0},p[B+1]=0,g=0;
    for(int i=l;i<=r;i++) c[__builtin_clzll(~(a[i]<<__builtin_clzll(a[i])))-1]++,g+=(65-__builtin_clzll(a[i]));
    for(int i=B;i>0;i--) c[i-1]+=(c[i]+p[i])/2,p[i-1]=p[i]^(c[i]&1);
    return 2*(g-(c[0]-!p[0]))-1;
}

其中$c_i$表示前缀连续$1$个数为$i-1$的数的个数；$p_i=0/1$表示进行到$c_i$中的对时的青鱼是先/后手，$g$是不考虑炸的答案。可以发现这里如果把循环各轮的$c,p$分别倒过来组成一个二进制数，我们就是计算了$c$和$p$的和，不过$c$的每一位可以$>1$，并且进到$B$位就停止。接下来使用这个定义的$c,p$(也就是说它们都是倒过来的)。

继续考虑$p$是什么，可以发现它就是$c+p$上"经过"每一位的值的奇偶性的前缀和，也就是说如果向第$i$位发生了一次进位，对$p_{j\geq i}$的贡献就是$\operatorname{xor}$上一个$1$。注意到如果$c$的某位值$\geq 2$则必然向下一位进位，考虑一下发现我们在$c$上做完这些进位，做法就是直接加起来，最后再跑一遍上面的模拟即可。用BiT支持单点修改区间求和，复杂度$O(q(\log n+\log v))$。提交记录。

算法2.5

怎么砍$\log v$?下面这个做法由 hehezhou 发现。喝喝粥好闪，拜谢喝喝粥！

考虑扫过某个$c_i=1$的$i$时会发生什么，发生进位当且仅当$p_i=1$，否则这一位保留$1$，$p_{i+1}$变成$1$。如果$p_i=1$，那么$p_{i+1}=0$，于是$c_{i+1}=1$的话它得到$i$的进位而继续进位，否则它必然不会进位。于是我们知道经过连续的一段$1$之后$p$又变回$1$，而类似$1111$这样的东西它的$c+p$是$00001$。也就是说它不会改变第一个$1$，而在经过第一个$1$之后它的效果就是把每个$1$连续段清空并把连续段后一位赋为$1$。

我们只关心$c_B-\operatorname{not}p_B$(不考虑$B$及以上位的初值)。讨论一下 :

• 如果$c$全$0$，那么$c_B=p_B=0$。

• 如果$c_{B-1}=0$，那么$c_B=0,p_B=1$。

• 如果$c_{B-1}=1,p_{B-1}=0$，那么$c_B=0,p_B=1$。

• 如果$c_{B-1}=1,p_{B-1}=1$，那么$c_B=1,p_B=0$。

只有第一个case的结果是$1$，所以我们知道$c_B-\operatorname{not}p_B=1$当且仅当$c$全$0$。这样就$O(1)$了。提交记录。

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