BZOJ 2217 [Poi2011]Lollipop

发布于 2017-11-28  243 次阅读


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

题意:一个只有 1 和 2 的序列,Q 次询问,每次查询序列中是否存在和为 x 的子序列,若存在,输出任意一个。


标签是乱加的。

考虑每个 1~i 的前缀序列,若目前的前缀和为 sum,下一位是 1,则可确定 sum+1 的合法区间,如果下一位是 2 呢?

同时将左右端点向右平移,如果下一位是 2 则没有影响,平移直至有一个的下一位为 1 位置,则找到了 sum+2-1 的合法区间。

 


一个非常弱的准退役OIER