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