2021.11.05模拟赛

I will never go

2021.11.05 模拟赛

A. 宝藏

暴力怎么做，暴力是不是二分，二分，主席树

显然有主席树可以 $O(\log n)$ 检验一个位置是否满足条件，再想一下发现位置有单调性，枚举长度顺序检验即可

复杂度 $O(n\log n+q)$

B. 寻找道路

震惊，无良出题人脚造数据竟使暴力满分

先把前导零去掉，剩下的部分先保证长度最短，然后保证 $1$ 的位置尽可能靠后

从 $1$ 开始 BFS 找到所有前导零的点，然后把长度相同的一起转移，先转移 $0$ 再转移 $1$ 的边

注意要一起转移，否则可能会有某个点用 $1$ 更新了原本能用其他点的 $0$ 能更新的点

C. 猪国杀

大力计数

首先我们选的卡牌必然是排完序的一个前缀

如果我们能求出来 $i$ 个数字 每个数字不超过 $j$ 总和不超过 $k$ 的方案数 $f_{i,j,k}$

枚举一个数字表示当前选的最大值为 $j$ 有 $i$ 个严格小于他的， $t$ 个等于 $j$ 的，选了 $k$ 个 $j$

方案为 $\sum\limits_{i=0}^{n}\sum\limits_{j=1}^{A}\sum\limits_{k=1}^{n-i}f_{i,j-1,m-kj}\sum\limits_{t=k}^{n-i}(A-j)^{n-u-t}\binom{n}{i}\binom{n-i}{t}$

组合意义比较明显，问题是我们要求的是期望，为啥只用计算方案数？

因为方案数有重复统计的，注意到我们虽然钦定 $j$ 是选的数最大的，但其实他不是

因为 $f_{i,j-1,m-kj}$ 只要求总和小于等于 $m-kj$ 有可能选完之后后面还能选一些数

而对于固定个数列，因为我们对比当前选的数大的数没有限制，所以每个被选的数都当了遍 “最大值”，所以这样正好计算了选的个数次

D. 数树

树哈希可过

考虑状压 设 $dp_{x,S}$ 表示在大树上第 $x$ 个节点儿子对应小树的状态 $S$

考虑如果让 $v$ 对应 $i$ 则 $v$ 的儿子也应对应 $i$ 的儿子

预处理小树儿子集合转移即可，最后需要除去小树自同构的方案数

复杂度 $O(nm^22^{10})$