CEOI2023D1T3(LOJ4019) Brought Down the Grading Server? (分治+欧拉回路)

作者：XiaoQuQu，发表于 Thu Feb 22 2024。

因为我们有 $S=2^k$，所以我们先考虑 $k=1$ 即 $S=2$ 的时候应该怎么做。

发现如果我们对于每一个核心从 $t_1$ 向 $t_2$ 连一条无向边，如果我们把 「不交换 $t_1,t_2$」 看成将这条边定向为 $t_1\to t_2$，否则如果「交换 $t_1,t_2$」看成将这条边定向为 $t_2\to t_1$，我们会发现对于一个数 $x$ 在左边出现的次数相当于 $x$ 的出度，$x$ 在右边出现的次数相当于 $x$ 的入度，我们要找到一种定向方法使得这个图上每个点的入度和出度相差不超过 $1$。

于是我们想到了欧拉回路，欧拉回路上每个点的出度和入度相等（因为每个点出去一次进来一次），但问题是我们的这个无向图不一定有欧拉回路，且我们只需要入度和出度相差不超过 $1$。

考虑到一个无向图有欧拉回路当且仅当这个图上的每一个点的度数都为偶数，于是我们想到建立一个源点，从这个源点向每个度数为奇数的点连一条边，然后在这个新的图上跑欧拉回路，最后只用关注那些原先就在这个图上的边，这样就可以保证每个点的出度和入度相差不超过 $1$ 了。

接下来考虑 $S>2$ 应该怎么做，由于 $S=2^k$，我们可以先将前 $2^{k-1}$ 个评测看成一个整体，将后 $2^{k-1}$ 个评测看成一个整体，我们要使得对于任意一个数 $x$，其在前 $2^{k-1}$ 个中出现的次数与其在后 $2^{k-1}$ 个评测中出现的次数相等，于是我们发现只需要将 $t_i$ 与 $t_{n-i}$ 连边，然后跑一遍欧拉回路，然后分治地处理 $[1,2^{k-1}]$ 与 $[2^{k-1}+1,2^{k}]$ 即可。

因为我们可能会建重边，所以可以在每条边中插入一个点，以记录重边的编号（当然可能不记录也是对的，但是我没验证过）。

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

const int MAXN = 5e6 + 5;
int ecnt, n, s, t, d[MAXN], hd[MAXN], st[MAXN], top;
vector<vector<int>> a;
struct _node {
	int v, ex, rev;
};
vector<_node> G[MAXN];
bool vis[MAXN];
struct _edge {
	int u, v, i, j;
	bool operator < (const _edge b) const {
		return u == b.u ? v < b.v : u < b.u;
	}
};

void Hierholzer(int x) {
	vis[x] = true;
	for (int &i = hd[x]; i < (int)G[x].size();) {
		if (G[x][i].ex) {
			G[x][i].ex = G[G[x][i].v][G[x][i].rev].ex = 0;
			i++;
			Hierholzer(G[x][i - 1].v);
		} else ++i;
	}
	st[++top] = x;
}

void add(int x, int y) {
	G[x].push_back({y, 1, G[y].size()});
	G[y].push_back({x, 1, G[x].size() - 1});
}

void solve(int l, int r) {
	int len = (r - l + 1);
	ecnt = top = 0;	
	int x = t;
	unordered_map<int, pair<int, int>> emap;
	for (int i = 0; i < len / 2; ++i) {
		for (int j = 1; j <= n; ++j) {
			const int u = a[j][l + i], v = a[j][r - i];
			if (u == v) continue;
			add(u, ++x); add(v, x);
			emap[x] = make_pair(i, j);
			d[u]++; d[v]++; d[x] += 2;
		}
	}
	for (int i = 1; i <= t; ++i) {
		if (d[i] % 2 == 1) {
			add(0, ++x);
			add(i, x);
		}
	}
	for (int i = 0; i <= t; ++i) {
		if (vis[i]) continue;
		top = 0;
		Hierholzer(i);
		reverse(st + 1, st + top + 1);
		for (int j = 3; j <= top; j += 2) {
			if (!st[j] || !st[j - 2] || st[j] == st[j - 2]) continue;
			const auto _ = emap[st[j - 1]];
			int &u = a[_.second][l + _.first], &v = a[_.second][r - _.first];
			if (u != st[j - 2]) {
				swap(u, v);
			}
		}
	}
	for (int i = 0; i <= t + x; ++i) G[i].clear(), vis[i] = false, d[i] = hd[i] = 0;
	if (len != 2) {
		solve(l, mid); solve(mid + 1, r);
	}
}

void work() {
	cin >> n >> s >> t;
	a.resize(n + 1);
	for (int i = 1; i <= n; ++i) {
		a[i].resize(s + 1);
		for (int j = 1; j <= s; ++j)
			cin >> a[i][j];
	}
	solve(1, s);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= s; ++j) cout << a[i][j] << ' ';
		cout << endl;
	}
}

另：之前听别人说，好像如果没有 $S=2^k$ 这个条件也一定有解，但是好像最好只能做到根号。