bzoj 2217 [Poi2011]Lollipop 乱搞贪心

2217: [Poi2011]Lollipop

Time Limit: 15 Sec Memory Limit: 64 MBSec Special Judge
Submit: 383 Solved: 159
[Submit][Status][Discuss]

Description

有一个长度为n的序列a1,a2,...,an。其中ai要么是1("W")，要么是2("T")。
现在有m个询问，每个询问是询问有没有一个连续的子序列，满足其和为q。

Input

第一行n，m (1<=n,m<=1000000)
第二行这个序列，起始编号为1，终止编号为n
下面每行一个询问q，询问有没有一个连续的子序列，满足其和为q (1<=q<=2000000)

Output

对于每个询问，输出一行，如果有，输出这个序列的起点和终点(如果有多个输出任意一个)；如果没有，输出“NIE”。

Sample Input

5 3
TWTWT
5
1
7

Sample Output

1 3
2 2
NIE

HINT

尚无SPJ，请不要提交

这题有一个性质，如果存在一个连续的序列和为k，那么在前缀和中一定存在k或者k+1

为什么？

可以证明，如果l-r和为k，那么后面部分，可以不断减去，前面部分不断加入，如果相差为2，那么后面部分减去一个1，或者2，使其

差<2就可以了，这样是保证了这个性质。

所以对于这道题，对于k判断前缀和十分有k，有的话直接输出，否则判断是否有k+1，如果有的话，就记录前面二的个数，后面哪个位置是1，

然后搞一搞就好了。

 #pragma GCC optimize(2)

 #pragma G++ optimize(2)

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #define N 27

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 #define MAXN 1000010

 #define MAXM 1010

 #define INF 1000000000

 #define MOD 1000000007

 #define eps 1e-8

 #define ll long long

 int n,m;

 char a[MAXN];

 int s[MAXN],nxt[MAXN];

 int v[MAXN<<];

 int main()

 {

     int i,x;

     scanf("%d%d%s",&n,&m,a+);

     for(i=;i<=n;i++)

     {

         s[i]=s[i-]++(a[i]=='T');

         v[s[i]]=i;

     }

     x=n+;

     for(i=n;i;i--)

     {

         if(a[i]=='W')x=i;

         nxt[i]=x-i;

     }

     while(m--)

     {

         scanf("%d",&x);

         if(v[x])printf("%d %d\n",,v[x]);

         else if(v[x+])

         {

             int l=,r=v[x+];

             if(nxt[l]<nxt[r])

             {

                 r+=nxt[l];

                 l+=nxt[l]+;

                 printf("%d %d\n",l,r);

             }else if(r+nxt[r]<=n)

             {

                 l+=nxt[r];

                 r+=nxt[r];

                 printf("%d %d\n",l,r);

             }else printf("NIE\n");

         }else printf("NIE\n");

     }

 }

NIE