「Summary」学科营题目集合

What we don’t know.

---

The Problem List

Title	Source	Link	Finished
补退选	THUSC 2016	loj2291	True
成绩单	THUSC 2016	loj2292	True
星露谷物语	THUSC 2016	loj2293
大葱的神力	THUWC 2017	loj2288
在美妙的数学王国中畅游	THUWC 2017	loj2289
随机二分图	THUWC 2017	loj2290	True
巧克力	THUSCH 2017	loj2977	True
杜老师	THUSCH 2017	loj2978	True
换桌	THUSCH 2017	loj2979	True
大魔法师	THUSCH 2017	loj2980	True
如果奇迹有颜色	THUSCH 2017	loj2981
宇宙广播	THUSCH 2017	loj2982
Minimax	PKUWC 2018	loj2537	True
Slay the Spire	PKUWC 2018	loj2538
斗地主	PKUWC 2018	loj2539
随机算法	PKUWC 2018	loj2540	True
猎人杀	PKUWC 2018	loj2541
随机游走	PKUWC 2018	loj2542	True
真实排名	PKUSC 2018	loj6432	True
最大前缀和	PKUSC 2018	loj6433	True
主斗地	PKUSC 2018	loj6434
星际穿越	PKUSC 2018	loj6435	True
神仙的游戏	PKUSC 2018	loj6436
PKUSC	PKUSC 2018	loj6437

「THUSC 2016」补退选

link record

观察到这个查询答案具有单调性，可以直接建出来可持久化 Trie，二分版本号查询是否满足要求即可。
Trie 上维护的信息是当前每个前缀出现次数和所有版本中每个前缀出现的最大次数（相当于维护了一个单调序列）。

「THUSC 2016」成绩单

link record

发现 $n$ 非常小，所以定义状态 $dp_{l, r}$ 表示 $[l, r]$ 这个区间最小代价，发现这样转移不了，因为这个题目定义的发成绩的方式可以允许首先在这个区间里面抽出去一部分之后继续发。
于是换一个方式去定义，定义 $dp_{l, r, minl, maxl}$ 表示 $[l, r]$ 这个区间首先分发出去一部分后剩余部分里面最大值是 $maxl$ ，最小值是 $minl$ 的最小代价，$res_{l, r}$ 表示 $[l, r]$ 这个区间的答案。

考虑在 $[l, r]$ 这个区间往后加上一个 $r + 1$ 之后怎么转移。

• 和 $[l, r]$ 一起取走， $dp_{l, r + 1, \min \{minl, a_{r + 1} \}, \max \{maxl, a_{r + 1} \}} = \min \{ dp_{l, r, minl, maxl} \}$ 。
• 枚举一个中间的 $k$，把 $[k + 1, r + 1]$ 一起取走 $dp_{l, r + 1, minl, maxl} = dp_{l, k, minl, maxl} + res_{k + 1, r + 1}$。

答案是 $res_{1, n}$ 。

「THUSCH 2017」巧克力

link record

随机化 /kk。一个叫 color coding 的神必算法。

首先有一个中位数二分的套路，如果 $n m$ 很小，可以跑 $\binom{n + m}{k}$ 次斯坦纳树的板子。

然后开始乱搞，将所有的颜色映射到 $[0, k)$ 里面，考虑随出来最优解的概率，当最优解包含的 $k$ 种颜色被映射到了不同的数字上，可以拿到最优解，每一次成功的概率是 $\Large \frac{k!}{k^k}$ ，当我们随了 $T$ 次时仍然不成功的概率是 $(1- \frac{k!}{k^k})^T$ 。

大概 $200$ 次以后这个错误率不用管了。

「THUSCH 2017」大魔法师

link record

直接矩阵乘法即可。
直接被卡常，有点无聊，需要把矩阵乘法里面的循环展开，以及取模优化。。。

「THUWC 2017」随机二分图

link record

暴力都有点难想。
首先考虑如何建边，具体如下。
对于情况一，我们直接建边并把边的概率设为 $\frac{1}{2}$ 。
对于情况二，我们建出两条单独的边，并把边的概率设为 $\frac{1}{2}$，等于这两条边可以 $\frac{1}{2}$ 单独用，也可以以的概率一起用，所以我们在建一条概率为 $\frac{1}{4}$ 的边，强制连接两对点。
对于情况三，仿照上面的做法，多建一条概率为 $\frac{1}{4}$ 的边，因为他们不能一起用。
然后搜索可以有 $20pts$ 。

发现 $n$ 很小可以状压。定义 $dp_{s1, s2}$ 为左边连接情况为 $s1$，右边连接情况为 $s2$，注意到转移时可以直接选最小的没有被覆盖的点转移，因为最终的目的是覆盖所有点。
需要用 map 存状态，感性理解一下，复杂度 $\Theta(n)$。

「THUSCH 2017」杜老师

link record

很高妙，但是乱搞。
尤启发性的一点是这道题提供了另外一种统计乘积为完全平方数的子集的个数的方案。
具体来说，对于每一个数建一个向量 $b$，统计每一个质因子出现的奇偶次数，当一个子集 $S$ 里面的数乘积为完全平方数当且仅当 $S$ 中所有向量 $b$ 的和在 $\mod 2$ 意义下为 $0$。这个可以用线性基维护，用 bitset 优化。但是复杂度在 $\frac{(r - l + 1)\pi^2(n)}{\omega} = 1e18$。
可以发现 $> \sqrt{1e7}$ 的因子只会出现一次，于是对于这些因子单独处理，当某个数 $x$ 的最大因子 $mxp_x > \sqrt{1e7}$ 时，就先检查 $mxp_x$ 的向量是否为空，如果是空的，那么令该线性基为 $x$ 表示的向量，否则用 $x$ 的向量异或上该向量再插入线性基，于是线性基的规模从 $1e6$ 变成了 $450$。
最后一步需要观察，当 $l, r$ 差距非常大的时候线性基很容易满，这个阈值大概是 $1e7$ 左右，那么此时枚举所有 $[1,r]$ 之间的质数检验即可。
最后得到了一个类似根号分治的做法。

「THUSCH 2017」换桌

link record

首先建 $n \times m$ 个中转的点，一边是桌子编号，一边是位置编号。因为桌子的编号移动是连续的于是线段树优化即可，绝对值直接拆开就行了。

「PKUWC2018」Minimax

link record

以为。这是期望概率推式子高妙题，结果是个数据结构。
拆开算贡献，发现只需要算出来概率就可以了。定义 $dp_{i, j}$ 表示第 $i$ 个节点是 $j$ 的概率，考虑合并两个儿子，式子是

$$ dp_{u, i} = dp_{lch, i} \times \left[p_u\sum_{j < i}(dp_{rch, j}) + (1 - p_u) \sum_{j > i}(dp_{rch, j}) \right] $$

右儿子同理。

发现这个直接做是 $\Theta(n^2 \log n)$ 或者 $\Theta(n^2)$ 的。
其实这个式子已经没有办法化简了，解题的关键在于去掉一些没有意义的转移，因为题目保证了所有的权值不同，那么在往上算贡献的时候线段树有很多空节点，再注意到这个式子的贡献方式很优美，是区间求和，并且加上有合并两个儿子的操作，于是在线段树合并的时候顺便维护前后缀和即可。

「PKUWC2018」随机游走

link record

综合性较强的好题。
需要会一点 min-max容斥 。写一个速通版本，成立的前提是满足全序关系且元素有可加减性。

全序关系

对于集合 $X$，如果满足全序关系，则对于任意 $a, b, c \in X$ 满足。
反对称性：若 $a \le b$ 且 $b \le a$，则 $a = b$
传递性：若 $a \le b$ 且 $b \le c$，则 $a \le c$
完全性：对于 $a,b$，一定有 $a \le b$ 或 $b \le a$

$$ \max_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{x_j}} \\ \min_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\max_{j\in T}{x_j}} $$

于是拿到这道题来，设随机变量 $x_i$ 表示第一次走到 $i$ 的时间，要求的是

$$ E\left( \max_{i \in S} x_i \right) $$

套容斥公式得到

$$ E\left( \max_{i \in S} x_i \right) = E\left( \sum_{T\subseteq S}{(-1)^{|T|-1}\min_{i\in T}{x_i}} \right) $$

也就是 $\sum_{T\subseteq S}{(-1)^{|T|-1}}E\left(\min_{i\in T}{x_i}\right)$。

现在需要对于任意一个集合 $T \subseteq [n]$ 求出 $E(\min_{i \in T} x_i)$，这个式子的意义是第一次走到 $T$ 中某个结点的步数的期望时间，于是定义 $f_i$ 表示从 $i$ 开始第一次走到 $T$ 中某个结点的期望步数，当 $i \in T$ 时，$f(i) = 0$，当 $i \not\in T$，$f(i) = 1 + \frac{1}{deg(i)} \sum_{(i, j) \in E} f(j)$。
后面这个式子是有技巧性的可以消除后效性，可以参考 here 。
拿到推出来的式子后可以 $\Theta(n2^n)$ 地去计算，做了子集前缀和之后可以得到一个 $\Theta(1)$ 回答的做法。

「PKUWC2018」随机算法

link record

看到 $n \le 20$ 考虑状压，这道题和 ABC 267 G 有差不多的想法。
把生成排列看成按顺序从小往大往序列里面插入元素，那么很自然地定义 $dp_{sta}$ 表示现在的独立集集合是 $sta$ 的方案数，但是要求最大的，那就补一维 $i$ 表示长度，现在的状态是 $dp_{sta, i}$，然后枚举一个不在 $sta$ 里面的 $j$ 尝试转移，设与 $j$ 的距离在 $1$ 以内的点组成的集合是 $t$，于是转移的方式是在 $t$ 中除了 $j$ 的元素出现之前把 $j$ 放进去，意思时说把 $t$ 中除了 $j$ 的元素随便放在序列的最后面，于是转移是

$$ dp_{S \cup T, i + 1} = dp_{S \cup T, i + 1} + dp_{S} \times A^{\mid T - (S \cap T) \mid}_{n - \mid S \mid - 1} $$

「PKUWC2018」真实排名

非常容易，只需要查看对于每个数会产生贡献的数的个数即可，分类讨论一下这个数本身翻不翻倍然后组合数就可以了。

「PKUWC2018」最大前缀和