【NOI2019十二省联合省选】部分题简要题解

客官°小女子只卖身不卖艺 2022-10-02 15:41 128阅读 0赞

## Day 1 T1 异或粽子 ##

题意：给出一个长为n的序列，选择K个不完全重合的区间使得每个区间的异或值的总和最大。

题解：先做一个前缀异或和，对于每一个右端点我们记录三元组(l,r,x)表示在左端点在\\(\[l,r\]\\)内，最大异或值为x，塞进堆里。每次取出堆顶，并将该三元组对应的区间分裂成两个，重新扔回堆里。计算区间最大异或值利用可持久化字典树。  
时间复杂度\\(O(n\\log n+K\\log Maxvalue)\\)

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) #define N 500005 #define M 17000005 #define L 33 #define LL long long using namespace std; LL a[N],cf[L],ans,d[N]; int t[M][2],rt[N],mw,mx[M]; int n,cnt,n1; void ins(int k,int x,int w) { fod(i,mw,0) { int p=((a[w]&cf[i])>0); t[k][p^1]=t[x][p^1]; mx[k]=w; k=t[k][p]=++n1,x=t[x][p]; } mx[k]=w; } void read(LL &x) { x=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); } struct node { int x,l,r,w; LL v; friend bool operator <(node x,node y) { return x.v<y.v; } }; priority_queue<node> h; int get(int l,int r,LL v) { int k=rt[r]; fod(i,mw,0) { int p=(v&cf[i])>0; k=(t[k][1-p]&&mx[t[k][1-p]]>=l)?t[k][1-p]:t[k][p]; } return mx[k]; } int main() { freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); cin>>n>>cnt; cf[0]=1; fo(i,1,32) cf[i]=cf[i-1]*(LL)2; rt[0]=++n1; mw=0; fo(i,1,n) { read(a[i]); a[i]^=a[i-1]; fod(j,31,0) if(a[i]&cf[j]) {mw=max(mw,j);break;} } ins(1,0,0); fo(i,1,n) { rt[i]=++n1; ins(rt[i],rt[i-1],i); int w=get(0,i-1,a[i]); h.push((node){i,0,i-1,w,a[i]^a[w]}); } fo(i,1,cnt) { node p=h.top();h.pop(); ans+=p.v; int x=p.x; if(p.l<p.w) { int w=get(p.l,p.w-1,a[x]); h.push((node){x,p.l,p.w-1,w,a[x]^a[w]}); } if(p.r>p.w) { int w=get(p.w+1,p.r,a[x]); h.push((node){x,p.w+1,p.r,w,a[x]^a[w]}); } } printf("%lld\n",ans); }

## Day 1 T2 字符串问题 ##

题意：给出一个字符串S，将S中的一些子串定为A串，一些定为B串，给出了m组某个A串支配某个B串的关系，要求选出一个最长的字符串T，T为A串拼接而成，且任意相邻的两个A串(ai,ai+1)中，存在一个B串，它是ai+1的前缀，且被ai支配。求最长的长度，需要判是否无限长。

题解：将倒着做一遍，将后缀自动机的fail树弄出来（后缀树），然后我们将包含A，B串的节点设为关键点，将A,B串在这个节点上对应的长度分裂成一个新节点，同一个节点分裂出来的点从长度小到大连边，显然这个新构出来的树点数还是是\\(O(n)\\)的，将支配关系也看做边连起来，最后新建一个节点，每个A串向这个点连边表示结束。跑拓扑序DP即可，如果出环就是无限长。  
分裂节点、找节点的时候利用map和倍增来做，总的时间复杂度\\(O(n\\log n)\\)

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) #define N 900005 #define M 2000005 #define LL long long using namespace std; int t[N][26],n1,mx[N],ft[N][20],n,m,ma,mb,fs[N],nt[M],dt[M],pr[M],m1,mq,pt[2][N],len[N],d[N],rd[N],n2; LL f[N],ans; char st[N]; struct node { int x,y,p,w; friend bool operator <(node x,node y) { return (x.x<y.x)||(x.x==y.x&&x.y<y.y); } }ask[N]; map<int,int> h[N]; typedef map<int,int>::iterator IT; void link(int x,int y,int z) { nt[++m1]=fs[x]; dt[fs[x]=m1]=y; rd[y]++; pr[m1]=z; } void make() { int ls=1; n1=1; fo(j,0,25) t[1][j]=0; fod(i,n,1) { int c=st[i]-'a',p=ls; mx[ls=++n1]=n-i+1; fo(j,0,25) t[n1][j]=0; while(p&&!t[p][c]) t[p][c]=ls,p=ft[p][0]; if(p) { int q=t[p][c]; if(mx[q]==mx[p]+1) ft[ls][0]=q; else { ft[++n1][0]=ft[q][0]; mx[n1]=mx[p]+1; ft[q][0]=ft[ls][0]=n1; fo(j,0,25) t[n1][j]=t[q][j]; while(p&&t[p][c]==q) t[p][c]=n1,p=ft[p][0]; } } else ft[ls][0]=1; } } void jump(int &x,int e) { for(int j=19;mx[ft[x][0]]>=e;) { while(j&&mx[ft[x][j]]<e) j--; x=ft[x][j]; } } void read(int &x) { x=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); } void bfs() { d[0]=0; fo(i,1,n2) if(!rd[i]) d[++d[0]]=i; int l=0; while(l<d[0]) { int k=d[++l]; ans=max(ans,f[k]); for(int i=fs[k];i;i=nt[i]) { int p=dt[i]; f[p]=max(f[p],f[k]+pr[i]); rd[p]--; if(rd[p]==0) d[++d[0]]=p; } } } int main() { freopen("string.in","r",stdin); freopen("string.out","w",stdout); int t1; cin>>t1; while(t1--) { fo(i,1,n1) { mx[i]=0,h[i].clear(); ft[i][0]=0; } fo(i,1,n2) fs[i]=rd[i]=f[i]=0; m1=0; n1=n2=0; mq=0; scanf("\n%s",st+1); n=strlen(st+1); make(); fo(i,1,n1) h[i][mx[i]]=i; read(ma); fo(i,1,ma) { int l,r; read(l),read(r); ask[++mq]=(node){l,r,0,i}; len[i]=r-l+1; } read(mb); fo(i,1,mb) { int l,r; read(l),read(r); ask[++mq]=(node){l,r,1,i}; } sort(ask+1,ask+mq+1); fo(j,1,19) fo(i,1,n1) ft[i][j]=ft[ft[i][j-1]][j-1]; int k=1,j=n,w=1; n2=n1; ask[mq+1].x=n+1; fod(i,mq,1) { if(i==mq||ask[i].x!=ask[i+1].x) { fod(p,ask[i+1].x-1,ask[i].x) k=t[k][st[p]-'a']; w=k; } jump(w,ask[i].y-ask[i].x+1); if(!h[w][ask[i].y-ask[i].x+1]) h[w][ask[i].y-ask[i].x+1]=++n2; pt[ask[i].p][ask[i].w]=h[w][ask[i].y-ask[i].x+1]; } fo(i,1,n1) { IT it=h[i].begin(); int ls=ft[i][0]; for(;it!=h[i].end();it++) if(ls) link(ls,(*it).second,0),ls=(*it).second; } read(m); fo(i,1,m) { int x,y; read(x),read(y); link(pt[0][x],pt[1][y],len[x]); } n2++; ans=0; fo(i,1,ma) link(pt[0][i],n2,len[i]); bfs(); if(d[0]!=n2) printf("-1\n"); else printf("%lld\n",ans); } }

## Day 2 T1 皮配 ##

题意：有n所学校，c座城市，每个学校都属于某一个城市。现在有4位导师，分成两大阵营(1,2),(3,4)和两大派系(1,3),(2,4)。每个阵营和每个派系都有一个人数上限，每个学校有一个选手人数。现在问有多少种分配方案，满足同一个城市的学校选择同一个阵营，同一个学校的所有选手选择同一个导师。此外，有k所学校的选手一定不会选择某一位导师。

题解：若k=0，我们容易发现阵营限制和派系限制是独立的，由于一个城市必须选择相同阵营，且对于学校来说所属城市选哪个阵营没有关系。我们只需要将城市对于阵营人数做背包，学校对于派系做背包，最后答案乘在一起即可。  
若k!=0，我们将有限制的k个学校取出，剩余没有限制的学校和城市跟之前一样DP。剩下k所学校暴力做同时两维限制的背包即可，最后再将三个东西乘在一起。  
直接做容易卡常数，我们发现每所学校的人数不超过10，那么DP时和的上界对总人数取个min，单组数据复杂度就优化到是\\(O((n+c)M+kM\*10k)\\)

相当丑...

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) #define N 2505 #define LL long long #define mo 998244353 #define L 12 using namespace std; LL f[N][N],g[N][N],cf[L+1],l2[L+1],h[2][N][N][2]; int a[N],c[N],s[N],t,n,m,lim[4],mx,bp[N],fr[N],n1,m1,d[N],d2[N],bq[2][N][N][2]; bool bz[N]; bool cmp(int x,int y) { return (bp[x]<bp[y]); } bool cmp2(int x,int y) { return (bz[x]<bz[y]); } void inc(LL &x,LL v) { x=(x+v)%mo; } bool cmp3(int x,int y) { return fr[x]<fr[y]; } LL gf(int l,int r) { if(r>lim[2]) r=lim[2]; if(r<0) return 0; LL s=f[n1][r]; if(l>0) s=(s-f[n1][l-1]+mo)%mo; return s; } LL gg(int l,int r) { if(r>lim[0]) r=lim[0]; if(r<0||l>r) return 0; LL s=g[m1][r]; if(l>0) s=(s-g[m1][l-1]+mo)%mo; return s; } int main() { freopen("mentor.in","r",stdin); freopen("mentor.out","w",stdout); cin>>t; cf[0]=1; fo(i,1,L) l2[cf[i]=cf[i-1]<<1]=i; while(t--) { mx=0; memset(bz,0,sizeof(bz)); memset(s,0,sizeof(s)); memset(f,0,sizeof(f)); memset(h,0,sizeof(h)); memset(g,0,sizeof(g)); memset(bq,0,sizeof(bq)); memset(bp,255,sizeof(bp)); scanf("%d%d",&n,&m); int sum=0; fo(j,0,3) scanf("%d",&lim[j]),mx=max(mx,lim[j]); fo(i,1,n) { int x,y; scanf("%d%d",&x,&y); fr[i]=x; sum+=y; s[x]+=y,c[i]=y; d[i]=i; } int lc; scanf("%d",&lc); fo(i,1,lc) { int x,y; scanf("%d%d",&x,&y); bp[x]=y; bz[fr[x]]=1; } sort(d+1,d+n+1,cmp); n1=0; while(n1<n&&bp[d[n1+1]]<0) n1++; f[0][0]=1; fo(i,1,n1) { fo(j,0,lim[2]) { f[i][j]=f[i-1][j]; if(j>=c[d[i]]) inc(f[i][j],f[i-1][j-c[d[i]]]); } } fo(i,1,m) d2[i]=i; sort(d2+1,d2+m+1,cmp2); m1=0; while(m1<m&&!bz[d2[m1+1]]) m1++; g[0][0]=1; fo(i,1,m1) { fo(j,0,lim[0]) { g[i][j]=g[i-1][j]; if(s[d2[i]]>0&&j>=s[d2[i]]) inc(g[i][j],g[i-1][j-s[d2[i]]]); } } h[0][0][0][0]=1,bq[0][0][0][0]=n1; sort(d+n1+1,d+n+1,cmp3); int vr=0; fo(i,n1+1,n) { int i1=(i-n1)&1; if(i==n1+1||fr[d[i]]!=fr[d[i-1]]) vr+=s[fr[d[i]]]; fo(p,0,1) { int r1=min(lim[0],vr); fo(j,0,r1) { int uj=(p==0&&(i==n1+1||fr[d[i]]!=fr[d[i-1]]))?j-s[fr[d[i]]]:j; if(uj>=0) { int r2=min(10*(i-n1),lim[2]); fo(k,0,r2) { h[i1][j][k][p]=0; bq[i1][j][k][p]=i; if(!(i==n1+1||fr[d[i]]!=fr[d[i-1]])) { if(bp[d[i]]!=p*2&&k>=c[d[i]]) { if(bq[1^i1][uj][k-c[d[i]]][p]==i-1) inc(h[i1][j][k][p],h[1^i1][uj][k-c[d[i]]][p]); } if(bp[d[i]]!=p*2+1) { if(bq[1^i1][uj][k][p]==i-1) inc(h[i1][j][k][p],h[1^i1][uj][k][p]); } } else { if(bp[d[i]]!=p*2&&k>=c[d[i]]) { if(bq[1^i1][uj][k-c[d[i]]][0]==i-1) inc(h[i1][j][k][p],h[1^i1][uj][k-c[d[i]]][0]); if(bq[1^i1][uj][k-c[d[i]]][1]==i-1) inc(h[i1][j][k][p],h[1^i1][uj][k-c[d[i]]][1]); } if(bp[d[i]]!=p*2+1) { if(bq[1^i1][uj][k][0]==i-1) inc(h[i1][j][k][p],h[1^i1][uj][k][0]); if(bq[1^i1][uj][k][1]==i-1) inc(h[i1][j][k][p],h[1^i1][uj][k][1]); } } } } } } } fo(i,1,lim[2]) inc(f[n1][i],f[n1][i-1]); fo(i,1,lim[0]) inc(g[m1][i],g[m1][i-1]); int i1=(n-n1)&1; LL ans=0; fo(j,0,lim[0]) fo(k,0,lim[2]) { if(bq[i1][j][k][0]==n) inc(ans,h[i1][j][k][0]*gg(sum-j-lim[1],lim[0]-j)%mo*gf(sum-k-lim[3],lim[2]-k)%mo); if(bq[i1][j][k][1]==n) inc(ans,h[i1][j][k][1]*gg(sum-j-lim[1],lim[0]-j)%mo*gf(sum-k-lim[3],lim[2]-k)%mo); } printf("%lld\n",ans); } }

## Day 2 T2 春节十二响 ##

题意：给出一棵有根树，每个节点有点权，要将所有节点放入若干个集合中，每个集合的代价是集合中点权最大值。要求树上祖先和后代不能放入同一个集合。求最小总代价。

题解：先考虑一条链的情况（根不一定为链端），那一定是长一点的链上每个节点给一个集合，短的链的点塞进这些集合，根节点自成一个集合。深入思考可以发现一定是大的和大的点放在一起，小的和小的放在一起更优。同时这启发我们集合个数与深度有关。  
扩展到树上，我们采用长链剖分，对于每条长链维护一个堆记录集合的权值，合并子树的时候就暴力取出长链的前若干大合并，再暴力塞回去。  
由长链剖分的时间复杂度分析，这样做的时间复杂度是\\(O(n\\log n)\\)的。

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) #define N 200005 #define LL long long using namespace std; int fs[N],nt[2*N],dt[2*N],ft[N],n,m,pr[N],dep[N],son[N],m1; LL ans; priority_queue<int> h[N]; int rt[N],n1,u1[N]; void link(int x,int y) { nt[++m1]=fs[x]; dt[fs[x]=m1]=y; } void make(int k,int fa) { for(int i=fs[k];i;i=nt[i]) { int p=dt[i]; if(p!=fa) make(p,k),son[k]=(dep[p]>dep[son[k]])?p:son[k]; } dep[k]=dep[son[k]]+1; } void dfs(int k,int fa) { if(son[k]) dfs(son[k],k),rt[k]=rt[son[k]]; for(int i=fs[k];i;i=nt[i]) { int p=dt[i]; if(p!=fa&&p!=son[k]) dfs(p,k); } for(int i=fs[k];i;i=nt[i]) { int p=dt[i]; if(p!=fa&&p!=son[k]) { u1[0]=0; while(!h[rt[p]].empty()) { int x=h[rt[k]].top(),y=h[rt[p]].top(); h[rt[k]].pop(),h[rt[p]].pop(); u1[++u1[0]]=max(x,y); } fo(j,1,u1[0]) h[rt[k]].push(u1[j]); } } if(!rt[k]) rt[k]=++n1; h[rt[k]].push(pr[k]); } int main() { freopen("spring.in","r",stdin); freopen("spring.out","w",stdout); cin>>n; fo(i,1,n) scanf("%d",&pr[i]); fo(i,2,n) scanf("%d",&ft[i]),link(ft[i],i); make(1,0); dfs(1,0); ans=0; while(!h[rt[1]].empty()) { ans+=h[rt[1]].top(); h[rt[1]].pop(); } printf("%lld\n",ans); }

转载于:https://www.cnblogs.com/BAJimH/p/10689734.html