• 搬题人：
  • 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)$。