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)

题意：给一个数列，求每个数右边比自己大的数到自己的距离（下标减法）

题解：从大到小插入数组，维护一个单调栈。每次从单调栈里lowerbound一个大的数

Problem F

Upsolved by Kilo_5723.

题意：给一棵树，每个节点有一个权值，$5000$ 次询问，求离节点 $u$ 距离 $\le k (k\le 100)$ 的所有节点的权值和。

题解：如果内存足够，一个显然的 dp 做法是：以 $1$ 为根，$f(u,p)$ 代表 $u$ 的子树中与 $u$ 的距离 $\le p$ 的节点权值和，那么与 $u$ 距离 $\le k$ 的节点 $v$ 可以按照 $LCA(u,v)$ 与 $u$ 的距离分类，最多 $100$ 类，每类都可以 $O(1)$ 求。

但现在内存有限制，不能直接 $dp$，但询问次数不是很多，可以将所有询问离线，一边做 dp 一边处理询问。问题转换成了如何最小化同时需要的 dp 数组数量。

我们发现，首先显然地，一个数组在被使用完之后可以释放内存。但这样不能处理深度较深的情况。在此基础上，我们发现一个数组被申请的时机可以延后到刚刚处理完它的第一个子节点的时刻。

这样已经需要面向程序特殊构造数据卡掉了，但可以对每一个节点，把深度最深的子节点交换到第一个子节点的位置。这样可以保证数组个数是严格 $O(logn)$ 的。

Problem G

Solved by Xiejiadong. 01:18 (+2)

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

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

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

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

Upsolved by Weaver_zhu

Problem H

Upsolved by Weaver_zhu.

题意：$n=p_1^{q_1}...p_k^{q_k} , f(n)=q_1+...+q_k$ 求 $\sum\limits_{i=1}^{n}f(i!)$

题解：对于小的素数，直接计算 $\sum\limits_{i=1}^{n}{p^c}$，类似类欧，实际上找规律 $O(1)$ 也能出。对于大的素数，$p^c,c=1$。$f(ab) = f(a)+f(b)$，原式=$\sum\limits_{i=1}^{n}(n-i+1)f(i)$。每个 $p$ 的贡献为 $(n-p+1)f(p) + ... + (n-xp+1)f(xp), x=\frac{n}{p}$。所有素数一起求，套个数论分块，然后发现需要求区间素数个数和区间素数和。求和的点都是 $n/x$，因此可以只筛一遍 min25。

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)$：

\begin{equation} dfs(u)=\left\{ \begin{aligned} &dep(u)&(|S(u)|=0)\\ &max_{i=1}^{|S(u)|}dfs(rand(S(u))) & (|S(u)|\neq 0) \end{aligned} \right. \end{equation}

求 $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$ 的概率，$dfs(u)=max_{i=1}^{|S(u)|}dfs(rand(S(u)))=maxdep$ 的概率 $p(u)$ 就是 $1-(1-f(u))^{|S(u)|}$。答案就是 $p(1)$。

Problem K

Solved by Kilo_5723. 02:06 (+2)

题意：给出平面上 $n$ 个点，求至少要添加多少个点使得所有点中心对称。

题解：枚举中心对称的点。对于每个点 $P$，$P$ 每是一对点的中点，选取 $P$ 就能减少两个需要添加的点。$P$ 每和一个点重合，选取 $P$ 就能减少一个需要添加的点。在所有点中选取能减少需要添加点的数量最多的就是答案。

Problem L

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

题意：平面网格图上有一个骰子，给出 $n$ 个需要经过的点，可以以任意顺序经过这些点，但一定要正面向上才算经过。求让骰子经过所有点的最小滚动次数。

题解：问题分为两部分。第一部分是求出 $n$ 个点之间滚动的最短距离，第二部分是给出 $n$ 个点以及两两距离，求从原点出发经过每个点的最短链。

对于第一部分，我们要求的是从 $(x1,y1)$ 正面朝上出发，正面朝上地到达 $(x2,y2)$ 的最小滚动次数。我们发现，当 $|x1-x2|$ 或 $|y1-y2|$ 太大，我们最优的选择之一是朝相近的方向滚动 $4$ 次，不改变骰子的朝向而将距离减少 $4$。因此，我们可以把 $|x1-x2|$ 和 $|y1-y2|$ 压缩到较小的范围而不影响正确性。我们取 $0 \le |x1-x2|,|y1-y2| \le 100$。

对于这种范围，可以 BFS 求出 $0,0$ 到每个位置上每个朝向状态的最小翻滚次数。可朝向状态太多，还是很难处理。

但我们发现，这些状态是可以压缩的。因为这道题里，每个侧面都没有区别，所以可以把朝向状态压缩成六个：正面朝上，背面朝上，侧面朝上时正面向上/下/左/右。这样，向四个方向滚动后新的朝向状态也能枚举出来。对于问题的第一部分，只要把两个点之间的相对距离压缩到 $100$ 以内，再通过 BFS 预处理的结果 $O(1)$ 求出来。

而问题的第二部分是一个经典的状态压缩 $dp$。将 $n$ 个点两两按距离建边，通过状压 $dp$ 求出最短链就是答案。

Problem M

Solved by Weaver_zhu. 02:30 (+)

题意：给两个字符串，求s最长的子序列使其比t的字典序大

题解：求出每个字母后面最近的26个字母，然后枚举在每个位置用哪个字母超越t的字典序。不超越显然就要和t相同，最后再判断是否能前缀相同长度再比他大。