ExaWizards 2019 题解
AB 就不写了。
C - Snuke the Wizard
题意
有 \(N\) 个格子从左到右排列，第 \(i\) 个格子上有一个字符 \(s_i\)。
初始时，每个格子上有一个棋子。接下来进行 \(Q\) 次操作，第 \(i\) 次操作为：
- 将所有字符为 \(t_i\) 的格子上的棋子向 \(d_i\) 方向移动，\(d_i\) 为
L或R，分别表示向左和向右。
若一个棋子被移出格子，该棋子消失。求最后存在的棋子数量。
\(N,Q\le 2\times 10^5\)
题解
注意到棋子间的相对顺序不会改变。所以最后存在的棋子一定是原来的一个区间。
可以通过二分求出该区间的左右端点。
时间复杂度 \(O(N+Q\log N)\)。
D - Modulo Operations
题意
有 \(N\) 个互不相同的数 \(S_i\)，以及一个数 \(X\)。你需要求出对于所有 \(S_i\) 的排列，\(X\) 依次对所有 \(S_i\) 取模后的值之和。对 \(10^9+7\) 取模。
\(N\le 200,S_i,X\le 10^5\)
题解
显然对最后结果有影响的是所有等于前缀最小值的位置。
将 \(S_i\) 从大到小排序，考虑钦定若干数作为前缀最小值，那么其他数就必须插入到后面，也就是说，第 \(i\) 个数若没有被钦定为前缀最小值，则方案数需要乘上 \(N-i\)。
于是就可以简单 DP 了。时间复杂度 \(O(NX)\)。
E - Black or White
题意
有 \(B\) 个黑球和 \(W\) 个白球，不断执行以下操作：
- 等概率选择黑白两种颜色之一，若存在该颜色的球，则取走一个。
对于每个 \(i=1,\ldots,B+W\)，求第 \(i\) 个取走的球是黑色的概率。
\(B,W\le 10^5\)
题解
题目中的操作相当于两种颜色同时存在时黑白颜色各有 \(\frac{1}{2}\) 的概率，只有一种颜色时只能取走该颜色的球。
求出 \(f_i,g_i\) 分别表示前 \(i\) 个球把所有白球或所有黑球取完的概率，那么第 \(i\) 个球是黑球的概率即为 \(f_{i-1}+\frac{1}{2}(1-f_{i-1}-g_{i-1})\)。
考虑如何求 \(f_i,g_i\)。显然有递推式 \[f_i=f_{i-1}+\binom{i-1}{W-1}\frac{1}{2^i}\]
\(g_i\) 类似。
时间复杂度 \(O(N)\)。
F - More Realistic Manhattan Distance
题意
有 \(N\) 条水平单向道路和 \(M\) 条竖直单向道路，相邻两条道路距离为 \(1\)。道路与道路之间有 \(NM\) 个交点。每条道路的方向是给定的。
\(Q\) 次询问，每次给定两个点 \((a,b),(c,d)\)，求最短路。
\(N,M\le 10^5,Q\le 2\times 10^5\)
题解
注意到 \((a,b)\) 右边第二条向下的路是没有用的，其他方向同理。
于是我们只需要保留 \((a,b)\) 上下左右各方向的第一条道路即可，\((c,d)\) 同理。
这样最多只有 \(6\) 条水平道路和 \(6\) 条竖直道路，最多有 \(36\) 个交点，\(72\) 条边。
直接跑堆优化 Dijkstra 即可。
时间复杂度 \(O(N+M+Q)\)。
