2020牛客多校
打星为 upsolve
Round 1
好多论文题。。自闭
rank 99 (3/10)
*A
后缀数组，卡常
F
签到，扩两倍下标取模比较下
H
预处理费用分段函数，讨论
J
OEIS 牛逼
Round 2
再也不做构造系列
rank 85 (5/11)
*A
对于每个字符串枚举前缀 $s[1]$ … $s[i]$，设有 $cnt[i]$ 个后缀和他相同，但这样会重复计算，如字符串 $aba$ 和后缀 $aba$，同一字符串的后缀被计了两次数
考虑去重，从前往后 $cnt[next[i]]-=cnt[i]$，然后计算答案即可。
B
三点定圆，考虑枚举 $(0,0)$ 外的另外 $2$ 点，算出圆心去重统计答案，注意精度。
C
赵哥狂日$20$发
题解做法：所有叶子按 dfs 序 sort, $l_{1} - l_{s/2+1}$, $l_{2} - l_{s/2+2}$ $…$ $l_{s/2} - l_{n}$
D
签到
*E
待补 FWT
F
两维分别单调队列，这里求 $gcd$ 可以记忆化去掉一个 $log$
*G
依出题人的说法，这种 $m$ 是 4万的数据应该往 $bitset$ 上靠。。。
$n*m$ 在 1e9 左右的题都可以考虑一下 $bitset$，复杂度会除个 $64$
做法类似于 $shift-and$，首先对于每个 $a[i]$ 处理出他在 $b$ 数组中能匹配的位置 $s[i]$，这个用个 bitset 存下。
注意到本质不同的 $s$ 最多 $m$ 种，对于每个 $b[j]$ 求下 $s$ 即可
剩下的做法和 $shift-and$ 一致了，$f[i][j]$ 表示结尾为 $i$ 的子区间是否能匹配上 $b[1$~$j]$，记作 $cur$，转移：cur = (cur << 1 & s[i]) | 1
*H
赛中差一点调出，爆了 int 。。。
考虑三种情况：
- $a < b < x$，a 和 b 取 x 的两个前驱最优
- $a < x < b$，a 和 b 分别取 x 的前驱和后继最优
- $x < a < b$，首先 a 和 b 一定是连续的，其次考虑能组成三角形时的条件：$x+a>b$ 即 $x>b-a$，因此维护有序序列，权值为相邻两项的差，求 $>x$ 权值的 $min$ 即可
1 和 2 开个 $set$ 搞一搞就行
3: 请选择你喜欢的数据结构.jpg
*I
网络流平面图转对偶图
J
*K
待补，几何 给队友了。。。
Round 3
rank 62 (8/12)
好，dreamoon牛逼
A
贪心，有🐟就抓，倒序累计可以用鱼饵抓鱼的时间点
B
平衡树
模拟 手玩观察规律，护偏移量就行
C
几何，zyy牛逼
D
构造，zyy牛逼
先构造一个正方形，每次向右上挪点 ans+=2,变成一条链后拆两端的点，每次 ans+=2
E
dp，zzq牛逼
先sort，观察发现偶数 >=4 联通快内最优解为 2*(a[r]-a[l])，之后dp
F
数论，zzq牛逼
a b 不互质直接构造
分解 b，若 b 为 p^k 则无解
否则分解 b 为 p^k * b/p^k，exgcd解两个解
G
数据结构
并查集维护联通情况，vector 维护边集，启发式合并
list 可以做到 O(1) 合并
H
数据结构，每次找 [l,r] 中 p 最小的位置分治，笛卡尔树做到线性
*I
待补
*J
待补
*K
待补
L
签到
Round 4
rank 84 (4/10)
题不错，就是人太菜
*A
考虑 k 固定，二分答案记作 dis，每次贪心找叶子的 dis 级祖先并割掉这颗子树
一个性质若答案为 dis，则关键点数至少为 n/dis 级别的（考虑一条链）
那么总关键点数就是一个调和级数，对于每个 dis 用线段树模拟割子树的过程总复杂度两个 log
B
简单数论
*C
牛逼串串题 题面好难读
把后缀全丢到 Trie 上总点数为 10N 级别的
然后问题变成了求 Trie 上串本质不同字串个数，广义SAM
*D
待补
*E
待补
F
签到不会系列
*G
待补，搬砖题？？
H
数论，原题了
除了 1 和 > n/2 的质数外都能匹上
一种构造：
倒序考虑所有质数 p，处理他的所有未匹配的倍数，假设有 num 个
若 num 为偶数，则两两匹配，若为奇数，则留下 2*p
最后将所有留下的所有 2*pi 两两匹配
I
魔 幻 调 参
每次找一个未归类的点，假设他所有的话都是真的，扩一波点
然后以多数人原则来判断组内是否有错加入的点，及当 >cnt 的人认为他是一组时就认为是真的
然后做 bfs 扩点，同样也用同样的原则辨别真假
最后 cnt 调成 当前组内点数/2 过了。。。
*J
据说是分块，补一下