BZOJ 3003 LED

发布于 2017-11-24  132 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3003

题意:多组数据,给出一个长度为 n 的 01 序列,初始均为 0,给出 k 个位置,要求最终状态中它们为 1,其余为 0,有 L 种操作方式,均为将任意一给定长度的区间状态取反,问可否达成目标状态,若可以,最小化操作次数。


一道挺有意思的题,好像原题是 CF 的?

首先考虑到如果每个点都被钦定了随便状压即可,但是 n 很大。

发现最终状态有很多连续的区间,都没有用,修改区间也是连续的,所以考虑差分一下前缀异或序列。

这样得到的答案状态最多和 2k 个位置有关,可以状压了。

通过预处理出将长度为 len 的区间取反的每个 len 的最小费用去优化转移,同时发现每次暴力转移是 1 的下标的复杂度不太优雅,转移 lowbit 即可,是常见的套路。

写了发记忆化跑的飞快,拿了个 rk1...

update 17/11/25

之前写的飞快的代码是假的= =,由于数据水能过... 现在的代码虽然慢了不过是真的...

 


一个非常弱的准退役OIER