首页 > 代码库 > noi2017 day1 题解
noi2017 day1 题解
d1t1
用线段树维护区间是否全0/全1，叶子上压位维护对应位置的数位，加法首先对叶子加，如需进位则向右找到第一个不是全1的叶子+1，中间部分全1部分打上反转标记，减法同理。
#include<cstdio>int _(){ int x=0,f=1,c=getchar(); while(c<48)c==‘-‘?f=-1:0,c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x*f;}const int N=1100127;typedef unsigned int u32;int n,_l,flag;u32 _ans;int mx;struct node{ node*lc,*rc; int rev; u32 _or,_and; void revs(){ rev^=1; _or=~_or; _and=~_and; } void up(){ _or=lc->_or|rc->_or; _and=lc->_and&rc->_and; } void dn(){ if(rev){ rev^=1; lc->revs(); rc->revs(); } } void find(int L,int R){ if(L==R){ _ans=_or; return; } int M=(L+R)>>1; dn(); if(_l<=M)lc->find(L,M); else rc->find(M+1,R); } void inc(int L,int R){ if(L==R){ flag=(_and+_ans<_and); _and+=_ans; _or=_and; return; } int M=(L+R)>>1; dn(); if(_l<=M)lc->inc(L,M); else rc->inc(M+1,R); up(); } void dec(int L,int R){ if(L==R){ flag=(_and-_ans>_and); _and-=_ans; _or=_and; return; } int M=(L+R)>>1; dn(); if(_l<=M)lc->dec(L,M); else rc->dec(M+1,R); up(); } void inc1(int L,int R){ if(flag)return; if(_l<=L){ if(_and==~0u)return revs(); if(L==R){ _or=++_and; flag=1; return; } } dn(); int M=(L+R)>>1; if(_l<=M)lc->inc1(L,M); rc->inc1(M+1,R); up(); } void dec1(int L,int R){ if(flag)return; if(_l<=L){ if(_or==0u)return revs(); if(L==R){ _or=--_and; flag=1; return; } } dn(); int M=(L+R)>>1; if(_l<=M)lc->dec1(L,M); rc->dec1(M+1,R); up(); }}ns[N*2],*np=ns,*rt;node*build(int L,int R){ node*w=np++; if(L<R){ int M=(L+R)>>1; w->lc=build(L,M); w->rc=build(M+1,R); } w->_or=w->_and=w->rev=0; return w;}void inc(u32 a,int x){ if(!a)return; _ans=a;_l=x; rt->inc(0,mx); if(flag){ flag=0; _l=x+1; rt->inc1(0,mx); }}void dec(u32 a,int x){ if(!a)return; _ans=a;_l=x; rt->dec(0,mx); if(flag){ flag=0; _l=x+1; rt->dec1(0,mx); }}int main(){ n=_();_();_();_(); mx=n+10; if(mx<1000)mx=1000; rt=build(0,mx); for(int i=0;i<n;++i){ if(_()==1){ int a0=_(),b=_(); int b1=b>>5,b2=b&31; if(a0>0){ u32 a=a0; inc(a<<b2,b1); if(b2)inc(a>>(32-b2),b1+1); }else if(a0<0){ u32 a=-a0; dec(a<<b2,b1); if(b2)dec(a>>(32-b2),b1+1); } }else{ int k=_(); _l=k>>5; rt->find(0,mx); printf("%d\n",_ans>>(k&31)&1); } } return 0;}
d1t2
预处理询问涉及的串的hash值，用散列表离散化，对每次修改操作，枚举新产生/消失的长度<=50的子串，若其hash值等于某个询问，则对应在散列表上记录贡献。
#include<cstdio>#include<cstring>#include<vector>typedef unsigned long long u64;const int P=998244353,N=250007,Q=500007,pz=13999133,H=1<<25;int _(){ int x=0,f=1,c=getchar(); while(c<48)c==‘-‘?f=-1:0,c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x*f;}int n,m,mk=1;int v[N],nx[N],pv[N];char ss[11000007];u64 h1[11000007],pp[107];int qs[Q][3];std::vector<int>qv[Q];u64 hx[H+777];int hy[H+777];int ins(u64 x){ int w=(x^x>>25^x>>39)&(H-1); while(hx[w]){ if(hx[w]==x)return w; w=(w+1237)&(H-1); } hx[w]=x; return w;}bool inc(u64 x,int a){ int w=(x^x>>25^x>>39)&(H-1); while(hx[w]){ if(hx[w]==x){ hy[w]+=a; return 1; } w=(w+1237)&(H-1); } return 0;}int ls[111],lp,t0[11];int ms[111],mp=0;int min(int a,int b){return a<b?a:b;}int max(int a,int b){return a>b?a:b;}void chk(int a,int b,int c){ lp=mp=0; for(int i=1,w=a;i<mk&&w;++i,w=pv[w])ls[lp++]=v[w]; for(int i=lp-1;i>=0;--i)ms[++mp]=ls[i]; for(int i=1,w=b;i<mk&&w;++i,w=nx[w])ms[++mp]=v[w]; for(int i=1;i<=mp;++i)h1[i]=h1[i-1]*pz+ms[i]; for(int i=0;i<lp;++i){ int r=min(mp,i+mk); for(int j=lp+1;j<=r;++j){ inc(h1[j]-h1[i]*pp[j-i],c); } }}int main(){ n=_();m=_(); pp[0]=1; for(int i=1;i<=100;++i)pp[i]=pp[i-1]*pz; for(int i=1;i<=n;++i)++t0[v[i]=_()]; for(int i=1;i<=m;++i){ qs[i][0]=_(); if(qs[i][0]==1){ qs[i][1]=_(); qs[i][2]=_(); }else if(qs[i][0]==2){ qs[i][1]=_(); }else{ scanf("%s",ss+1); int len=strlen(ss+1); int k=_(); if(k>mk)mk=k; for(int j=1;j<=len;++j)h1[j]=h1[j-1]*pz+ss[j]-‘0‘; qv[i].resize(max(len-k+1,0)); for(int j=k;j<=len;++j){ qv[i][j-k]=ins(h1[j]-h1[j-k]*pp[k]); } } } for(int i=1;i<=6;++i)inc(i,t0[i]); for(int i=1;i<=m;++i){ if(qs[i][0]==1){ int a=qs[i][1],b=qs[i][2]; nx[a]=b;pv[b]=a; chk(a,b,1); }else if(qs[i][0]==2){ int a=qs[i][1],b=nx[a]; nx[a]=pv[b]=0; chk(a,b,-1); }else if(qs[i][0]==3){ int ans=1; for(int j=0;j<qv[i].size()&&ans;++j){ ans=u64(ans)*hy[qv[i][j]]%P; } printf("%d\n",ans); } } return 0;}
d1t3
询问=k拆成<=k和<=k-1
只需考虑原矩形每一列最下面的一个可选位置，令f[x][y]表示最下方x行可选，第x+1行存在不可选位置，宽度y的矩形 合法的概率，则
$f[x][y]=\sum_{i=0}^{y-1}f[>=x][i]f[>x][y-1-i]$
这里dp不处理x=0的部分，只考虑x>0，因此0<xy<=k，暴力转移的时间复杂度可以接受
把0的影响表示为一个常系数线性齐次递推的形式，转化为多项式幂取模计算
#include<cstdio>#include<cstring>const int P=998244353;typedef long long i64;const i64 X=(1ll<<45)/P*P;int pw(int a,int n){ int v=1; for(;n;n>>=1,a=i64(a)*a%P)if(n&1)v=i64(v)*a%P; return v;}int n,m,q,A,B;int f[1007][1007],g[1007][1007],cs[1007],v[1007],f0[1007],a0[1007],a1[1007];i64 c[2007];void mul(int*a,int*b,int m){ memset(c,0,sizeof(c)); for(int i=0;i<=m;++i){ for(int j=0;j<=m;++j)c[i+j]+=i64(a[i])*b[j]; if(i%8==7||i==m)for(int j=0;j<=m+i;++j)c[j]-=(c[j]>>45)*X; } for(int i=m*2;i>m;--i){ c[i]%=P; for(int j=1;j<=m+1;++j)c[i-j]+=c[i]*v[j]; if((m*2-i)%8==7)for(int j=0;j<i;++j)c[j]-=(c[j]>>45)*X; } for(int i=0;i<=m;++i)a[i]=c[i]%P;}int cal(int n,int m,int q){ if(!m)return pw(1-q,n); memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); g[m+1][0]=1; cs[0]=1-q; for(int i=1;i<=m;++i)cs[i]=cs[i-1]*i64(q)%P; for(int i=m;i;--i){ memcpy(g[i],g[i+1],sizeof(g[0])); for(int j=1;j<=m/i;++j){ for(int k=0;k<j;++k){ f[i][j]=(f[i][j]+i64(g[i][k])*g[i+1][j-1-k])%P; } f[i][j]=i64(cs[i])*f[i][j]%P; g[i][j]=(f[i][j]+g[i][j])%P; } } for(int i=1;i<=m+1;++i)v[i]=g[1][i-1]*i64(cs[0])%P; f0[0]=pw(cs[0],P-2); for(int i=1;i<=m+1;++i){ f0[i]=0; for(int j=1;j<=i;++j)f0[i]=(f0[i]+f0[i-j]*i64(v[j]))%P; } memset(a0,0,sizeof(a0)); memset(a1,0,sizeof(a1)); a0[0]=a1[1]=1; for(;n;n>>=1,mul(a1,a1,m))if(n&1)mul(a0,a1,m); int s=0; for(int i=0;i<=m;++i)s=(s+i64(a0[i])*f0[i])%P; return s;}int main(){ scanf("%d%d%d%d",&n,&m,&A,&B); ++n; q=i64(A)*pw(B,P-2)%P; int s=(cal(n,m,q)-cal(n,m-1,q))%P; printf("%d\n",(s+P)%P); return 0;}
noi2017 day1 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。