• 周五. 4月 26th, 2024

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)也必定可以组成。
代码已经咕了。

《AGC 028E》有一个想法
  1. Gut Vita™ is a daily supplement that helps consumers to improve the balance in their gut microbiome, which supports the health of their immune system. It supports healthy digestion, even for consumers who have maintained an unhealthy diet for a long time. https://gutvitabuynow.us/

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注