2020.9 月赛题解

Once edited 4 年，6 月前

花絮

• 久违的六个题月赛。
• 全场几乎没人提问，是否侧面反映出题目细致程度有所提高（出题组先自恋五秒）。

Problem A 击鼓传花

First Solved: Yewenw

首先肯定需要转换一下，把起点变为 $0$，那么问题就转化为，求最小的自然数 $x$ 使得 $l\le ax\mathrm{mod}n\le n$。当然在转换后有可能 $l＞r$ ，此时我们对 $[l,n)$ 和 $[0,r]$ 分开做，再对两个答案取最小值就行了。

首先判断无解的情况：$a=0$ 且 $l\ne 0$ 显然无解。当 $d=gcd(a,b)$ 则 $ax\mathrm{mod}b=kd,k\in [0,\frac{b}{d})$ ，所以若不存在 $k\in [0,\frac{b}{d})$ 使得 $l\le kd\le r$ 时无解。

假设 $f(a,b,l,r)=minx\in N^{\ast }|l\le ax\mathrm{mod}b\le r$ ，显然有 $f(a,b,l,r)=f(a\mathrm{mod}b,b,l,r)$ ，这个形式类似于欧几里得算法，所以我们期望是通过变形将 $a$ , $b$ 的位置互换，这样就能用欧几里得算法求解了。

分情况讨论一下：

• 当 $l=0,f(a,b,l,r)=0$
• 当 $\lceil \frac{l}{a}\rceil \le \lfloor \frac{r}{a}\rfloor$ 则 $\mathrm{\exists }\lceil \frac{l}{a}\rceil \le \lfloor \frac{r}{a}\rfloor$ 存在最小的 $x_0=\lceil \frac{l}{a}\rceil$, 使得 $l\le a{x}_0\le r$ ，显然 $f(a,b,l,r)=x_0$
• 当 $\lceil \frac{l}{a}\rceil >\lfloor \frac{r}{a}\rfloor$ ，存在 $M\in N^{\ast }$ 使得 $aM<l\le r<a(M+1)$ $$aM<l\le ax-bk\le r<a(M+1)\iff -a(M+1)<-r\le bk-ax\le -l<-aM\iff a(x-M-1)\le ax-r<bk\le ax-l\le a(x-M)$$

所以 $f(b,a,(-r)\mathrm{mod}a,(-l)\mathrm{mod}a)=f(b,a,a-r\mathrm{mod}a,a-l\mathrm{mod}a)$ 则完成了 $a,b$ 的交换。

Comments

Xiejiadong ：事实上，验题人在前一天验题的时候提出了这个题是个原题，但由于短时间内没有题目可以替代，考虑到 EOJ 月赛不涉及到任何利益仅用作大家交流和学习的平台，所以就只能硬上。

Problem B 健康监测计划

First Solved: Renatus

解法 1

考虑 $k=2$ 的时候是不是取所有的叶子结点，接着考虑 $k=3$ 的时候，发现可以多取一个点，考虑 $k=4$ 的时候，最优的策略一定是，先取所有的叶子结点并去掉它们，在剩余的树中取叶子结点。于是就有了一个想法，是不是对于 $k$ 为偶数的时候，就是取 $\frac{k}{2}$ 次叶子，当 $k$ 为奇数的时候，多取一个结点。

大概可以证明一下，显然前一批次取的叶子结点一定要比后一批次的叶子结点更多，调整法可知一定是最后几层叶子，又因为一条简单路径最多经过两个同批次取的叶子结点，所以显然是可行的。

解法 2

我们不妨从简单的情况开始考虑。当 $k=1$ 时，显然只能选取一个节点；当 $k=2$ 时，我们可以选取所有的叶子节点。所以我们不难发现叶子节点在选取的过程中有非常高的优先性，以此引发我们往贪心的角度思考。

首先二分答案，考虑如何判断一个答案是否合法。

我们可以用类似于拓扑排序的方式。首先将所有叶子节点加入队列，接着每次选取队头的节点为监测站，并将其删去，如果产生了新的叶子节点，则加入队尾。进行操作直到选完二分预期数量的监测站。

接着我们就可以利用树上动态规划，检查简单路径上监测站的最大值，不再赘述。

总时间复杂度 $O(n\log n)$。由于纯线性的做法只需要在这个思路上稍加优化，所以我们开足了一百万的数据量，不保证带 $\log$ 的算法可以通过。如果你的编程技巧非常高超，那么顺利通过也是很有可能的。

Problem C 最小表示

First Solved: MAOooo

不难发现，一段连续的 $1$ 可以变为开头一个 $1$ 和末尾一个 $-1$。然而，直接这么做有显然的反例，例如 $1110111$ 的最小表示只需要用到 $3$ 个 $1$ 或 $-1$，而直接变化会用到 $4$ 个。

粗暴做法的答案为 1 0 0 -1 1 0 0 -1，而一种正确答案为 1 0 0 0 -1 0 0 -1，对比一下，其实就是把相邻的 $-1$ 和 $1$ 进一步合并为一个 $-1$，同理，相邻的 $1$ 和 $-1$ 也能合并为一个 $1$，这个过程可以使用动态规划完成。所以，最终我们可以先将连续的 $1$ 表示为类似于差分的形式，然后再动态规划合并相邻的正负一。

设 $f[i]$ 为前 $i$ 位需要的非零元素数量。那么如果 $a[i]=0$，则 $f[i]=f[i-1]$；如果 $a[i]=-1$ 且 $a[i-1]=1$，或 $a[i]=1$ 且 $a[i-1]=-1$，则$f[i]=f[i-2]+1$。否则，如果 $a[i]=1$ 或 $a[i]=-1$，则 $f[i]=f[i-1]+1$。在转移的同时还需要记录转移的方向，最后才能输出方案。

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

Problem D 礼物箱

First Solved: paleprince

设共有 $n$ 种不同的礼物，其中第 $i$ 种礼物有 $a_i$ 件。求收集到所有种类的礼物时，收集到礼物总量的期望值。

解:

min-max 容斥.

令 $X_i$ 表示搜集到第 $i$ 种礼物时，搜集到的礼物数量。

那么所求即为
$$Y=\underset{i=1,2,\dots ,n}{max}(X_i)$$

注意到这里 $X_i$ 之间互相不独立. 所以不好直接求 $Y$ 的分布函数或者期望.

使用min-max容斥公式
$$\underset{i=1,2,\dots ,n}{max}(X_i)=\sum _i{X}_i-\sum _{i<j}min(X_i,X_j)+\cdots +(-1{)}^{n+1}\underset{i=1,2,\dots ,n}{min}(X_i)$$

根据期望的线性性，只要求 $min(S)$ 即可，$S$ 为 $X_1,X_2,\dots ,X_n$ 的某个子集。

先考虑最简单的 $E[X_i]$。

问题:

有$n$ 个白球，$m$ 个黑球，每次拿一个求出来，问第一次拿到白球时，已经拿出的黑球个数的期望。
$$\frac{(\genfrac{}{}{0ex}{}{m}{1})}{(\genfrac{}{}{0ex}{}{n+m}{1})}\frac{n}{n+m-1}+2\frac{(\genfrac{}{}{0ex}{}{m}{2})}{(\genfrac{}{}{0ex}{}{n+m}{2})}\frac{n}{n+m-2}+3\frac{(\genfrac{}{}{0ex}{}{m}{3})}{(\genfrac{}{}{0ex}{}{n+m}{3})}\frac{n}{n+m-3}+\cdots +m\frac{1}{(\genfrac{}{}{0ex}{}{n+m}{m})}\frac{n}{n+m-m}$$
尝试化简一下发现不会做了，考虑用递推来做。
$$dp[n][m]=\frac{m}{m+n}(dp[n][m-1]+1)+\frac{n}{m+n}$$
计算 $E[X_i]$ 时，把 $a_i$ 看成白球，其他看成黑球。也就是 $dp[a_i][N-a_i]$，其中 $N=\sum _i{a}_i$，然后考虑 $min(X_i,X_j)$， 表示第 $i$ 种礼物被抽到或者第 $j$ 种礼物被抽到。

那么计算时，只要把 $a_i+a_j$ 看成白球，其他看成黑球，即 $dp[a_i+a_j][N-(a_i+a_j)]$，也就是说只要递推一次 $dp[N][N]$，后面的期望都可以 $O(1)$ 得到。

最后答案就是把 min-max 公式套进来就行了。

Problem E 加密的情书

First Solved: SuperSodaSea

设 $f(x)$ 为题目所述的加密运算，那我们不难通过找规律得出结论：

• 若 $x=0$，则 $f(x)=0$
• 若 $x\ne 0,x\mathrm{mod}9\ne 0$，则 $f(x)=x\mathrm{mod}9$
• 若 $x\ne 0,x\mathrm{mod}9=0$，则 $f(x)=9$

所以，整个自然数数列的密文就是 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 …

Comments

Once ：为了增加签到难度，bingoier 在输入范围中加入了 $0$，不要忘记特判。题面强调自然数的概念也是希望大家能意识到 $0$ 的特殊性。

Once ：这六道题题面是我写的，大家有喜欢的不喜欢的欢迎吐槽。

Problem F 动态树

First Solved: guogai

解法 1 - 树套树

先说一个简单又有点套路的结论。节点 $u$ 到节点 $v$ 的边权异或和，等于从节点 $u$ 到根节点的边权异或和，异或上 $v$ 到根节点的边权异或和。我们记录 $a[i]$ 为 $i$ 号节点到根节点的边权异或和，那么对于查询操作而言，$a[x]$ 是确定的，就只需要在 $y$ 的子树中寻找一个节点 $t$ 使得 $a[x]\oplus a[t]$ 尽可能大，其中 $\oplus$ 表示按位异或操作。

这个问题是经典的字典树运用。我们把 $y$ 子树中的所有 $a[t]$ 值放入一个字典树中，然后拿着 $a[x]$ 逐位尽可能往反方向走，就能快速地找出最大的异或和。

然而“把 $y$ 子树中的所有 $a[t]$ 值放入一个字典树中”并不是一个简单的操作。考虑到子树中所有节点的 dfs 序是一个连续的区间，那么我们可以想到一种简单粗暴的做法。用一棵线段树，根据 dfs 序维护每个区间的异或和字典树，那么查询就可以在 $O(\log n)$ 的时间内确定一个特定 dfs 值区间的字典树，再用 $O(\log v)$ 的时间在字典树上查询即可。对于插入操作，我们只需要在线段树叶子节点到根节点的链上的每一个节点的字典树上插入一个异或值，单次插入操作的时间复杂度也是 $O(\log n\log v)$ 的。

总时间复杂度 $O(Q\log n\log v)$，其中 $v$ 表示边权上限。

解法 2

考虑如果是固定起点，在树上找任意点作为终点的时候问题如何解决。

此时，我们如果要求任意两个点 $x,y$ 之间的路径长度，显然有 $d(x,y)=d(1,x)\oplus d(1,y)$ ，所以我们可以保存下所有的点 $x$ 到根结点的路径长度 $d(1,x)$ ，并插入 Trie 中，之后对于每一个询问的处理就变成了求序列中两个数异或最大的经典问题。

而从这个问题拓展到规定子树的查询问题，其实也是一个比较套路的事情。如果按照 dfs 顺序编号的话，子树对应的编号一定是一个连续的区间，所以对于一个子树，我们只需要知道编号的开始和结束位置，也就是说，我们在 Trie 上找对应结点的时候，我们需要保证走到的 Trie 结点的子树中包含至少一个在 $b$ 对应子树编号区间内的 01 串即可。

Comments

MAOoo

4 年，6 月前

D 题题解的对期望的容斥我没太看懂，看样子复杂度应该是$O(2^n+m^2)$的。不过我写的复杂度大概是$O(n{m}^2)$的。就是分别计算拿到的最后一种礼物是$i$的期望，然后加起来。计算的时候只需要让另外$n-1$种至少选了$1$个，这里用类似背包的方法就行了。

看了一眼所有通过记录，就我是这样写的，而且时间也很悬，像是放了一个假做法通过。。

回复 1 0

Once

4 年，6 月前

这题数据稍微粗糙了点，造的时候也没有刻意去卡。不过这题可以说是 min-max 容斥的板子题了。

回复 0 0

TD18530125

4 年，6 月前

E题 n=1 且唯一的密文为0时 为什么不考虑l==r==0的情况?

回复 0 0

Once

4 年，6 月前

对于你所说的情况，答案存在且唯一，即为 $l=r=0$。测试数据中并没有这组数据。

回复 0 0

zqy1018

4 年，6 月前

C 不用 DP，直接把一段正负 1 交替的子段合并到只有 1 或者 -1 似乎也行

回复 0 0

Once

4 年，6 月前

是的，这题有很多可以直接用贪心构造的方法。dp 的优势在于可以减少很多特殊判断。

回复 0 0

跃迁引擎启动

4 年，6 月前

D 邦邦，出题人头像好评（

上次无限池吃井，本来想出个求进下个池子的期望次数hhh

回复 0 0

heyuhhh

4 年，6 月前

请问一下A题的原题是哪道题呢

回复 0 0

tommy0103

4 年，6 月前

F题中，我觉得你这个既然节点是动态插入的，子树的dfs序就不好维护吧

回复 0 0

Once

4 年，6 月前

这题不是在线操作的。题解所说的 dfs 序是指完整的树上的 dfs 序。

回复 0 0

tommy0103

4 年，6 月前

那没事了qwq

回复 0 0

tommy0103

4 年，6 月前

我觉得这个F有点假，可以放下std么/kel

回复 0 0

Once

4 年，6 月前

选手程序都已公开。

回复 0 0

求求你让我AC77

4 年，6 月前

有没有B题的std？qwq

回复 0 0

Once

4 年，6 月前

比赛程序已经全部公布

回复 0 0

Chirography_11

4 年，6 月前

F题的第二种方法，“我们在 Trie 上找对应结点的时候，我们需要保证走到的 Trie 结点的子树中包含至少一个在 对应子树编号区间内的 01 串即可“，这个要怎么维护呢？

回复 0 0

Once

4 年，6 月前

可以利用一些技巧，比如打时间戳，或者像方法一一样套一个数据结构去维护。

回复 0 0