即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

BZOJ 1095: [ZJOI2007]Hide 捉迷藏

系统运维 cgh_Andy 754℃ 0评论

一时兴起觉得这题的代码打的挺帅挺快的留个代码。

我的定义好像跟他的略有偏差 貌似表示左右括号的一些东西是反的

这题好腻害啊 膜了岛娘的括号序列
岛娘
 QAQ

#include
#include
#include
#include
using namespace std;
const int N=100005,inf=1e9;
inline int read()
{
    char ch=getchar(); int x=0,f=1;
    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;
}
struct node{
    int y,next;
}a[N<<1]; int len,first[N];
int v[N*3],cnt,p[N]; bool c[N];
struct T{
    int l,r,l1,r1,l2,r2,d,c1,c2;
    void in(int x){
        d=-inf,c1=c2=0;
        if(v[x]==-1)c1++;
        if(v[x]==-2)c2++;
        if(v[x]>0 && (!c[v[x]]))
            l1=l2=r1=r2=0;
        else l1=l2=r1=r2=-inf;
    }
}t[12*N];
void ins(int x,int y)
{
    a[++len].y=y,a[len].next=first[x],first[x]=len;
    a[++len].y=x,a[len].next=first[y],first[y]=len;
}
void dfs(int x,int fa)
{
    v[++cnt]=-1,v[++cnt]=x,p[x]=cnt;
    for(int k=first[x];k;k=a[k].next)
        if(a[k].y!=fa)dfs(a[k].y,x);
    v[++cnt]=-2;
}
inline T merge(T s1,T s2)
{
    T s;
    int a=s1.c1,b=s1.c2,c=s2.c1,d=s2.c2;
    s.l=s1.l,s.r=s2.r;
    s.d=max(s1.d,s2.d);
    s.d=max(s.d,max(s1.r1+s2.l2,s1.r2+s2.l1));
    if(a>1;
    bulid(lc,l,mid);
    bulid(rc,mid+1,r);
    t[x]=merge(t[lc],t[rc]);
}
void change(int x,int u)
{
    int l=t[x].l,r=t[x].r;
    if(l==r){t[x].in(l); return;}
    int lc=x<<1,rc=lc+1,mid=(l+r)>>1;
    if(u<=mid)change(lc,u);
    else change(rc,u);
    t[x]=merge(t[lc],t[rc]);
}
int main()
{
    int i,n=read(),m,x,y,black=n;
    for(i=1;i





转载请注明:CodingBlog » BZOJ 1095: [ZJOI2007]Hide 捉迷藏

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情