BZOJ 2217 [Poi2011]Lollipop


题目链接: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 的合法区间。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2217 [Poi2011]Lollipop


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,