ICPC 2019 Xuzhou Online Contest

Problem A

Solved by Kilo_5723 && Weaver_zhu. 03:40 (+)

题意：用同余式给出 $n$，有 $n$ 个石子，第一个人可以拿任意多但不能全拿走，之后每个人可以拿 $1$ 到前一个人拿取石子总数两倍的石子，取光石子的人获胜，求先手必胜还是后手必胜。

题意：第一部分是 CRT，第二部分是斐波那契博弈，当且仅当 $n$ 在斐波那契数列里出现过时后手必胜。

Problem B

Solved by Xiejiadong. 03:23 (+5)

题意：支持两个操作：

• 删掉一个数

• 询问一个数之后没被删掉的第一个数

题解：询问的位置之后，连续的一段被删掉的是会被影响的。

可以发现，答案只会是所有询问和修改位置，或者他们 $+1$ 位置，离线以后离散，用并查集维护即可。

死于 C++14 跑的比 C++11 慢。

Problem C

Solved by Xiejiadong. 00:14 (+1)

傻逼签到题。

死于出题人的英语水平。

Problem D

Solved by Kilo_5723. 01:43 (+)

题意：给出一个父串 $T$，给出 $n$ 个子串 $S_i$，求 $T$ 和每个 $S_i$ 的包含关系。保证 $\sum_{i=1}^{n}(|T|+|S_i|)\le 10^7$。

题解：一开始没看到最后一个限制条件，做 $n$ 次 KMP 就可以了。

Problem E

Solved by Weaver_zhu. 00:51 (+1)

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 01:18 (+2)

题意：询问所有回文子串的价值，一个字符串的价值定义为包含的不同字母数量。

题解：利用 pam 建出所有回文串。

在见串的同时保存被一个状态所包含的不同字母数量，暴力加上当前转移边上的字母。

答案就是所有状态出现的次数 * 所有状态包含的不同字母数量。

Problem H

Unsolved.

Problem I

Solved by Xiejiadong && Kilo_5723. 01:55 (+)

题意：给出一个排列，每次求一个排列的区间中有多少数对满足 $min(x,y)=gcd(x,y)$ 。

题解：很容易发现， $min(x,y)=gcd(x,y)$ 等价于 $x|y$ 或者 $y|x$ ，而因为保证了给出的是一个排列，所以整除关系总数是 $nlogn$ 的。

于是，可以利用筛法，如果 $x|y$ ，我们就把 $(x,y)$ 这个点加入平面，询问就变成了询问一个正方形区域内点的数量。

离线，树状数组维护二维数点即可。

Problem J

Solved by Kilo_5723. 02:49 (+)

题意：给出一棵树，令 $S(u)$ 代表 $u$ 的孩子的集合，$rand(S(u))$ 代表 $u$ 的一个随机孩子，定义函数 $dfs(u)$：若 $|S(u)|=0$，返回 $dep(u)$，否则返回 $max_{i=1}^{|S(u)|}dfs(rand(S(u)))$。另 $maxdep=max_{i=1}^n dep(i)$，求 $dfs(1)=maxdep$ 的概率。

题解：相当于求可以访问到深度最深的节点的概率。另 $dfs(u)=maxdep$ 的概率为 $p(u)$，则对于每一个非叶节点 $u$，$f(u)=\frac{\sum_{v \in S(u)}p(v)}{|S(u)|}$ 就是 $dfs(rand(S(u))=maxdep$ 的概率，那么 $max_{i=1}^{|S(u)|}dfs(rand(S(u)))=maxdep$ 的概率就是 $1-(1-f(u))^{|S(u)|}$ 的概率。

Problem K

Solved by Kilo_5723. 02:06 (+2)

Problem L

Solved by Kilo_5723 && Xiejiadong. 04:43 (+)

Problem M

Solved by Weaver_zhu. 02:30 (+)