P9731 [CEOI2023] Balance 题解

首先考虑 \(S=2\) 怎么做，我们把它转化为图论问题。对于每一行的两个点的颜色连一条无向边，那我们相当于要给这些边定向。最后要求 \(|in_u-out_u| \le 1\)。会发现这个要求很像欧拉回路。

但是欧拉回路是要求每个点的入度和出度相等，怎么办呢？我们再建一个超级源点，向每个奇数度数的点连边。这样跑一遍欧拉回路，最后忽略和超级源点相连的边即可。

问题变为了 \(S > 2\) 怎么做。因为题目说 \(S\) 是 \(2\) 的次幂，这让我们想到分治。每一次只需要要求每种颜色在左一半的出现次数和在右一半的出现次数差不超过 \(1\)。但是题目要求我们只能在行内交换，所以假设我们现在分治到 \([l,r]\)，我们就连边 \((a_{i,j},a_{i,mid+1+j-l})\)。会发现这样一定有解。

时间复杂度 \(O(nS \log S)\)。

//dzzfjldyqqwsxdhrdhcyxll
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e6 + 10;
int n,s,t,head[MAXN],cnt,vis[MAXN << 1],ans[MAXN << 1],tot,d[MAXN << 1];
struct Node {int u,v,nxt;}e[MAXN << 1];
inline void Add(int u,int v) {
//	cout << "u = " << u << " v = " << v << endl; 
	e[cnt] = {u,v,head[u]};
	head[u] = cnt++;
}
vector <int> a[MAXN];
inline int Get(int i,int j) {
	return max(t,n * s) + (i - 1) * s + j; 
}
inline void dfs(int u) {
	for(int &i = head[u]; ~ i;i = e[i].nxt) {
		if(vis[i]) continue;
		int now = e[i].v;
		vis[i] = vis[i ^ 1] = 1;
		dfs(now);
		if(i==-1){
			break;
		}
	}
	ans[++tot] = u;
//	cout << u << " ";
}
inline void solve(int l,int r) {
	int mid = (l + r) >> 1;
	for(int i = 1;i <= n;i++) {
		for(int j = l;j <= mid;j++) {
			if(a[i][j] == a[i][mid + 1 + j - l]) continue;
			Add(a[i][j],Get(i,j));
			Add(Get(i,j),a[i][j]);
			Add(Get(i,j),a[i][mid + 1 + j - l]);
			Add(a[i][mid + 1 + j - l],Get(i,j));
			d[a[i][j]]++;
			d[a[i][mid + 1 + j - l]]++;
		}
	}
	if(l == 3 && r == 4) {
//		cout << "dddd = " << d[3] << endl;
	}
	for(int i = 1;i <= n;i++) {
		for(int j = l;j <= r;j++) {
			if(d[a[i][j]] % 2 == 1) {
				d[a[i][j]]++;
				Add(0,a[i][j]);
				Add(a[i][j],0);
			}
		}
	}
	tot = 0;
//	dfs(0);
	for(int i = 1;i <= n;i++) {
		for(int j = l;j <= r;j++) {
//			cout << endl << endl << endl;
			dfs(a[i][j]);
		}
	}
	for(int i = 1;i <= tot;i++) {
		if(l == 3 && r == 4) {
//			cout << "ans = " << ans[i] << endl;
		}
		if(ans[i] > max(t,n * s)) {
			int val = ans[i] - max(t,n * s);
			int x = (val - 1) / s + 1;
			int y = (val % s == 0 ? s : val % s);
			if(ans[i - 1] == a[x][y]);
			else swap(a[x][y],a[x][mid + 1 + y - l]);
		}
	}
	d[0] = 0;
	head[0] = -1;
	for(int i = 1;i <= n;i++) {
		for(int j = l;j <= r;j++) {
			d[a[i][j]] = 0;
			head[a[i][j]] = -1;
			d[Get(i,j)] = 0;
			head[Get(i,j)] = -1;
		}
	}
	for(int i = 0;i < cnt;i++) {
		vis[i] = 0;
		d[e[i].u] = 0;
		d[e[i].v] = 0;
		head[e[i].u] = -1;
		head[e[i].v] = -1;
	}
//	memset(d,0,sizeof d);
//	memset(vis,0,sizeof vis);
//	memset(head,-1,sizeof head);
	cnt = 0;
//	cout << "l = " << l << " r = " << r << endl;
//	for(int i = 1;i <= n;i++,puts(""))
//		for(int j = 1;j <= s;j++) cout << a[i][j] << " ";
	if(r - l == 1) return; 
	solve(l,mid),solve(mid + 1,r);
	return; 
} 
signed main() { 
//	freopen("P9731_23.in","r",stdin);
	memset(head,-1,sizeof head);
	cin >> n >> s >> t;
	for(int i = 1;i <= n;i++) {
		a[i].resize(s + 5); 
	}
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= s;j++) {
			cin >> a[i][j];
		}
	}
	solve(1,s);
	for(int i = 1;i <= n;i++,puts("")) {
		for(int j = 1;j <= s;j++) {
			cout << a[i][j] << " ";
		}
	}	
	return 0;
}
/*
3 8 5
2 3 5 1 5 5 4 4
3 5 1 1 2 3 2 2
1 3 3 2 2 5 3 4
3 2 5
4 1 
3 5
2 3
*/