XR-3 做题记录
ix35
·
2021-10-22 14:46:48
·
个人记录
XR-3
（Luogu P5534~P5539）
本场比赛平均质量较高，比 XR-4 更好一些。
一星表示是极其简单的题，我基本上可以秒。
二星表示是比较简单的题，我赛时可以比较快做出。
三星表示是中等难度的题，我赛时不确定能不能做出。
四星表示是较难的题，我赛时做不出。
五星表示是很难的题，我可能永远也做不出。
主要考虑思维难度。
打*号表示没有写的题，可能是不打算写了，也可能是暂时没来得及写。
A. 等差数列
难度： \bigstar
题目大意：
求首项为 a_1 ，第二项为 a_2 的 n 项等差数列元素和。
|a_1|,|a_2|,n\leq 10^6
题目解法：
答案为 \binom n 2\times (a_2-a_1)+na_1 ，时间复杂度 O(1) 。
这样的题目出现在比赛中是怎么会事呢？
B. 小道消息
难度： \bigstar
题目大意：
有 n 个人，代号为 2,\ldots,n+1 ，第零秒将一个信息告诉第 k 个人，每秒内，知道消息的人会将消息告诉所有代号和他的代号互素的人，问至少多少秒后所有人都知道了信息。
**题目解法：**
众所周知 $(n,2n]$ 中有至少一个素数，所以答案至多是 $2$，只需要判定答案是不是 $1$，即 $k+1$ 是否与所有其他数互素。
时间复杂度为 $O(\sqrt n)$。
---
### C. 核心城市
**难度：**$\bigstar$
**题目大意：**
给定 $n$ 个点的树，你可以选择包含 $k$ 个点的一个连通块，最小化所有点到连通块的最短距离的最大值，只需要输出这个最小的最大值。
$n\leq 10^5
题目解法：
二分答案 C ，考虑枚举连通块的 LCA，LCA 之下只要是到子树内最远点距离不小于 C 的点就要选，直接进行一个换根 DP 就可以了。
时间复杂度为 O(n\log n) 。
事实上也可以先证明直径中点必选，然后直接排序选择，可以 O(n) 。
D. 系统设计
难度： \bigstar\bigstar （更优复杂度 \bigstar\bigstar\bigstar ）
题目大意：
给定 n 个点的有根树，长度为 m 的序列 a_1,\ldots,a_m ，支持 q 个操作：
修改操作：序列的单点修改；
查询操作：给定 x,l,r ，求从 x 出发，依次考虑 i=a_l,\ldots,a_r ，如果 x 有大于 i 个儿子就令 x 变为其编号第 i 小的儿子，否则终止过程，问过程结束后 x 到了哪里。
1\leq n,m,q\leq 5\times 10^5
题目解法：
考虑重链剖分，查询时先快速跳掉在重链上下行的部分，然后走一条轻边，由于轻边最多只会走 \log n 次，所以只需要快速求出在一条重链上能走多远，而这只需要预处理重链上每个点重儿子编号相对大小构成的序列的区间 Hash 值，与序列 a 的区间 Hash 值比对即可。
具体地，由于存在修改，可以用线段树维护 a 的区间 Hash，查询时直接二分则总复杂度为 O(n\log^3 n) ，如果线段树上二分则总复杂度为 O(n\log^2 n) 。
然而还有一种更好的做法，首先我们可以“回退”根结点到 x 的这一段（视为在 a_l,\ldots,a_r 这个序列前加入一些数），将问题转化为从根结点出发，那么只需要预先存好每个点对应的从根结点出发的路径的 Hash 值，就只要查询最大的 m 使得 a_l,\ldots,a_m 的 Hash 值与某个点的 Hash 值匹配，采用线段树上二分，复杂度为 O(n\log n) 。
E. Namid[A]me
难度： \bigstar\bigstar\bigstar
题目大意：
给定 n 个点的点带权树，设其叶子（度数为 1 的点）个数为 d ，点 i 的权值为 a_i ，令 f(u,v) 为 u\to v 路径上点权与，对所有无序对 (u,v) 求和 f(u,v)^{f(u,v)} ，答案对 786433 取模，模数有一个原根是 10 。
**题目解法：**
我的做法似乎和题解不太一样。
显然树中的任意一条路径是以某个叶子为根时的一段祖先链，我们不妨依次枚举叶子 $l_1,\ldots,l_d$ 为根，统计祖先链的贡献。
对于确定的 $u$，枚举其祖先 $v$ 的过程中，显然 $f(u,v)$ 只有不超过 $\log A$ 种取值（$A$ 是 $a_i$ 的上界），并且在 DFS 过程中对每一位记录最深的这一位为 $0$ 的点就可以得到这 $\log A$ 种值和它们的分界点，于是只需要 $O(n\log A)$ 就可以统计所有祖先链的答案。
但是这样会重复计算，所以我们不妨让 $l_i$ 为根时不再计算在 $l_1,\ldots,l_{i-1}$ 为根时已经计算过的那些路径。
设祖先链是 $u\to v$（$v$ 是祖先，$u$ 是后代），再设 $w$ 是 $v$ 到 $u$ 路径上 $v$ 的后继点，那么这条祖先链之前没有被算过，当且仅当 $l_1,\ldots,l_{i-1}$ 都在 $w$ 的子树中，且都不在 $u$ 的子树中，也就是说我们只是对 $u$ 的选取进行限制，然后再限制 $v$ 是 $u$ 的深度不超过一个定值的祖先，还是可以用与上面相同的 DFS 方法求解。
注意利用原根使得幂的计算变为 $O(1)$ 的。
时间复杂度为 $O(dn\log A)$。
---
### F. Unknown Mother-Goose
**难度：**$\bigstar\bigstar\bigstar\bigstar
题目大意：
给定 n 和一个正整数集合 S ，求 x 的数量，使得：
存在 a\in S 使得 a\mid x ；
存在 b\in S 使得 b\mid (x-1) ；
存在 c\in S 使得 c\mid (x-2) 。
3\leq n\leq 10^9,\ \ |S|\leq 20
题目解法：
考虑暴力，复杂度是 O(n+\sum\limits_{x\in S}\dfrac{n}{x}) ，难以通过。
使用位运算来加速这一过程，设一个长度为 n+1 的 \texttt{01} 串 T 满足：T_i 为 \texttt{1} 当且仅当 i-1 是某个 x\in S 的倍数。
我们要查询的是 T 中有多少个连续三个 \texttt{1} ，如果压位存储，只需要类似 popcount(T|(T>>1)|(T>>2)) 的运算就可以求出答案了。
用 unsigned long long 存储 T ，但我们还是没有减小这个 \dfrac{n}{x} 的复杂度，因此还要对 x 分类讨论：
如果 x\ge 64 ，那么直接采用 \dfrac{n}{x} 的暴力算法；
如果 x<64 ，那么 x 的倍数对应的对 T 的影响是周期的，有一个周期是 64x ，而 64 恰好又是 unsigned long long 的位数，我们只要用一个辅助数组存储 x 对 T 的前 x 个 unsigned long long 单元的影响，然后周期性地将它的第 i 个单元或到 T 的第 jx+i 个单元即可，利用位运算，可以做到复杂度 O(\dfrac{n}{64}+64) 。
时间复杂度为 O(\dfrac{n|S|}{w}) ，其中 w=64 。