1. CEOI2023 - Balance
考虑 \(S=2\)。令 \((a_{i,j},j+T)\) 连一条无向边，若 \(a_{i,j}\) 度数为奇数则连 \((a_{i,j},S+T+1)\)，在这张图上跑出一个欧拉回路，则对边进行定向后每个题目入度与出度相同，去掉点 \(S+T+1\) 后入度与出度差 \(1\)，刚好符合题目要求。于是若欧拉回路中 \(j+T\to a_{i,j}\) 则令其放到左边一列，否则放到右边一列。
对于 \(S=2^k\) 的情况，相同处理后可以递归下去。
点击查看代码
// Problem: P9731 [CEOI2023] Balance
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9731
// Memory Limit: 1 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10, M = 2e6 + 10;
int n, m, t;
vector<int> a[N];
int ind[N], cnt, id[N], cb[N];
int hd[N], fr[M], to[M], nx[M], tot = 1;
int vis[N], ban[M];
int cl[N], cr[N];
vector<int> st;
void add(int x, int y){
fr[++tot] = x;
to[tot] = y;
nx[tot] = hd[x];
hd[x] = tot;
}
void dfs(int x){
vis[x] = 1;
for(int &i = hd[x]; i; i = nx[i]){
int y = to[i];
if(ban[i]){
continue;
}
int eg = i;
ban[i] = ban[i^1] = 1;
dfs(y);
st.push_back(eg);
}
}
void solve(int l, int r){
if(l == r){
return;
}
int mid = l + r >> 1;
for(int i = 1; i <= n; ++ i){
for(int j = l; j <= r; ++ j){
if(!ind[a[i][j]]){
id[a[i][j]] = ++ cnt;
cb[cnt] = a[i][j];
}
++ ind[a[i][j]];
}
}
for(int i = 1; i <= n; ++ i){
for(int j = l; j <= r; ++ j){
add(id[a[i][j]], i+cnt);
add(i+cnt, id[a[i][j]]);
}
}
for(int i = 1; i <= cnt; ++ i){
if(ind[cb[i]] & 1){
add(i, n+cnt+1);
add(n+cnt+1, i);
}
}
for(int i = 1; i <= cnt + n + 1; ++ i){
if(!vis[i]){
dfs(i);
}
}
reverse(st.begin(), st.end());
for(int i = 1; i <= n; ++ i){
cl[i] = l, cr[i] = r;
}
for(auto i : st){
int x = fr[i], y = to[i];
if(x <= cnt && y <= n + cnt){
a[y-cnt][cl[y-cnt]++] = cb[x];
}
if(x <= n + cnt && y <= cnt){
a[x-cnt][cr[x-cnt]--] = cb[y];
}
}
vector<int> ().swap(st);
for(int i = 1; i <= cnt; ++ i){
ind[cb[i]] = id[cb[i]] = 0;
cb[i] = 0;
}
for(int i = 1; i <= cnt + n + 1; ++ i){
vis[i] = hd[i] = 0;
}
for(int i = 1; i <= tot; ++ i){
ban[i] = 0;
}
cnt = 0;
tot = 1;
solve(l, mid);
solve(mid+1, r);
}
int main(){
int T = 1;
while(T--){
scanf("%d%d%d", &n, &m, &t);
for(int i = 1; i <= n; ++ i){
a[i].resize(m+5);
for(int j = 1; j <= m; ++ j){
scanf("%d", &a[i][j]);
}
}
solve(1, m);
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){
printf("%d ", a[i][j]);
}
puts("");
}
}
return 0;
}