本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-21 10:20:59

感谢 weak ABCDE + G 题 LCT 送我上 1600 2kyu。
但距离 1 Dan 仍然还差 400 分，慢慢推进吧。

A

把后 3 位拆出来，根据题目判断一下就行了，另外注意这题的 atcoder better 翻译是错的。

B

开个数组记录每个位置是否有牙齿，模拟即可。

C

错误做法：

从 $1$ 到 $n$ 枚举每个位置的数，将其交换到正确位置。
Hack：

5
1 5 4 2 3

具体的，假设枚举到第 $i$ 个数，将其与 $a_i$ 位置的数交换，如果 $a_i \gt i$，并且 $a_{a_i}$ 不能放在 $i$ 位置，那么此算法就会使得 $a_{a_i}$ 被交换到错误的位置，而且不会再修正。
我赛时因此吃了 2 发罚时。

正确做法：

从 $1$ 到 $n$ 枚举每个数，记录其位置，设 $pos_i$ 为 $i$ 在数组中的位置。

依次枚举 $i$ 从 $1$ 到 $n$，如果 $pos_i \neq i$，那么交换 $a_i,a_{pos_i}$。
显然，每次交换都会让一个数处于正确位置，而不会造成另一个数从正确位置到错误位置。另外，当有 $n-1$ 个数被修正后，剩下那个数一定处于正确位置，所以操作次数不会超过 $n-1$。
submission

D

显然，最后的图中，每个连通块都必须构成完全图。
dfs 算出每个连通块大小，假设有 $k$ 个连通块，第 $i$ 个连通块有 $node_i$ 个点，$edg_i$ 个边，那么答案是 $\sum\limits_{i=1}^{k} (\frac{node_i(node_i - 1)}{2} - edg_i) = (\sum\limits_{i=1}^{k} \frac{node_i(node_i - 1)}{2}) - m$

然后就可以 $O(n)$ 做出来了。

E

设 $f(n)$ 为初始值为 $n$，变为 $0$ 的最小期望代价。
显然有：$f(n) = \sum\limits_{i=1}^{6}\frac{1}{6}(f(\lfloor \frac{n}{i} \rfloor)+y)$
本题解的傻逼作者赛时第一遍写了一发级数求和，然后过不去样例。
事实上移项就能做：
设 $s = \sum\limits_{i=2}^{6}\frac{1}{6}(f(\lfloor \frac{n}{i} \rfloor)+y)$。
那么 $f(n) = s + \frac{1}{6}(f(n)+y)$
$f(n) = s + \frac{1}{6}f(n)+\frac{1}{6}y$
$f(n)-\frac{1}{6}f(n) = s+\frac{1}{6}y$
$\frac{5}{6}f(n) = s+\frac{1}{6}y$
$f(n) = \frac{6}{5}(s+\frac{1}{6}y)$

F

用文艺平衡树模板应该能做，这里使用简单递归。
大概是这样的形式（我不会写标准伪代码，先这样吧）：

define pre[i] 假设左括号代表 +1，右括号 -1，那么前 i 个字符的前缀和是 pre[i]
void f(l,r,turn) \/\/ 处理 l,r 区间，l,r 为括号，turn 代表是否翻转 [l+1,r-1] 区间  
	define seqs 用于存储合法子序列的容器
	define sub_l = [l+1,r-1] 区间的第一个左括号的位置  
    	define sub_r = 最小的满足 pre[sub_r] = pre[sub_l-1] 的 sub_r 位置   
        while [sub_l,subr] 属于合法区间，且属于 [l+1,r-1] 子序列。  
        	seqs.append([sub_l,sub_r])
          	更新 sub_l,sub_r 到下一个合法区间  
        if turn == False  
        	正向枚举 seqs，记当前枚举到 [sl,sr]  
            		输出上一个区间与 [sl,sr] 之间的空隙。  
                	执行 f(sl,sr,1)  
                正向输出最后一个区间和 r 之间的空隙。  
        else  
        	反向枚举 seqs，记当前枚举到 [sl,sr]  
            		输出上一个区间与 [sl,sr] 之间的空隙。  
                	执行 f(sl,sr,0)  
                反向输出最后枚举的区间和 l 之间的空隙。    

My submission

G

@Iceturky 说他的做法是根号分治 + bitset，我不会这位大佬的做法，所以这里放一个思路较为简单的 LCT 做法，复杂度 $O(Q \log n)$，复杂度比根号分治 + bitset 优很多。

维护森林的加边显然可以 LCT。

另外一个就是求 $u,v$ 都相邻的点。

第一步，并查集判联通，如果不连通直接输出 0。

显然，这个点一定在 $u,v$ 的路径上，且这个点存在当且仅当 $u,v$ 路径上除了 $u,v$ 外只有一个点。

而 LCT 可以维护路径权值，那么我们只需要为将第 $i$ 个点的权值设置为 $i$，然后记 LCT 求得的路径权值和为 $s$，那么将 $u,v$ 从 $s$ 中剔除就可以了。

然后，要判断答案是否合法，此时可以用 map 记录哪些点是相连的。

由于是 Atcoder 的比赛，可以自由复制模板。