CF1481F

本题解仅为一种线性空间做法的介绍。其他部分不再赘述。

其实就是一个小技巧：线性空间记录 bool 背包每个大小的转移是放入了什么物品。关键在于，注意到对于每个背包大小

x

，我们只需要在 $dp_{i,x}$ 第一次为 $1$ 时记录这次转移中放入了什么就行。

这样构造的正确性也相当显然。设上述大小为

x

的背包，放入的物品为

f_i

。假设

dp_{i,x}

是从

dp_{i-1,y}

转移过来，那么在更新

f_x

，

f_y

一定有值，并且以后不再修改。同时

f_x

显然比

f_y

更晚放入背包，所以构造时依次取出的物品不会重复，方案合法。

其实主要还是自己想想才好理解。

然后这个东西也厉害在它可能兼容 bitset 优化 bool 背包。具体地，你只需要将

dp_i

和

dp_{i-1}

的 bitset 异或一下就能得到在

dp_{i,x}

第一次为

1

的

x

，然后记录

f_x

。由于这样的

x

总共不超过

siz

个，所以配合 _Find_next 相关操作，这一部分总复杂度为

O(siz)

，大部分情况下可以接受。

code：

CPP

int n,m,dep[N];
pii frm[N];
bool dp[N],ans[N];
vector<int> f[N],g[N],h[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	if(head[u]){
		g[dep[u]].eb(u);
	}else{
		h[dep[u]].eb(u);
	}
	go(i,u){
		int v=e[i].to;
		dfs(v,u);
	}
}
void Yorushika(){
	read(n,m);
	rep(i,2,n){
		int u;read(u);
		add(u,i);
	}
	dfs(1,0);
	rep(i,1,n){
		f[g[i].size()+h[i].size()].eb(i);
	}
	dp[0]=1;
	rep(i,1,n){
		if(f[i].size()){
			int t=f[i].size();
			for(int j=1;j<=t;t-=j,j<<=1){
				drep(k,n,j*i){
					dp[k]|=dp[k-j*i];
				}
				rep(k,1,n){
					if(!frm[k].fi&&dp[k]){
						frm[k]=Mp(i,j);
					}
				}
			}
			if(t){
				drep(k,n,t*i){
					dp[k]|=dp[k-t*i];
				}
				rep(k,1,n){
					if(!frm[k].fi&&dp[k]){
						frm[k]=Mp(i,t);
					}
				}
			}
		}
	}
	int mx=0;
	rep(i,1,n){
		mx=max(mx,dep[i]);
	}
	if(dp[m]){
		printf("%d\n",mx);
		int u=m;
		while(u){
			auto [x,y]=frm[u];
			rep(_,1,y){
				if(!f[x].size()){
					break;
				}
				ans[f[x].back()]=1;
				f[x].pop_back();
			}
			u-=x*y;
		}
		rep(i,1,n){
			pc('a'+!ans[dep[i]]);
		}
	}else{
		printf("%d\n",mx+1);
		bool fl=0;
		int x=m,y=n-x;
		rep(i,1,n){
			if(g[i].size()>x){
				swap(x,y),fl^=1;
			}
			for(int j:g[i]){
				ans[j]=fl;
				x--;
			}
			for(int j:h[i]){
				if(!x){
					swap(x,y),fl^=1;
				}
				ans[j]=fl;
				x--;
			}
		}
		rep(i,1,n){
			pc('a'+ans[i]);
		}
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

文章操作

相关推荐

评论

CF1481F