专栏文章

P13537 题解

llmh_qwq
P13537题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mioknaag
此快照首次捕获于
2025/12/02 20:45
3 个月前
此快照最后确认于
2025/12/02 20:45
3 个月前
查看原文
不难发现一个图有解当且仅当它联通。
一个朴素的想法是，把最终的结果按照列分割成若干块，每块宽 33 格，两边全部放同一种颜色 xx，中间放与 xx 相邻的颜色。
当然为了确保相邻块的 xx 之间有连边，需要找一棵生成树并在必要的时候回溯。为了方便实现，使用 dfs 生成树。
这个做法可以做到 4n4n。
现在我们保留生成树，递归地构造答案。如果生成树上一个点 xx 有多个儿子，那么是说，这个点是子树中所有点导出子图的一个割点，删掉之后导出子图变成多个联通块。
用 xx 将它的不同子树分隔开来，有如下构造：
CPP
xxxxxxxxx
x1x2x3x4x
xxxxxxxxx
x...x...x
x...x...x
x...x...x
x...x...x
其中两个 . 的连通块代表 xx 的不同子树，数字代表子树中与 xx 有边相连的点。
显然这个构造可以做到宽度 2n−12n-1，长度 3n3n，尝试进一步优化。
为了保证构造中 1234 的位置不和其他东西相邻，需要把与它直接相邻的位置填上 x，因而可以挖掉角上的位置得到
CPP
_x_x_x_x_
x1x2x3x4x
xx.xxx.xx
x...x...x
x...x...x
x...x...x
x...x...x
或者
CPP
x_x_x_x_x
xx1x2x3xx
x.x.x.x.x
x...x...x
x...x...x
x...x...x
x...x...x
其中 _ 为上一层用掉的部分。
相邻层之间交错排列，这样就可以做到 2n+12n+1。发现最外面一层的数字上面不需要放东西，可以再省掉一层，做到 2n2n。
显然如果一个子树大小为 s>1s>1，那么按照这种构造，上面一层至少会留下 s−2s-2 个位置可以用来填数。子树内至多有 s−1s-1 个与 xx 相邻的点，其中又有至少一个是它的儿子，因此 s−2s-2 个是够用的。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=250;
int n,m,k,ans[N][N],ok[N],vis[N],TO[N][N];
vector<int> to[N];
void dfs(int u){
	vis[u]=1;
	for (auto v:to[u]) if (ok[v]&&vis[v]==0) dfs(v);
}
void del(vector<int>& vec,int x){
	if (vec.size()==0) return;
	for (int i=0;i<vec.size();++i) if (vec[i]==x){
		swap(vec[i],vec.back());break;
	}
	if (vec.back()==x) vec.pop_back();
}
void solve(vector<int> vec,int l,int r,int h){
	assert(vec.size());assert(r-l==(vec.size()-1)*2);
	int u=vec[0];
	if (vec.size()==1){
		for (int i=1;i<=h;++i) for (int j=l;j<=r;++j) ans[i][j]=u;
		for (int i=l;i<=r;++i) if (ans[h+1][i]==0) ans[h+1][i]=u;
		return;
	}
	for (auto x:vec) ok[x]=1;
	dfs(u);
	for (auto x:vec) assert(vis[x]);
	for (auto x:vec) vis[x]=0;
	for (int i=1;i<=h;++i) ans[i][l]=ans[i][r]=u;
	for (int i=l;i<=r;++i) ans[h][i]=u;
	if (ans[h+1][l]==0) ans[h+1][l]=u;
	if (ans[h+1][r]==0) ans[h+1][r]=u;
	int d=l+1+(ans[h+1][l+1]!=0);
	for (auto x:to[u]) if (ok[x]){
		assert(d<r);
		assert(ans[h+1][d]==0);
		ans[h+1][d]=ans[h-1][d]=u;
		ans[h][d]=x;
		d+=2;
	}
	while(d<r){
		assert(ans[h+1][d]==0);
		ans[h+1][d]=ans[h][d]=ans[h-1][d]=u;
		d+=2;
	}
	d=l;
	for (int i=1;i<=n;++i) ok[i]=0;
	del(vec,u);
	while(vec.size()){
		int v=0;
		for (auto x:vec) if (TO[u][x]){v=x;break;}
		assert(v);
		vector<int> nxt(1,v);
		for (auto x:vec) ok[x]=1;
		dfs(v);
		for (auto x:vec) if (vis[x]&&x!=v) nxt.emplace_back(x);
		for (auto x:nxt) del(vec,x);
		solve(nxt,d+1,d+2*nxt.size()-1,h-2);
		d+=2*nxt.size();
		for (int i=1;i<=h;++i) ans[i][d]=u;
		for (int i=1;i<=n;++i) ok[i]=vis[i]=0;
	}
	assert(d==r);
}
vector<vector<int> > create_map(int N,int M,vector<int> A,vector<int> B){
	memset(ans,0,sizeof(ans));
	n=N;m=M;
	for (int i=0;i<m;++i){
		to[A[i]].emplace_back(B[i]);
		to[B[i]].emplace_back(A[i]);
		TO[A[i]][B[i]]=TO[B[i]][A[i]]=1;
	}
	m=0;k=2*n;
	vector<int> vec;
	for (int i=1;i<=n;++i) vec.emplace_back(i);
	solve(vec,1,k-1,k);
	vec.clear();
	for (int i=1;i<=n;++i) to[i].clear();
	for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) TO[i][j]=0;
	for (int i=1;i<=k;++i) ans[i][k]=ans[i][k-1];
	vector<vector<int> > ans(k,vector<int>(k,0));
	for (int i=1;i<=k;++i) for (int j=1;j<=k;++j) ans[i-1][j-1]=::ans[i][j];
	return ans;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...