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

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);
}