比赛：CF2131 Div.3

CF2131 Div.3

D. Arboris Contractio

缩成直径最小的时候就是菊花图。

考虑固定菊花图的中心，把该中心设为树根，那么每次操作

(s,t)

时，

s

一定为根，

t

一定为叶子，答案就是以该点为根时，与根距离

>1

的叶子数量。考虑证明：

假定这个不是答案，只是我们给树定义了一个权值。
菊花图的权值为 $0$ ，不是菊花图的树权值一定 $>0$ 。
假设操作了一次 $(s,t)$ ，
- 若 $s$ 不为根，那么树权值一定不减。
- 若 $s$ 为根，但 $t$ 不为叶子，那么树的权值不变。
- 否则 $s$ 为根，且 $t$ 为叶子，树的权值刚好减一。
综上所述，树的最小操作次数就是该树的权值。

然后用简单换根 DP 即可

O(n)

解决。

Code

E. Adjacent XOR

每个

i

只能操作一次，也就是每个

i

必须一步到位，那么只需考虑

i

能从

i+1

处取什么来异或。发现要么不取，要么取

b_{i+1}

，要么取

a_{i+1}

，因此

O(n)

check 即可。

Code

F. Unjust Binary Life

假设要走到

(x,y)

，那么

a[1,x]

和

b[1,y]

必须都变成同一个数。

因此记一下

a0(i),a1(i),b0(i),b1(i)

表示前缀

0,1

个数，答案就是

\min(a0(x)+b0(y),a1(x)+b1(y))

。

枚举

x

，考虑如何计算贡献。推一下式子：

\begin{aligned} a0(x)+b0(y)&<a1(x)+b1(y) \\ a0(x)-a1(x)&<b1(y)-b0(x) \end{aligned}

于是拿桶预处理一下即可。

Code

G. Wafu!

设

f(i)

表示完全删掉

i

需要多少步，

f(1)=1

，

f(i)=1+\sum\limits_{j=1}^{i-1} f(j)

，发现可以把值域缩小到

O(\log k)

级别。

因此直接暴力模拟即可。复杂度大概是

O(n\log n + \log^2 k)

。

Code

文章操作

CF2131 Div.3

D. Arboris Contractio

E. Adjacent XOR

F. Unjust Binary Life

G. Wafu!

H. Sea, You & copriMe

相关推荐

评论

比赛：CF2131 Div.3