• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

AGC 028E

admin

11月 28, 2021

这题首先可以想到按位贪心,
高位尽可能填0。
但是如何判断能不能填0呢?

原序列的上升位在划分后肯定还是上升位。
但是因为划分成了两个序列,可能会有一些新晋上升位。
可以证明:
如果存在一种(X)串,(Y)串上升数相等的方案,那么,必定存在一种(X)中的上升全为原串中的上升,或(Y)中的上升全为原串中上升的划分。
因为考虑(X,Y)均有新晋上升位的话,
那么交换这两个位置,(X,Y)的上升数均减一,因为一个串中新晋上升位的克星必定在另一个串中。

有了这个结论,先考虑(X)中上升全为原串上升。
考虑从左往右扫,第(i)位做决策时,
(A)的已有上升位为(lena)
(B)的已有上升位为(lenb)
([i+1,n])的原有上升位为(Q)
(Y)的原有上升位个数为(k)
(X)的原有上升位个数为(Q-k)
(B)中新晋上升为为(m)
列出方程$$lena+Q-k=lenb+k+m$$

[lena+Q-lenb=2*k+m
]

左边为常量。
问题转化为是否可以从([i+1,n])中选一个上升序列,
其中如果是原有上升位,贡献为(2),新晋上升位贡献为(1)
考虑用线段树维护奇偶最大值,因为如果(x)可以组成,那么(x-2)也必定可以组成。
代码已经咕了。

发表回复

您的电子邮箱地址不会被公开。