论如何 AK ABC350

· · 个人记录

感谢 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 的比赛，可以自由复制模板。