POI2015题解

POI2015题解

吐槽一下为什么POI2015开始就成了破烂波兰文题目名了啊。。。

咕了一道3748没写打表题没什么意思，还剩\(BZOJ\)上的\(14\)道题。

[BZOJ3746][POI2015]Czarnoksiężnicy okrągłego stołu

这个题真的神仙。

\(p=0\)，答案是\([n=1]\)。

\(p=1\)，答案是\([n=1]+[n=2,k=0]\)。

\(p=2\)，只有至多两种方案，即\(n\)左手边坐\(n-1,n-3...\)，右手边坐\(n-2,n-4...\)或是反过来。分别判一下是否满足限制即可。

\(p=3\)。

考虑增量构造，即按编号从大到小加入。当我们加入\(x\)时，它当前的左右两边一定要是\(x+1,x+2,x+3\)三者中的其二，否则将会不合法。可以发现，我们关心的只有\(x+1,x+2,x+3\)这三个数两两之间是否直接相邻以及它们的相对顺序（顺/逆时针排列），所以设状态\(f_{i,s,j}\)表示填了\(i...n\)，\(i,i+1,i+2\)的排列方式是顺时针还是逆时针，\(i\)与\(i+1\)，\(i\)与\(i+2\)，\(i+1\)与\(i+2\)之间分别有没有大于\(i+2\)的数（也就是是否直接相邻）。

转移的时候只有至多三种插入方式，分别讨论一下是否合法即可。注意最后\(i=1\)时要特判\(i,i+1,i+2\)之间是否合法。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
const int mod = 1e9+7;
int n,k,p,f[N][2][8],a[N],b[N][7];
inline bool chk(int x,int y){
	if (abs(x-y)>p) return false;
	return !b[x][y-x+3];
}
inline bool judge(int x,int s,int j,int k){
	int s1=j>>2,s2=j>>1&1,s3=j&1,fg=1;
	if (!s)
		if (!k) fg&=(!s1)&(s2|chk(x+3,x+1))&(s3|chk(x+2,x+3));
		else if (k&1) fg&=(!s2)&(s3|chk(x+2,x+3))&chk(x+3,x);
		else fg&=(!s3)&(s2|chk(x+3,x+1))&chk(x,x+3);
	else
		if (!k) fg&=(!s1)&(s2|chk(x+1,x+3))&(s3|chk(x+3,x+2));
		else if (k&1) fg&=(!s2)&(s3|chk(x+3,x+2))&chk(x,x+3);
		else fg&=(!s3)&(s2|chk(x+1,x+3))&chk(x+3,x);
	if (x==1)
		if (!s)
			if (!k) fg&=chk(x+1,x)&chk(x,x+2);
			else if (k&1) fg&=chk(x,x+1)&(s1|chk(x+1,x+2));
			else fg&=chk(x+2,x)&(s1|chk(x+1,x+2));
		else
			if (!k) fg&=chk(x,x+1)&chk(x+2,x);
			else if (k&1) fg&=chk(x+1,x)&(s1|chk(x+2,x+1));
			else fg&=chk(x,x+2)&(s1|chk(x+2,x+1));
	return fg;
}
inline void upt(int &x,int y){x+=y;x>=mod?x-=mod:x;}
int main(){
	n=gi();k=gi();p=gi();
	for (int i=1;i<=k;++i){
		int x=gi(),y=gi();
		if (abs(x-y)>3) continue;
		b[x][y-x+3]=1;
	}
	if (p==0) return puts(n==1?"1":"0"),0;
	if (p==1) return puts(n==1||(n==2&&k==0)?"1":"0"),0;
	if (p==2){
		if (n<=2) return puts(n==1||(n==2&&k==0)?"1":"0"),0;
		int fg=1,ans=0;a[1]=n;
		for (int i=2,j=n-1;j>0;++i,j-=2) a[i]=j;
		for (int i=n,j=n-2;j>0;--i,j-=2) a[i]=j;
		for (int i=1;i<n;++i) fg&=chk(a[i],a[i+1]);fg&=chk(a[n],a[1]);
		ans+=fg;fg=1;
		for (int i=2,j=n-2;j>0;++i,j-=2) a[i]=j;
		for (int i=n,j=n-1;j>0;--i,j-=2) a[i]=j;
		for (int i=1;i<n;++i) fg&=chk(a[i],a[i+1]);fg&=chk(a[n],a[1]);
		ans+=fg;printf("%d\n",ans);
	}
	if (p==3){
		if (n<=2) return puts(n==1||(n==2&&k==0)?"1":"0"),0;
		f[n-2][0][0]=f[n-2][1][0]=1;
		for (int i=n-2;i>1;--i)
			for (int s=0;s<2;++s)
				for (int j=0;j<8;++j)
					if (f[i][s][j]){
						if (judge(i-1,s,j,0)) upt(f[i-1][s^1][1],f[i][s][j]);
						if (judge(i-1,s,j,1)) upt(f[i-1][s][2|j>>2],f[i][s][j]);
						if (judge(i-1,s,j,2)) upt(f[i-1][s][4|j>>2],f[i][s][j]);
					}
		int ans=0;
		for (int s=0;s<2;++s)
			for (int j=0;j<8;++j)
				upt(ans,f[1][s][j]);
		printf("%d\n",ans);
	}
	return 0;
}

[BZOJ3747][POI2015]Kinoman

从左到右枚举右端点，维护左端点的答案。

需要支持的操作是区间加和区间取最大值。用线段树维护即可。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
int n,m,a[N],lst[N],pos[N],b[N];long long mx[N<<2],tag[N<<2],ans;
void modify(int x,int l,int r,int ql,int qr,int v){
	if (l>=ql&&r<=qr) {mx[x]+=v;tag[x]+=v;return;}
	int mid=l+r>>1;
	if (ql<=mid) modify(x<<1,l,mid,ql,qr,v);
	if (qr>mid) modify(x<<1|1,mid+1,r,ql,qr,v);
	mx[x]=max(mx[x<<1],mx[x<<1|1])+tag[x];
}
int main(){
	n=gi();m=gi();
	for (int i=1;i<=n;++i) lst[i]=pos[a[i]=gi()],pos[a[i]]=i;
	for (int i=1;i<=m;++i) b[i]=gi();
	for (int i=1;i<=n;++i){
		modify(1,1,n,1,i,b[a[i]]);
		if (lst[i]){
			if (lst[lst[i]]) modify(1,1,n,1,lst[lst[i]],b[a[i]]);
			modify(1,1,n,1,lst[i],-b[a[i]]<<1);
		}
		ans=max(ans,mx[1]);
	}
	printf("%lld\n",ans);return 0;
}

[BZOJ3749][POI2015]Łasuchy

对每盘食物设一个状态\(S=\{0,1,2,3\}\)表示是否每相邻的两个人吃，然后就可以大力\(dp\)了。

枚举起点，\(dp\)一圈回来判一下是否合法。记录前驱输出方案即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
int n,a[N],S,f[N][4],g[N][4],b[N];
bool dp(){
	memset(f,0,sizeof(f));f[0][S]=1;
	for (int i=1;i<=n;++i){
		if (f[i-1][1]&&a[i-1]>=a[i]) f[i][0]=1,g[i][0]=1;
		else if (f[i-1][3]&&a[i-1]>=2*a[i]) f[i][0]=1,g[i][0]=3;

		if (f[i-1][1]&&2*a[i-1]>=a[i]) f[i][1]=1,g[i][1]=1;
		else if (f[i-1][3]&&a[i-1]>=a[i]) f[i][1]=1,g[i][1]=3;

		if (f[i-1][0]&&a[i]>=a[i-1]) f[i][2]=1,g[i][2]=0;
		else if (f[i-1][2]&&2*a[i]>=a[i-1]) f[i][2]=1,g[i][2]=2;

		if (f[i-1][0]&&a[i]>=2*a[i-1]) f[i][3]=1,g[i][3]=0;
		else if (f[i-1][2]&&a[i]>=a[i-1]) f[i][3]=1,g[i][3]=2;
	}
	return f[n][S];
}
int main(){
	n=gi();
	for (int i=1;i<=n;++i) a[i]=gi();a[0]=a[n];
	for (S=0;S<4;++S) if (dp()) break;
	if (S==4) return puts("NIE"),0;
	for (int i=n;i;--i){
		if (S&1) b[i]=i;
		if (S&2) b[i-1?i-1:n]=i;
		S=g[i][S];
	}
	for (int i=1;i<=n;++i) printf("%d ",b[i]);
	puts("");return 0;
}

[BZOJ3750][POI2015]Pieczęć

确定最左上的那个点，直接染色就好了。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1005;
int n,m,a,b,t,f,g[N][N],dx[N*N],dy[N*N];char s[N];
bool cover(int p,int q){
	for (int i=1;i<=t;++i){
		int x=p+dx[i],y=q+dy[i];
		if (x<1||x>n||y<1||y>m||!g[x][y]) return false;
		g[x][y]=0;
	}
	return true;
}
int main(){
	int Case=gi();while (Case--){
		n=gi();m=gi();a=gi();b=gi();t=0;f=1;
		for (int i=1;i<=n;++i){
			scanf("%s",s+1);
			for (int j=1;j<=m;++j) g[i][j]=s[j]=='x';
		}
		for (int i=1;i<=a;++i){
			scanf("%s",s+1);
			for (int j=1;j<=b;++j)
				if (s[j]=='x') dx[++t]=i,dy[t]=j;
		}
		for (int i=2;i<=t;++i) dx[i]-=dx[1],dy[i]-=dy[1];
		dx[1]=dy[1]=0;
		for (int i=1;i<=n;++i)
			for (int j=1;j<=m;++j)
				if (g[i][j]&&!cover(i,j)) {f=0;break;}
		puts(f?"TAK":"NIE");
	}
	return 0;
}

[BZOJ4377][POI2015]Kurs szybkiego czytania

设匹配位置的第一个下标位置为\(x\)。

那么串\(s\)相当于给出限制：\(a(x+i)+b\mod n\ge p\)或是\(a(x+i)+b\mod n< p\)。

于是就可以确定\(ax\)这个量在\([0,n)\)内的取值范围，或者说是不能取到的范围

所以拿个扫描线维护一下这个东西就好了。

注意最后\(m-1\)个位置是无论如何不能匹配的，所以还要特殊处理一下。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
int n,a,b,p,m,cnt,ans;char s[N];
struct node{
	int x,y;
	bool operator < (const node &b) const
		{return x<b.x;}
}t[N<<3];
void cover(int l,int r){
	t[++cnt]=(node){l,1};t[++cnt]=(node){r+1,-1};
}
int main(){
	n=gi();a=gi();b=gi();p=gi();m=gi();scanf("%s",s+1);
	for (int i=1,x=b;i<=m;++i,(x+=a)%=n)
		if (s[i]-'0')
			if (x<p) cover(n-x,n-1),cover(0,p-x-1);
			else cover(n-x,p+n-x-1);
		else
			if (x<=p) cover(p-x,n-x-1);
			else cover(0,n-x-1),cover(p+n-x,n-1);
	for (int i=n-m+1;i<n;++i) cover(1ll*a*i%n,1ll*a*i%n);
	sort(t+1,t+cnt+1);t[++cnt]=(node){n,0};
	for (int i=1,s=0;i<=cnt;++i){
		if (t[i].x!=t[i-1].x)
			if (!s) ans+=t[i].x-t[i-1].x;
		s+=t[i].y;
	}
	printf("%d\n",ans);
	return 0;
}

[BZOJ4378][POI2015]Logistyka

对于每次询问，小于等于\(s\)的数可以被减成零，而大于\(s\)的数至多减\(s\)，所以就只需要比较\(c\times s\)与小于等于\(s\)的数之和\(+\)大于\(s\)的数的个数\(\times s\)这两个数大小就行了。用两个\(BIT\)维护。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define ll long long
const int N = 1e6+5;
int n,m,op[N],a[N],b[N],o[N],len,val[N],c1[N];ll c2[N];

void mdf1(int k,int v){while(k<=len)c1[k]+=v,k+=k&-k;}
int qry1(int k){int s=0;while(k)s+=c1[k],k^=k&-k;return s;}
void mdf2(int k,int v){while(k<=len)c2[k]+=v,k+=k&-k;}
ll qry2(int k){ll s=0;while(k)s+=c2[k],k^=k&-k;return s;}

void add(int x){mdf1(x,1),mdf2(x,o[x]);}
void del(int x){mdf1(x,-1),mdf2(x,-o[x]);}

int main(){
	n=gi();m=gi();
	for (int i=1;i<=m;++i) op[i]=getchar()=='U',a[i]=gi(),o[++len]=b[i]=gi();
	o[++len]=0;sort(o+1,o+len+1);len=unique(o+1,o+len+1)-o-1;
	for (int i=1;i<=m;++i) b[i]=lower_bound(o+1,o+len+1,b[i])-o;
	mdf1(1,n);
	for (int i=1;i<=n;++i) val[i]=1;
	for (int i=1;i<=m;++i)
		if (op[i]) del(val[a[i]]),val[a[i]]=b[i],add(val[a[i]]);
		else puts(1ll*(qry1(len)-qry1(b[i]))*o[b[i]]+qry2(b[i])>=1ll*a[i]*o[b[i]]?"TAK":"NIE");
	return 0;
}

[BZOJ4379][POI2015]Modernizacja autostrady

毒瘤warning！

换根\(dp\)求出切断每条边之后两棵树内的直径。需要维护：子树内从\(u\)出发的前三长链，子树内最大次大直径（不算当前点），子树最大直径，子树外最长链与最大直径。

设两棵树的直径分别是\(A,B\)，那么连接两直径中点可得最小直径\(\max\{A,B,\lceil\frac A2\rceil+\lceil\frac B2\rceil+1\}\)，连接两直径端点可得最大直径\(A+B+1\)。

然后随便构造一下方案就好了。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 5e5+5;
int n,to[N<<1],nxt[N<<1],head[N],cnt=1,d[N][3],w[N][2],g[N],o[N],h[N],ans1=1e9,edg1,ans2,edg2,ban[N<<1],pre[N],dep[N],S,tmp[N],len;
void dfs1(int u,int f){
	for (int e=head[u],v;e;e=nxt[e])
		if ((v=to[e])!=f){
			dfs1(v,u);
			int t=d[v][0]+1;
			if (t>d[u][0]) d[u][2]=d[u][1],d[u][1]=d[u][0],d[u][0]=t;
			else if (t>d[u][1]) d[u][2]=d[u][1],d[u][1]=t;
			else if (t>d[u][2]) d[u][2]=t;
			t=g[v];g[u]=max(g[u],g[v]);
			if (t>w[u][0]) w[u][1]=w[u][0],w[u][0]=t;
			else if (t>w[u][1]) w[u][1]=t;
		}
	g[u]=max(g[u],d[u][0]+d[u][1]);
}
void dfs2(int u,int f){
	for (int e=head[u],v;e;e=nxt[e])
		if ((v=to[e])!=f){
			o[v]=max(o[u],d[v][0]+1==d[u][0]?d[u][1]:d[u][0])+1;
			h[v]=max(h[u],g[v]==w[u][0]?w[u][1]:w[u][0]);
			int a,b;
			if (d[v][0]+1==d[u][0]) a=d[u][1],b=d[u][2];
			else a=d[u][0],b=d[v][0]+1==d[u][1]?d[u][2]:d[u][1];
			h[v]=max(h[v],a+b);h[v]=max(h[v],a+o[u]);
			int t=max(max(h[v],g[v]),(h[v]+1)/2+(g[v]+1)/2+1);
			if (t<ans1) ans1=t,edg1=e;
			t=h[v]+g[v]+1;
			if (t>ans2) ans2=t,edg2=e;
			dfs2(v,u);
		}
}
void DFS(int u,int f){
	pre[u]=f;dep[u]=dep[f]+1;S=dep[u]>dep[S]?u:S;
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=f&&!ban[e]) DFS(to[e],u);
}
int main(){
	n=gi();
	for (int i=1;i<n;++i){
		int u=gi(),v=gi();
		to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
		to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
	}
	dfs1(1,0);dfs2(1,0);
	printf("%d %d %d ",ans1,to[edg1],to[edg1^1]);ban[edg1]=ban[edg1^1]=1;
	DFS(S=to[edg1],0);DFS(S,len=0);
	for (int i=S;i;i=pre[i]) tmp[++len]=i;printf("%d ",tmp[len+1>>1]);
	DFS(S=to[edg1^1],0);DFS(S,len=0);
	for (int i=S;i;i=pre[i]) tmp[++len]=i;printf("%d\n",tmp[len+1>>1]);
	printf("%d %d %d ",ans2,to[edg2],to[edg2^1]);ban[edg1]=ban[edg1^1]=0;ban[edg2]=ban[edg2^1]=1;
	DFS(S=to[edg2],0);printf("%d ",S);
	DFS(S=to[edg2^1],0);printf("%d\n",S);
	return 0;
}

[BZOJ4380][POI2015]Myjnie

设\(f_{i,j,k}\)表示区间\([i,j]\)最小费用为\(k\)的最大收益。为了方便转移记成后缀最大值的形式。

暴力枚举区间内最小值的位置以及这个最小值转移，复杂度\(O(n^3m)\)。

输出方案要多记录一些东西，比如\(g_{i,j,k}\)记录后缀最大值的真实的\(k\)的位置，\(h_{i,j,k}\)记录转移点（最小值的位置）。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 55;
const int M = 4005;
int n,m,a[M],b[M],c[M],o[M],tot[N][M],f[N][N][M],g[N][N][M],h[N][N][M],ans[N];
void add(int l,int r){
	for (int i=l;i<=r;++i)
		for (int j=1;j<=m;++j)
			tot[i][j]=0;
	for (int i=1;i<=m;++i)
		if (a[i]>=l&&b[i]<=r)
			for (int j=a[i];j<=b[i];++j)
				++tot[j][c[i]];
	for (int i=l;i<=r;++i)
		for (int j=m-1;j;--j)
			tot[i][j]+=tot[i][j+1];
}
void dfs(int l,int r,int k){
	if (l>r) return;
	k=g[l][r][k];int x=h[l][r][k];
	ans[x]=o[k];dfs(l,x-1,k);dfs(x+1,r,k);
}
int main(){
	n=gi();m=gi();
	for (int i=1;i<=m;++i) a[i]=gi(),b[i]=gi(),c[i]=o[i]=gi();
	sort(o+1,o+m+1);
	for (int i=1;i<=m;++i) c[i]=lower_bound(o+1,o+m+1,c[i])-o;
	for (int i=n;i;--i)
		for (int j=i;j<=n;++j){
			add(i,j);
			for (int k=m;k;--k){
				int res=-1;
				for (int x=i;x<=j;++x){
					int tmp=f[i][x-1][k]+f[x+1][j][k]+tot[x][k]*o[k];
					if (tmp>res) res=tmp,h[i][j][k]=x;
				}
				if (res>=f[i][j][k+1]) f[i][j][k]=res,g[i][j][k]=k;
				else f[i][j][k]=f[i][j][k+1],g[i][j][k]=g[i][j][k+1];
			}
		}
	printf("%d\n",f[1][n][1]);dfs(1,n,1);
	for (int i=1;i<=n;++i) printf("%d ",ans[i]);puts("");
	return 0;
}

[BZOJ4381][POI2015]Odwiedziny

POI居然会出\(5w\)的数据范围那就一定是根号算法了吧。

按步伐大小分块：小于等于\(\sqrt n\)的可以\(O(n\sqrt n)\)预处理每个点以\(i\)的步伐向上跳到根的权值和，大于\(\sqrt n\)的暴力跳即可。处理起来或许有点小细节。

这样复杂度是\(O(n\sqrt n)\)的。树剖跳\(k\)级祖先的复杂度看上去像是\(O(\log n)\)的，但对于一组询问重链的变换次数只有\(O(\log n)\)，所以单次的复杂度应该是\(O(\sqrt n+\log n)\)而非两者乘起来。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 50005;
const int M = 100;
int n,m,a[N],to[N<<1],nxt[N<<1],head[N],cnt,fa[N],dep[N],sz[N],top[N],dfn[N],id[N],tim,s[N],sum[N][M],b[N],c[N];
void dfs1(int u,int f){
	fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=f) dfs1(to[e],u),sz[u]+=sz[to[e]];
}
void dfs2(int u,int f){
	top[u]=f;id[dfn[u]=++tim]=u;int son=0;
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=fa[u]&&sz[to[e]]>sz[son]) son=to[e];
	if (son) dfs2(son,f);else return;
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=fa[u]&&to[e]!=son) dfs2(to[e],to[e]);
}
void dfs(int u,int f){
	s[dep[u]]=u;
	for (int i=1;i<M;++i){
		sum[u][i]=a[u];
		if (dep[u]>i) sum[u][i]+=sum[s[dep[u]-i]][i];
	}
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=f) dfs(to[e],u);
}
int father(int u,int k){
	if (k>=dep[u]) return 0;
	while (dep[u]-dep[top[u]]<k) k-=dep[u]-dep[top[u]]+1,u=fa[top[u]];
	return id[dfn[u]-k];
}
int lca(int u,int v){
	while (top[u]^top[v])
		if (dep[top[u]]>dep[top[v]]) u=fa[top[u]];
		else v=fa[top[v]];
	return dep[u]<dep[v]?u:v;
}
int jump(int x,int d,int k){
	if (k<M) return sum[x][k]-sum[father(x,(d/k+1)*k)][k];
	int res=0;
	while (d>=0) res+=a[x],d-=k,x=father(x,k);
	return res;
}
int work(int x,int y,int k){
	int z=lca(x,y),res=jump(x,dep[x]-dep[z],k);
	if ((dep[x]+dep[y]-2*dep[z])%k) res+=a[y];
	else y=father(y,(dep[x]+dep[y]-2*dep[z])%k);
	res+=jump(y,dep[y]-dep[z],k);
	if ((dep[x]-dep[z])%k==0) res-=a[z];
	return res;
}
int main(){
	n=gi();
	for (int i=1;i<=n;++i) a[i]=gi();
	for (int i=1;i<n;++i){
		int u=gi(),v=gi();
		to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
		to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
	}
	dfs1(1,0);dfs2(1,1);dfs(1,0);
	for (int i=1;i<=n;++i) b[i]=gi();
	for (int i=1;i<n;++i) c[i]=gi();
	for (int i=1;i<n;++i) printf("%d\n",work(b[i],b[i+1],c[i]));
	return 0;
}

[BZOJ4382][POI2015]Podział naszyjnika

对于两个相邻的同色块，我们可以在前一个上面打一个\(+1\)标记，在后一个上面打一个\(-1\)标记，然后就变成了选两个前缀他们的前缀和相等，相当于是这样个同色块之间不能割裂开来。

但是有若干种颜色每种颜色有若干块，标记可能会冲突，怎么办呢？我们给每对相邻同色块随机打上不同的标记就行啦。

这样第一问就是每种相同前缀数量\(sz\)的\(\sum\binom{sz}{2}\)，第二问可以把这些前缀拿出来做一个单调队列优化转移的\(dp\)状物。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define ll long long
const int N = 1e6+5;
int n,k,lst[N],id[N],ans2=N;ll p=1,sum[N],ans1;
bool cmp(int i,int j){return sum[i]==sum[j]?i<j:sum[i]<sum[j];}
int cal(int i,int j){
	int s=abs(n-(j-i<<1));
	ans2=min(ans2,s);return s;
}
int main(){
	n=gi();k=gi();
	for (int i=1;i<=n;++i){
		int a=gi();
		if (lst[a]) sum[lst[a]]+=p,sum[i]-=p,p*=20020415;
		lst[a]=i;
	}
	for (int i=1;i<=n;++i) sum[i]+=sum[i-1],id[i]=i;
	sort(id+1,id+n+1,cmp);
	for (int i=1,j=1;i<=n;i=j=j+1){
		while (j<n&&sum[id[j+1]]==sum[id[i]]) ++j;
		ans1+=1ll*(j-i)*(j-i+1)>>1;
		for (int k=i,l=i;k<=j;++k)
			while (l<k&&cal(id[l+1],id[k])<cal(id[l],id[k])) ++l;
	}
	printf("%lld %d\n",ans1,ans2);
	return 0;
}

[BZOJ4383][POI2015]Pustynia

暴力建图就是个差分约束状物。拿线段树优化连边可以做到边数\(O(\sum k\log n)\)。

注意判一下无解，包括可能某个数超过了\(10^9\)也算是无解。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 4e5+5;
int n,s,m,tot,pos[N],root,ls[N],rs[N],tmp[N],to[N*20],nxt[N*20],ww[N*20],head[N],cnt,in[N],f[N],t[N];
queue<int>Q;
void link(int u,int v,int w){
	to[++cnt]=v;nxt[cnt]=head[u];ww[cnt]=w;head[u]=cnt;++in[v];
}
void build(int &x,int l,int r){
	x=++tot;if (l==r) {pos[l]=x;return;}
	int mid=l+r>>1;
	build(ls[x],l,mid);build(rs[x],mid+1,r);
	link(ls[x],x,0);link(rs[x],x,0);
}
void modify(int x,int l,int r,int ql,int qr){
	if (l>=ql&&r<=qr) {link(x,tot,0);return;}
	int mid=l+r>>1;
	if (ql<=mid) modify(ls[x],l,mid,ql,qr);
	if (qr>mid) modify(rs[x],mid+1,r,ql,qr);
}
int main(){
	n=gi();s=gi();m=gi();
	build(root,1,n);memset(t,63,sizeof(t));
	while (s--){
		int p=gi();f[pos[p]]=t[pos[p]]=gi();
	}
	while (m--){
		int l=gi(),r=gi(),k=gi();tmp[0]=l-1,tmp[k+1]=r+1;++tot;
		for (int i=1;i<=k;++i) tmp[i]=gi(),link(tot,pos[tmp[i]],1);
		for (int i=0;i<=k;++i) if (tmp[i+1]-tmp[i]>1) modify(root,1,n,tmp[i]+1,tmp[i+1]-1);
	}
	for (int i=1;i<=tot;++i) if (!in[i]) f[i]=max(f[i],1),Q.push(i);
	while (!Q.empty()){
		int u=Q.front();Q.pop();
		for (int e=head[u];e;e=nxt[e]){
			f[to[e]]=max(f[to[e]],f[u]+ww[e]);
			if (f[to[e]]>t[to[e]]) return puts("NIE"),0;
			if (!--in[to[e]]) Q.push(to[e]);
		}
	}
	for (int i=1;i<=n;++i) if (!f[pos[i]]||f[pos[i]]>1000000000) return puts("NIE"),0;
	puts("TAK");
	for (int i=1;i<=n;++i) printf("%d ",f[pos[i]]);
	puts("");return 0;
}

[BZOJ4384][POI2015]Trzy wieże

首先只有一种字符的可以预先\(O(n)\)判掉。然后就是三种字符的出现次数均不相同。

对每个位置分别记下三种字符的前缀数量\(cnt_{i,0/1/2}\)。

问题要求的是：

\[cnt_{i,0}-cnt_{j,0}\neq cnt_{i,1}-cnt_{j,1}\\cnt_{i,0}-cnt_{j,0}\neq cnt_{i,2}-cnt_{j,2}\\cnt_{i,1}-cnt_{j,1}\neq cnt_{i,2}-cnt_{j,2}
\]

也就是

\[cnt_{i,0}-cnt_{i,1}\neq cnt_{j,0}-cnt_{j,1}\\cnt_{i,0}-cnt_{i,2}\neq cnt_{j,0}-cnt_{j,2}\\cnt_{i,1}-cnt_{i,2}\neq cnt_{j,1}-cnt_{j,2}
\]

记\(a_i=cnt_{i,0}-cnt_{i,1},b_i=cnt_{i,0}-cnt_{i,2},c_i=cnt_{i,1}-cnt_{i,2}\)，相当于是要求\(\max\{i-j|a_i\neq a_j,b_i\neq b_j,c_i\neq c_j\}\)。

按\(a_i\)排序，以\(b_i\)为下标插入树状数组，树状数组每个点上维护下标的最大最小值。因为有\(c_i\)的限制，所以要维护\(c_i\)值不同的最大次大值与最小次小值。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
int n,cnt[3],a[N],b[N],c[N],o[N],len,id[N],ans;char s[N];
bool cmp(int i,int j){return a[i]<a[j];}
struct node{
	int mx1,mx2,mn1,mn2;
	node(){mx1=mx2=0;mn1=mn2=N-1;}
	void upt(int x){
		if (x>mx1){
			if (c[x]!=c[mx1]) mx2=mx1;
			mx1=x;
		}
		else if (x>mx2&&c[x]!=c[mx1]) mx2=x;
		if (x<mn1){
			if (c[x]!=c[mn1]) mn2=mn1;
			mn1=x;
		}
		else if (x<mn2&&c[x]!=c[mn1]) mn2=x;
	}
};
struct Binary_Index_Tree{
	node t[N];
	void mdf(int k,int v){while(k<=len)t[k].upt(v),k+=k&-k;}
	int qry_mx(int k,int ban){
		int s=0;
		while (k) s=max(s,c[t[k].mx1]==ban?t[k].mx2:t[k].mx1),k^=k&-k;
		return s;
	}
	int qry_mn(int k,int ban){
		int s=n+1;
		while (k) s=min(s,c[t[k].mn1]==ban?t[k].mn2:t[k].mn1),k^=k&-k;
		return s;
	}
}T[2];
int main(){
	n=gi()+1;scanf("%s",s+2);
	for (int i=1;i<=n;++i){
		if (i>1) ++cnt[s[i]=='S'?2:s[i]-'B'];
		a[i]=cnt[1]-cnt[0];b[i]=cnt[2]-cnt[0];c[i]=cnt[2]-cnt[1];
	}
	for (int i=1;i<=n;++i) o[i]=b[i],id[i]=i;
	sort(o+1,o+n+1);len=unique(o+1,o+n+1)-o-1;
	for (int i=1;i<=n;++i) b[i]=lower_bound(o+1,o+len+1,b[i])-o;
	sort(id+1,id+n+1,cmp);
	for (int i=1,j=1;i<=n;i=j=j+1){
		while (j<n&&a[id[j+1]]==a[id[i]]) ++j;
		for (int k=i;k<=j;++k){
			int x=id[k];
			ans=max(ans,T[0].qry_mx(b[x]-1,c[x])-x);
			ans=max(ans,x-T[0].qry_mn(b[x]-1,c[x]));
			ans=max(ans,T[1].qry_mx(len-b[x],c[x])-x);
			ans=max(ans,x-T[1].qry_mn(len-b[x],c[x]));
		}
		for (int k=i;k<=j;++k){
			int x=id[k];
			T[0].mdf(b[x],x);T[1].mdf(len-b[x]+1,x);
		}
	}
	for (int i=2,j;i<=n;++i){
		if (s[i]!=s[i-1]) j=0;
		++j;ans=max(ans,j);
	}
	printf("%d\n",ans);return 0;
}

[BZOJ4385][POI2015]Wilcze doły

一定会选长度为\(d\)的区间。\(\mbox{Two-points}\)+单调队列维护即可。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define ll long long
const int N = 2e6+5;
int n,d,q[N],hd=1,tl,ans;ll p,sum[N],val[N];
int main(){
	n=gi();scanf("%lld",&p);d=gi();
	for (int i=1;i<=n;++i) sum[i]=sum[i-1]+gi(),val[i]=sum[i]-sum[max(0,i-d)];
	for (int i=1,j=1;i<=n;++i){
		while (hd<=tl&&val[q[tl]]<=val[i]) --tl;
		q[++tl]=i;
		while (sum[i]-sum[j-1]-val[q[hd]]>p){
			++j;while (q[hd]-d+1<j) ++hd;
		}
		ans=max(ans,i-j+1);
	}
	printf("%d\n",ans);
	return 0;
}

[BZOJ4386][POI2015]Wycieczki

裸的倍增矩乘。新建一个\(0\)号点表示路径的终点即可。

爆\(\mbox{long long}\)这点很烦，代码中判断如果乘出来的数超过了\(K\)就直接赋成\(-1\)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define ll long long
const int N = 125;
int n,m,sz;ll K,ans;
struct matrix{
	ll a[N][N];
	matrix(){memset(a,0,sizeof(a));}
	ll *operator [](int x){return a[x];}
	matrix operator * (matrix b){
		matrix c;
		for (int i=0;i<=sz;++i)
			for (int j=0;j<=sz;++j)
				for (int k=0;k<=sz;++k)
					if (a[i][k]&&b[k][j]){
						if (a[i][k]<0||b[k][j]<0) {c[i][j]=-1;break;}
						if (a[i][k]>K/b[k][j]) {c[i][j]=-1;break;}
						c[i][j]+=a[i][k]*b[k][j];
						if (c[i][j]<0) {c[i][j]=-1;break;}
					}
		return c;
	}
	bool check(){
		ll res=0;
		for (int i=1;i<=n;++i){
			if (a[i][0]<0) return false;
			res+=a[i][0];
			if (res>=K||res<0) return false;
		}
		return true;
	}
}T[63],Now,Tmp;
int main(){
	n=gi();m=gi();sz=3*n;scanf("%lld",&K);K+=n;T[0][0][0]=1;
	for (int i=1;i<=n;++i) Now[i][i]=T[0][i][0]=T[0][i][i+n]=T[0][i+n][i+n+n]=1;
	for (int i=1,u,v,w;i<=m;++i) u=gi(),v=gi(),w=gi()-1,++T[0][u+w*n][v];
	for (int i=1;i<63;++i) T[i]=T[i-1]*T[i-1];
	for (int i=62;~i;--i){
		Tmp=Now*T[i];
		if (Tmp.check()) ans|=1ll<<i,Now=Tmp;
	}
	if ((Now*T[0]).check()) puts("-1");
	else printf("%lld\n",ans);
	return 0;
}