P4443 [COCI2017-2018#3] Dojave(线段树)
传送门 设(lim=2^n-1),对于一个区间([l,r])来说,如果(sumneq lim)且能换出(x)并换进(y)来,使得(sumbigoplus a_xbigoplus a_y=lim),那么(a_xbigoplus a_y)是个定值,所以如果对于每一个(x),它对应的(y)都在([l,r])之间,这个区间就是不合法的 因为有一一对应关系,所以整个区间是由若干个二元组构成的,(sum)不管异或上哪个二元组都等于(lim),所以如果二元组个数为偶数,所有二元组异或起来为(0),(sum)也为(0),如果二元组个数是奇数,那么(sum)就等于二元组的值,则有(a_xbigoplus a_y=lim) 综上,一个区间不合法当且仅当这个区间长度为(4)的倍数且这个区间内每一个的(x),与它对应的(a_xbigoplus a_y=lim)的(y)都在区间内 那么把每个点和它对应的(y)连边,那么这个区间内就不能有边连到外面。记(cnt_i)为点(i)被边覆盖的次数,那么当(i)作为不合法区间的右端点时,最右边的能作为这个不合法区间左端点的为(j),满足(cnt_j=cnt_i),且对于任意(j<p<i),(cnt_pneq cnt_i),简单来说就是前面一个与它覆盖次数相等的点 然而这个点不一定合法,所以可以用线段树之类的来做一下判定 记(dp_{i,0/1})为以(i)为右端点的,长度(len%4=0/2)的区间个数,那么则有转移[dp_{i,0}=dp_{las_i,len%4}+1] //minamoto #include<bits/stdc++.h> #define R register #define ls (p<<1) #define rs (p<<1|1) #define ll long long #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,I=b-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,C+1,stdout),C=-1;} void print(R int x){ if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='n'; } const int N=(1<<20)+5; struct node{int mn,mx;}tr[N<<2]; int to[N],las[N],a[N],pos[N],nxt[N],dp[N][2]; int n,m,cnt;ll ans; void build(int p,int l,int r){ if(l==r)return (void)(tr[p]={to[l],to[l]}); int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); tr[p].mn=min(tr[ls].mn,tr[rs].mn); tr[p].mx=max(tr[ls].mx,tr[rs].mx); } node query(int p,int r,int ql,int qr){ // if(l<=r)printf("%d %d %d %dn",r,ql,qr); if(ql<=l&&qr>=r)return tr[p]; int mid=(l+r)>>1;node res={m,0}; if(ql<=mid){ node d=query(ls,mid,qr); cmin(res.mn,d.mn),cmax(res.mx,d.mx); } if(qr>mid){ node d=query(rs,d.mx); }return res; } inline bool check(int l,int r){ node res=query(1,r); return res.mn>=l&&res.mx<=r; } int main(){ // freopen("testdata.in","r",stdin); n=read(),m=(1<<n); if(n==1)return puts("2"),0; fp(i,m)a[i]=read(),pos[a[i]]=i; fp(i,m)to[i]=pos[a[i]^(m-1)]; fp(i,m)if(to[i]<i)--cnt,las[i]=nxt[cnt],nxt[cnt]=i; else ++cnt,nxt[cnt]=i; ans=1ll*m*(m+1)/2; build(1,m),dp[0][0]=1; fp(i,m){ dp[i][0]=1; if(to[i]>i)continue; // printf("%d %dn",las[i]+1,i); if(check(las[i]+1,i)){ int len=(i-las[i])%4/2; ans-=dp[las[i]][len]; dp[i][0]=dp[las[i]][len]+1; dp[i][1]=dp[las[i]][len^1]; } }printf("%lldn",ans); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |