难度预估：黄，蓝/紫，蓝/紫，黑。

A

注意到，一定会选择一个后缀（即 $\ge i$ 的所有位全部设为 $0$ ），并且有 $i\le \log n$ 。枚举 $\log n$ 以内的每个 $i$ 并计算答案即可。

时间复杂度 $O(n(k+\log n))$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,a[N][N];
int val[N],c[N];
void sol(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			char ch;
			cin>>ch;
			a[i][j]=ch-'0';
		}
	}
	int ans=0;
	for(int j=0;j<10;j++){
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++){
			val[i]+=(a[i][j]<<j);
			c[val[i]]++;
		}
		int res=0;
		for(int i=0;i<=n;i++){
			if(!c[i]){
				res=i;
				break;
			}
		}
		ans=max(ans,res);
	}
	cout<<ans<<"\n";
}
signed main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	while(ct--){
		sol();
	}
}

B

注意到，选择后一定是把所有解药往前放，所有毒药往后放。

考虑合法需要满足的条件。对于一个前缀 $i$ ，若其中毒药多于解药，令毒药比解药多 $w$ 瓶，那么至少需要有 $b_i=\left \lceil \frac{w}{2} \right \rceil$ 瓶毒药被换成解药才能合法。也就是说，前缀 $i$ 内必须选中 $\ge b_i$ 瓶毒药，且前缀 $i$ 外必须选中 $\ge b_i$ 瓶解药。

那我们就可以得到一个 $O(n^3)$ 的简单 dp：令 $f_{i,j,k}$ 表示前 $i$ 个位置，已选 $j$ 瓶毒药，且后面将要选 $k$ 瓶解药的答案。初始 $f_{0,0,i}=1$ ，转移如下：

不选：

f_{i,j,k}\to f_{i+1,j,k}

$i+1$ 位置是毒药，并且选，此时 $j$ 加 $1$ ， $k$ 不变：

f_{i,j,k}\to f_{i+1,j+1,k}

$i+1$ 位置是解药，并且选，此时 $j$ 不变， $k$ 减 $1$ ：

f_{i,j,k}\to f_{i+1,j,k-1}

在 $i$ 处，合法条件为 $j\ge b_i$ 且 $k\ge b_i$ ，将不合法的状态清掉。

最终答案为 $\sum\limits_i g_{n,i,0}$ 。

考虑优化状态。考虑如何将 $j,k$ 两维简化为一维。注意到 $j,k$ 只有较小的一个有用，且转移时 $j$ 只会增加， $k$ 只会减少。我们将状态拆分为 $f_{i,j}$ 和 $g_{i,k}$ 分别表示 $j<k$ 和 $j\ge k$ 时的答案。在 $j=k$ 时从 $f$ 向 $g$ 转移。由于每个方案有且仅有一个选中的位置满足 $j=k$ ，所以一定不会重复或者遗漏。初始状态 $f_{0,0}=g_{0,0}=1$ ，转移如下：

不选：

f_{i,j}\to f_{i+1,j}

g_{i,k}\to g_{i+1,k}

$i+1$ 位置是毒药，并且选，此时 $j$ 加 $1$ ， $k$ 不变：

f_{i,j}\to f_{i+1,j+1}

g_{i,k}\to g_{i+1,k}

以及转移后 $j$ 等于 $k$ 的情况：

f_{i,j}\to g_{i+1,j+1}

$i+1$ 位置是解药，并且选，此时 $j$ 不变， $k$ 减 $1$ ：

f_{i,j}\to f_{i+1,j}

g_{i,k}\to g_{i+1,k-1}

以及转移后 $j$ 等于 $k$ 的情况：

f_{i,j}\to g_{i+1,j}

在 $i$ 处，清除不合法的状态（ $j<b_i$ 或 $k<b_i$ ）。

最终答案 $g_{n,0}$ 。

时间复杂度 $O(n^2)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=6e3+5;
const int p=1e9+7;
void add(int &x,int y){
	x+=y;
	if(x>=p) x-=p;
}
int n,a[N],b[N];
int f[N][N],g[N][N];
void sol(){
	cin>>n;
	n*=2;
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		if(ch=='A') a[i]=1;
	}
	int pre=0;
	for(int i=1;i<=n;i++){
		if(a[i]==1) pre++;
		else pre--;
		if(pre<0){
			int w=((-pre)+1)/2; 
			b[i]=w;
		}
	}
	f[0][0]=1,g[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<b[i];j++){
			f[i][j]=g[i][j]=0;
		}
		for(int j=0;j<=n/2;j++){
			add(f[i+1][j],f[i][j]);
		}
		for(int k=0;k<=n/2;k++){
			add(g[i+1][k],g[i][k]);
		}
		if(a[i+1]==0){
			for(int j=0;j<=n/2;j++){
				add(f[i+1][j+1],f[i][j]);
				add(g[i+1][j+1],f[i][j]);
			}
			for(int k=0;k<=n/2;k++){
				add(g[i+1][k],g[i][k]);
			}
		} 
		else{
			for(int j=0;j<=n/2;j++){
				add(f[i+1][j],f[i][j]);
				add(g[i+1][j],f[i][j]);
			}
			for(int k=1;k<=n/2;k++){
				add(g[i+1][k-1],g[i][k]);
			}
		}
	}
	cout<<g[n][0]<<"\n";
}
signed main(){
	freopen("poison.in","r",stdin);
	freopen("poison.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	while(ct--){
		sol();
	}
}

C

考虑如何移动。发现一定要把所有 $1$ 全部移动到一个子树内或一个子树外。令其一定移动到一个子树内。对于移动到一个子树外的情况，相当于把 $0$ 全部移动到一个子树内，所以把 $a_i$ 取反再做一遍即可。

考虑全部移动到子树 $u$ 内时，一条边权为 $w$ 的边 $(x,fa_x)$ 的贡献（其中 $cnt_{0/1,x}$ 表示 $x$ 子树内 $0/1$ 的数量）：

$u$ 在 $x$ 的子树内，此时贡献为 $w\times (m-cnt_{1,x})$ 。
$u$ 为 $x$ 的严格祖先，此时贡献为 $w\times cnt_{0,x}$ 。
其他情况，贡献为 $w\times cnt_{1,x}$ 。

直接用树剖维护贡献即可，答案即为全局最小值。注意 $sz_u$ 需要等于 $1$ 的总数量 $m$ ，所以提前给 $sz_u\ne m$ 的位置增加 $inf$ 。

注意到满足第二条的 $sz_u=m$ 的 $u$ 至多只有一个。所以不需要树剖，直接用线段树即可。

时间复杂度 $O(n\log^2 n)$ 或 $O(n\log n)$ 。

代码如下，为保证可读性，这里提供卡常前的版本。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
const int inf=1e18;
struct sgt{
	#define mid (((le)+(ri))>>1)
	#define ls ((u)<<1)
	#define rs (((u)<<1)|1)
	#define lp ls,le,mid
	#define rp rs,mid+1,ri
	int s[N<<2],t[N<<2];
	void push_up(int u){
		s[u]=min(s[ls],s[rs]);
	}
	void ch(int u,int k){
		s[u]+=k;
		t[u]+=k;
	}
	void push_down(int u){
		if(t[u]){
			ch(ls,t[u]);
			ch(rs,t[u]);
			t[u]=0;
		}
	}
	void upd(int u,int le,int ri,int x,int y,int k){
		if(x<=le&&ri<=y){
			ch(u,k);
			return;
		}
		push_down(u);
		if(x<=mid) upd(lp,x,y,k);
		if(y>mid) upd(rp,x,y,k);
		push_up(u);
	}
	int que(int u,int le,int ri,int x,int y){
		if(x<=le&&ri<=y){
			return s[u];
		}
		push_down(u);
		int res=inf;
		if(x<=mid) res=min(res,que(lp,x,y));
		if(y>mid) res=min(res,que(rp,x,y));
		return res;
	}
}t;
int n,m,q,a[N];
int cnt[2][N];
int idx[N],dw[N],ans[N];
vector<int> e[N];
int p[N],val[N],tval[N],p1[N],p2[N];
int fr[N],dep[N],sz[N],hs[N];
int top[N],dfn[N],dc;
void cl(){
	t={};
	memset(cnt,0,sizeof(cnt));
}
void dfs0(int u,int fa){
	dep[u]=dep[fa]+1;
	fr[u]=fa;
	sz[u]=1;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs0(v,u);
		sz[u]+=sz[v];
		if(sz[hs[u]]<sz[v]) hs[u]=v;
	}
}
void dfs1(int u,int tt){
	top[u]=tt;
	dfn[u]=++dc;
	if(!hs[u]) return;
	dfs1(hs[u],tt);
	for(int v:e[u]){
		if(v==fr[u]||v==hs[u]) continue;
		dfs1(v,v);
	}
}
void dfs2(int u,int fa){
	cnt[a[u]][u]++;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs2(v,u);
		for(int j=0;j<=1;j++){
			cnt[j][u]+=cnt[j][v];
		}
	}
}
void opt(int x,int w){
	int wson=w*(m-cnt[1][x]);
	int wfa=w*(cnt[0][x]);
	int welse=w*(cnt[1][x]);
	t.upd(1,1,n,1,n,welse);
	t.upd(1,1,n,dfn[x],dfn[x]+sz[x]-1,wson-welse);
	x=fr[x];
	while(x){
		t.upd(1,1,n,dfn[top[x]],dfn[x],wfa-welse);
		x=fr[top[x]];
	}
}
void calc(){
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		if(sz[i]!=m){
			t.upd(1,1,n,dfn[i],dfn[i],inf);
		}
	}
	for(int i=1;i<n;i++){
		opt(p[i],val[i]);
	}
	for(int i=1;i<=q;i++){
		opt(p[idx[i]],dw[i]);
		ans[i]=min(ans[i],t.que(1,1,n,1,n));
	}
	cl();
}
signed main(){
	freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		a[i]=ch-'0';
		if(a[i]==1) m++;
	}
	for(int i=1;i<n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		e[x].push_back(y);
		e[y].push_back(x);
		p1[i]=x;
		p2[i]=y;
		val[i]=w;
	}
	dfs0(1,0);
	dfs1(1,1);
	for(int i=1;i<n;i++){
		p[i]=((fr[p1[i]]==p2[i])?(p1[i]):(p2[i]));
	}
	memcpy(tval,val,sizeof(val));
	for(int i=1;i<=q;i++){
		int x,k;
		cin>>x>>k;
		idx[i]=x;
		dw[i]=k-tval[x];
		tval[x]=k;
	}
	memset(ans,0x3f,sizeof(ans));
	calc();
	m=n-m;
	for(int i=1;i<=n;i++){
		a[i]^=1;
	}
	calc();
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<"\n";
	}
}

D

考虑一个 $01$ 序列，使其合法的最小修改次数。

若 $k=1$ ，发现合法的序列只有两种，计算这两种序列的修改次数即可。

若 $k>1$ ，修改次数为，每个相同颜色连续段的长度除以 $k+1$ 向下取整的和。

两种情况分别讨论。考虑均使用点分治。

$k=1$ 时是简单的。

若 $k>1$ ，一条路径需要记录每个路径到根的开头连续段（长度模 $k+1$ 的值），以及最小修改次数。对于一条最小修改次数为 $x$ 且开头连续段长度为 $y$ 的线段。查询修改次数 $<m-x$ ，或修改次数等于 $m-x$ 且开头连续段异色，或修改次数等于 $m-x$ ，开头连续段同色且其长度 $\le k-y$ 的最大值。使用动态开点线段树分别处理即可。

时间复杂度 $O(n\log^2 n)$ 。

代码如下，为保证可读性，这里提供卡常前的版本。

#include<bits/stdc++.h>
#define mid (((le)+(ri))>>1)
using namespace std;
const int N=1e5+5;
int mx[N*340],ls[N*340],rs[N*340],tot;
void push_up(int u){
	mx[u]=max(mx[ls[u]],mx[rs[u]]);
}
void upd(int &u,int le,int ri,int x,int k){
	if(!u) u=++tot;
	if(le==ri){
		mx[u]=max(mx[u],k);
		return;
	}
	if(x<=mid) upd(ls[u],le,mid,x,k);
	else upd(rs[u],mid+1,ri,x,k);
	push_up(u);
}
int que(int u,int le,int ri,int x,int y){
	if(x>y) return 0;
	if(!u) return 0;
	if(x<=le&&ri<=y){
		return mx[u];
	}
	int res=0;
	if(x<=mid) res=max(res,que(ls[u],le,mid,x,y));
	if(y>mid) res=max(res,que(rs[u],mid+1,ri,x,y));
	return res;
}
int n,m,k;
vector<pair<int,int>> e[N];
void cl(){
	fill(e,e+N,vector<pair<int,int>>());
	n=m=k=0;
}
namespace sol1{
	int ans;
	int vis[N],sz[N];
	void cl(){
		memset(vis,0,sizeof(vis));
		memset(sz,0,sizeof(sz));
		ans=0;
	}
	void get_sz(int u,int fa){
		sz[u]=1;
		for(auto [v,w]:e[u]){
			if(v==fa||vis[v]) continue;
			get_sz(v,u);
			sz[u]+=sz[v];
		}
	}
	void get_rt(int u,int fa,int &rt,int tot){
		int ok=1;
		for(auto [v,w]:e[u]){
			if(v==fa||vis[v]) continue;
			get_rt(v,u,rt,tot);
			if(sz[v]>tot/2) ok=0;
		}
		if(tot-sz[u]>tot/2) ok=0;
		if(ok) rt=u;
	}
	void append(int u,int fa,int dep,int val,int o,vector<pair<int,int>> &res){
		res.push_back({dep,val});
		for(auto [v,w]:e[u]){
			if(v==fa||vis[v]) continue;
			int z=(((dep&1)^w^o)?(1):(0));
			append(v,u,dep+1,val+z,o,res);
		}
	}
	void dfs(int u){
		get_sz(u,0);
		int rt=0;
		get_rt(u,0,rt,sz[u]);
		u=rt;
		int sgt[2]{};
		auto opt=[&](int v,int w){
			vector<pair<int,int>> res[2];
			for(int j=0;j<=1;j++){
				append(v,u,1,w^j,j,res[j]);
			}
			for(int j=0;j<=1;j++){
				for(auto [dep,val]:res[j]){
					if(val<=m){
						int w=que(sgt[j^1],0,n,0,m-val);
						ans=max(ans,w+dep);
					}
				}
			}
			for(int j=0;j<=1;j++){
				for(auto [dep,val]:res[j]){
					upd(sgt[j],0,n,val,dep);
				}
			}
		};
		for(int i=0;i<(int)e[u].size();i++){
			auto [v,w]=e[u][i];
			if(vis[v]) continue;
			opt(v,w);
		}
		vis[u]=1;
		for(auto [v,w]:e[u]){
			if(vis[v]) continue;
			dfs(v);
		}
	}
	void solve(){
		dfs(1);
		cout<<ans<<"\n";
		cl();
	}
};
namespace sol2{
	int ans;
	int vis[N],sz[N];
	void cl(){
		memset(vis,0,sizeof(vis));
		memset(sz,0,sizeof(sz));
		ans=0;
	}
	void get_sz(int u,int fa){
		sz[u]=1;
		for(auto [v,w]:e[u]){
			if(v==fa||vis[v]) continue;
			get_sz(v,u);
			sz[u]+=sz[v];
		}
	}
	void get_rt(int u,int fa,int &rt,int tot){
		int ok=1;
		for(auto [v,w]:e[u]){
			if(v==fa||vis[v]) continue;
			get_rt(v,u,rt,tot);
			if(sz[v]>tot/2) ok=0;
		}
		if(tot-sz[u]>tot/2) ok=0;
		if(ok) rt=u;
	}
	void append(int u,int fa,int dep,int val,int tcol,int tlen,int fl,int col,int len,vector<array<int,4>> &res){
		res.push_back({dep,val,tcol,tlen});
		for(auto [v,w]:e[u]){
			if(v==fa||vis[v]) continue;
			if(w==col){
				if(fl){
					if(len==k){
						append(v,u,dep+1,val+1,tcol,0,fl,col,0,res);
					}
					else{
						append(v,u,dep+1,val,tcol,tlen+1,fl,col,len+1,res);
					}
				}
				else{
					if(len==k){
						append(v,u,dep+1,val+1,tcol,tlen,fl,col,0,res);
					}
					else{
						append(v,u,dep+1,val,tcol,tlen,fl,col,len+1,res);
					}
				}
			}
			else{
				append(v,u,dep+1,val,tcol,tlen,0,w,1,res);
			}
		}
	}
	void dfs(int u){
		get_sz(u,0);
		int rt=0;
		get_rt(u,0,rt,sz[u]);
		u=rt;
		int s1=0;
		map<int,int> s2[2];
		auto opt=[&](int v,int w){
			vector<array<int,4>> res;
			append(v,u,1,0,w,1,1,w,1,res);
			for(auto [dep,val,tcol,tlen]:res){
				if(val<m){
					int w=que(s1,0,n,0,m-val-1);
					ans=max(ans,w+dep);
				}
				if(val<=m){
					int w=que(s2[tcol^1][m-val],0,n,0,n);
					ans=max(ans,w+dep);
				}
				if(val<=m&&tlen<=k){
					int w=que(s2[tcol][m-val],0,n,0,k-tlen);
					ans=max(ans,w+dep);
				}
			}
			for(auto [dep,val,tcol,tlen]:res){
				upd(s1,0,n,val,dep);
				upd(s2[tcol][val],0,n,tlen,dep);
			}
		};
		for(int i=0;i<(int)e[u].size();i++){
			auto [v,w]=e[u][i];
			if(vis[v]) continue;
			opt(v,w);
		}
		vis[u]=1;
		for(auto [v,w]:e[u]){
			if(vis[v]) continue;
			dfs(v);
		}
	}
	void solve(){
		dfs(1);
		cout<<ans<<"\n";
		cl();
	}
};
void sol(){
	cin>>n>>m>>k;
	for(int i=1;i<n;i++){
		int x,y,w;
		char ch;
		cin>>x>>y>>ch;
		if(ch=='A') w=0;
		else w=1;
		e[x].push_back({y,w});
		e[y].push_back({x,w});
	}
	if(k==1) sol1::solve();
	else sol2::solve();
	cl();
}
signed main(){
	freopen("war.in","r",stdin);
	freopen("war.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
	cin>>ct;
	while(ct--){
		sol();
	}
}

No comments so far...

做题记录（题解）

A

B

C

D

0 comments

Status

Development

Support

About