P9731 [CEOI2023] Balance
题意
给你一个 \(n\times s\) 的矩阵，满足 \(s\) 是 \(2\) 的幂。每个位置有一个颜色 \(a_{i,j} \in [1,t]\)。你可以交换任意行任意两个数若干次，使得每一种颜色出现在任意两列列的数量差不超过 \(1\)。构造出交换后的矩阵。
solution
首先可以把交换操作变成可以任意排序每一行。
本题是一个分治的思想我也不知道如何想到这个思想，大概部分分有提示。
考虑 \(s=2\) 的情况应该怎么做。直接做不是很好做，考虑转成图论来做。对于某一行 \((a_{i,1},a_{i,2})\)，我们连无向边 \((a_{i,1},a_{i,2})\)。交换操作可以看成给所有边定向。起点放在第一列，终点放在第二列。要求每种颜色在两列的出现次数的差不超过 \(1\)，可以转化为要求设计一种定向方式，使得每个点的入度和出度的差不超过 \(1\)。对于度数是偶数的点，显然入度和出度一定是度数的一半。对于度数是奇数的点，一个非常巧妙的方法是，建一个超级源点，和每一个度数为奇数的点连上一条边。因此要求转化成钦定一种定向方式，使得除了超级源点之外的所有点的入度等于出度。
如果你足够聪明，你会觉得这个很像欧拉回路。（由于不可能存在只有一个点的度数为奇数的情况，因此超级源点的度数也是偶数）欧拉回路可以满足所有点入度等于出度（包括超级源点）。其实我没有学过欧拉回路，假装我会了欧拉回路，那么直接跑一遍欧拉回路，给边定向，然后每条边起点放第一列，终点放第二列即可。
扩展到 \(s=2\) 的幂的情况，其实 \(2\) 的幂也许可以提示我们分治。
由上面的欧拉回路做法可以发现，我们随便搞一个图，连上超级源点后总是能跑出合法回路的，也就是说随便涂颜色都可以构造出合法方案。
于是正解来了。我们把矩阵分成两部分，\(1 \sim \frac{s}{2},\frac{s}{2}+1 \sim s\)，然后把它们看做左右两部，类似与两列的情况连边跑欧拉回路，构造出满足所有颜色在左部的数量和在右部的数量之差 \(\le 1\)。连边就每一行之间随便连，满足一个左部的点连着一个右部的点就行了，因为你目前只需要关心这个点被构造到左部还是右部，并不关心它实际上在哪一列，这个是细分后才需要关心的事情。然后我们再分治左右。
这样做是正确的。因为你每一次都一定能构造出满足左右数量差 \(\le 1\) 的方案。类似于线段树每一层节点长度差不超过 \(1\)，因此最后你构造出的方案也满足每一列数量差不超过 \(1\)。
时间复杂度：分治 \(\log s\) 次，每次 \(ns\) 的时间连边以及跑欧拉回路构造方案，一共 \(O(ns \log s)\)。
首先我需要学习一下欧拉回路怎么跑，明天学
code
upd 2024.10.28 今天改的……拖延症确诊了。
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
void read(T &x) {
x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) ;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
template <typename T>
void write(T x,char ch) {
static int st[20];
int top=0;
do {
st[top++]=x%10;
x/=10;
}while(x);
while(top) putchar(st[--top]+'0');
putchar(ch);
}
const int N=5e5+7;
int n,s,T;
int a[N];
struct edge {
int to,ne;
}e[N<<1];
int vi[N<<1];
int head[N],cnt;
int du[N];
int f(int i,int j) { return i*s+j; }
void addedge(int u,int v) { e[++cnt]={v,head[u]}; head[u]=cnt; }
void _addedge(int u,int v) { du[u]++,du[v]++; addedge(u,v),addedge(v,u); }
void init(int l,int r) {
memset(vi,0,sizeof(int)*(cnt+3));
cnt=1;
head[0]=0,du[0]=0;
rep(i,l,r) rep(j,0,n-1) head[a[f(j,i)]]=0,du[a[f(j,i)]]=0;
int mid=(l+r)>>1;
rep(i,l,mid) rep(j,0,n-1) _addedge(a[f(j,i)],a[f(j,i+mid-l+1)]);
rep(i,l,r) rep(j,0,n-1) if(du[a[f(j,i)]]&1) _addedge(0,a[f(j,i)]);
}
void dfs(int u) {
for(int &i=head[u];i;) {
if(vi[i]) { i=e[i].ne; continue; }
int v=e[i].to;
vi[i]=1;vi[i^1]=2;
i=e[i].ne;dfs(v);
}
}
void work(int l,int r) {
int c=1;
int mid=(l+r)>>1;
rep(i,l,mid) rep(j,0,n-1) { ++c; if(vi[++c]==1) swap(a[f(j,i)],a[f(j,i+mid-l+1)]); }
}
void oula(int l,int r) {
init(l,r);
dfs(0);
rep(i,l,r) rep(j,0,n-1) dfs(a[f(j,i)]);
work(l,r);
}
void solve(int l,int r) {
if(l==r) return;
oula(l,r);
int mid=(l+r)>>1;
solve(l,mid),solve(mid+1,r);
}
int main() {
#ifdef LOCAL
// freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
read(n),read(s),read(T);
rep(i,0,n*s-1) read(a[i]);
solve(0,s-1);
rep(i,0,n-1) { rep(j,0,s-1) write(a[f(i,j)],' '); putchar('\n'); }
}