传送门:

BZOJ

洛谷

解题思路:

这题就是最裸的括号序列了…用树状数组是什么神奇操作…

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+10;
const ll mod=12345678910;
ll top,sta[maxn];
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;
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(ll x){print(x);puts("");}
int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        if(!x)top++;
        else{
            if(!sta[top])sta[top-1]=(sta[top-1]+1)%mod,sta[top--]=0;
            else sta[top-1]=(sta[top-1]+sta[top]*2)%mod,sta[top--]=0;
        }
    }write(sta[0]);
    return 0;
}

发表评论