Codeforces Round 909 (Div. 3)

__vector__ · 2023-11-19 01:13:47 · 个人记录

输麻了，G 的正确代码差 1s 交上，F 干脆没做。
总之手速还是不行。Div.3 没啥难题， AK 难度就在于手速。

A

如果第一次 Vanya 没赢，那么 Vova 就可以重置，让他永远不赢。

B

参考 n 的最大因子个数。
暴力能过。

C

设 dp_i 表示右端点为 i 的最大大小。

若 a_i 和 a_{i-1} 奇偶不同，dp_i = \max(a_i,dp_{i-1}+a_i)
否则，dp_i = a_i

最后答案是 \max(dp_1,dp_2,\cdots,dp_n)

D

设 pw_i 为 a_i 的质因数分解中 2 的出现次数。
设 bs_i 为 \frac{a_i}{2^{pw_i}}。

由小学数学可以推导得知，i,j 能配对，当且仅当 pw_i - a_i = pw_j - a_j。

然后 map 统计一下就好了。

E

最终要求没有任意一个 i 使得 a_i \gt a_{i+1}。

考虑每次操作的影响。

如果 a_i \gt a_{i+1}，那么它本质上消除了一对不合法的数对。

否则相当于不改变。

依次操作下来，当最后一个不合法的 i 被执行操作，排序也就完成了。
设最后一个不合法的 i 为 lst。

考虑 [1,lst] 之间每个 i 被执行的影响。

第 i 个，如果跳出了 [1,lst] 的范围，那么没啥事。
如果没跳出（只要是没跳到 lst 后面就算），那么稍稍想一下依赖关系，必然是陷入了无限循环，无解。

那么如何判断无限循环呢？

只要有 [1,lst] 任意一个 i 操作之后位置不改变，那么一定陷入无限循环，从而间接导致其他的 i 跳不出去。

F

默认根是 1。

为了方便实现，我们可以仅仅用两条链构造出两个距离为 d_i 的叶子。

先根据 d_1 构造出大概是这样的两条链（从 1 出发）：

第一条链长度固定是 1，而第二条链的长度则根据 d_i 进行变化，这个例子中，d_i = 4。

剩下的节点干什么呢？因为第二天链的长度需要时刻变化，所以我们还是从 1 出发，新建第三条链，进行存储。

大概长这样（n=8,d_i=4)

第 3 条链是 1,6,7,8 组成的。

需要适应 d_i 时，直接配合第三条链进行切割/接尾操作就行。

我为了方便开了 3 个 std::list

G

我们可以将这个问题转化为一个更清新的问题：

给定一个数列 p，并推导得到一个数列 p{'}。

设 size_i 为 i 为根的子树大小，dfn_i 是 i 的 dfs 序。