题目链接：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 的合法区间。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#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); } } |
Comments | 1 条评论
大爷得上 QQ 啊