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 的合法区间。

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000010
#define ll long long
#define fir first
#define sec second
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[N],sum;
int nxt[N],lst;
pair<int,int> ans[N<<1];
int main()
{
    n=read(),m=read();register int i,x;
    char ch=getchar();
    while(ch!='T'&&ch!='W')ch=getchar();
    for(int i=1;i<n;i++)
    {
        a[i]=1+(ch=='T');
        ch=getchar();
    }
    a[n]=1+(ch=='T');
    lst=n+1;
    for(i=n;i>=1;--i)
    {
        if(a[i]==1)lst=i;
        nxt[i]=lst-i,sum+=a[i];
    }

    sum=0;
    for(i=1;i<=n;++i)// cal ans[sum-1]
    {
        sum+=a[i];
        ans[sum].fir=1,ans[sum].sec=i;
        if(a[i]==2)
        {
            if(nxt[1]<nxt[i])
            ans[sum-1].fir=nxt[1]+2,ans[sum-1].sec=nxt[1]+i;
            else if(i+nxt[i]!=n+1)ans[sum-1].fir=1+nxt[i],ans[sum-1].sec=i+nxt[i];
        }
    }
    while(m--)
    {
        x=read();
        (x>sum||!ans[x].fir)?puts("NIE"):printf("%d %d\n",ans[x].fir,ans[x].sec);
    }
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 1000010

#define ll long long

#define fir first

#define sec second

using namespace std;

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

inline int read()

{

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

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[N],sum;

int nxt[N],lst;

pair<int,int> ans[N<<1];

int main()

{

n=read(),m=read();register int i,x;

char ch=getchar();

while(ch!='T'&&ch!='W')ch=getchar();

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

{

a[i]=1+(ch=='T');

ch=getchar();

}

a[n]=1+(ch=='T');

lst=n+1;

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

{

if(a[i]==1)lst=i;

nxt[i]=lst-i,sum+=a[i];

}

sum=0;

for(i=1;i<=n;++i)// cal ans[sum-1]

{

sum+=a[i];

ans[sum].fir=1,ans[sum].sec=i;

if(a[i]==2)

{

if(nxt[1]<nxt[i])

ans[sum-1].fir=nxt[1]+2,ans[sum-1].sec=nxt[1]+i;

else if(i+nxt[i]!=n+1)ans[sum-1].fir=1+nxt[i],ans[sum-1].sec=i+nxt[i];

}

while(m--)

{

x=read();

(x>sum||!ans[x].fir)?puts("NIE"):printf("%d %d\n",ans[x].fir,ans[x].sec);

}

zgz233

zgz233

BZOJ 2217 [Poi2011]Lollipop

l1ll5

Comments | 1 条评论

limfc