程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 2217 Poi2011 Lollipop

BZOJ 2217 Poi2011 Lollipop

編輯:C++入門知識

BZOJ 2217 Poi2011 Lollipop


題目大意:給定一個由1和2組成的序列,多次詢問是否存在一個區間滿足區間和=x
如果x>sum顯然無解
如果存在一個前綴和為x則直接輸出
否則一定存在一個前綴和[1,i]等於x+1
然後我們將左右端點同時右移 顯然如果某一時刻a[l]=1或者a[r+1]=1那麼我們就找到解了
記錄exti表示從i開始有多少個連續的2
如果ext1,那麼解為[1+ext1+1,i+ext1]
如果ext1≥extii+exti≠n+1,那麼解為[1+exti,i+exti]
否則無解
O(n)預處理所有答案即可

#include 
#include 
#include 
#include 
#define M 2002002
using namespace std;
int n,m,sum;
char s[M>>1];
int ext[M],l[M],r[M];
int main()
{
    int i,x;
    cin>>n>>m;
    scanf("%s",s+1);
    for(i=n;i;i--)
    {
        ext[i]=ext[i+1]+1;
        if(s[i]=='W')
            ext[i]=0;
    }
    for(i=1;i<=n;i++)
    {
        sum+=s[i]=='W'?1:2;
        l[sum]=1;r[sum]=i;
        if(s[i]=='T')
        {
            if(ext[1]sum || !l[x] )
            puts("NIE");
        else
            printf("%d %d\n",l[x],r[x]);
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved