Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP7115 [NOIP2020] 移球游戏

Posted on Edited on In
Symbols count in article: 2.3k Reading time ≈ 2 mins.

神仙构造

移球游戏

卡了我很久了

思路

先考虑只有两个柱子（和一个空柱）以及两种球，我们有一下方法（据说写那篇题解的人考场上是瞪样例瞪出来的方法）：

  1. 统计 $i$ 柱的 $1$ 号颜色个数，记为 $ct$

  2. 把 $j$ 柱的 $ct$ 个球移给 $n + 1$ （空柱）

  3. 依次考虑 $i$ 柱所有的球：若为 $1$ 则移给 $j$ 柱；否则移给 $n + 1$ 柱

    完成该步后， $i$ 柱上无球，另两个柱满

  4. 把原来属于 $i$ 柱的球再移回 $i$ ，完成后 $i$ 柱上的球 $0/1$ 分开了（我们让 $1$ 在下面）

  5. 把 $j$ 柱的所有球移给 $n + 1$ ，完成后 $j$ 柱清空

  6. 把 $i$ 柱上层的 $0$ 移给 $j$

  7. 依次考虑 $n + 1$ 柱所有的球：若为 $1$ 则且 $i$ 柱未满则移给 $i$ 柱；否则移给 $j$ 柱

    完成该步后， $n + 1$ 柱上无球，另两个柱满，且 $i$ 柱上只有 $1$

不难发现，上面的操作移动次数为 $ct + m + m + m - ct + m - ct + m = 5m - ct < 5m$

这是对于两个柱子两种球，我们直接上分治，对于 $mid$ ，我们让 $[l, mid]$ 的柱子上球颜色为 $[l, mid]$ ， $[mid + 1, r]$ 柱子上颜色为 $[mid + 1, r]$ ，更具体的，我们直接枚举 $i \in [l, mid], j \in [mid + 1, r]$ ，把 $<mid$ 的颜色当成 $1$ ， $> mid$ 的颜色当成 $0$ ，每次完成 $i, j$ 中的一根柱子即可

用主定理可得，操作次数：
$$
\begin{aligned}
T(n) &= 2T(\frac{n}{2}) + 5mn \\
T(n) &= 5mn \log n
\end{aligned}
$$
而时间为：
$$
\begin{aligned}
T(n) &= 2T(\frac{n}{2}) + 5mn + n^2 + nm\\
T(n) &= nm
\end{aligned}
$$
（应该吧？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define pb push_back
#define pop pop_back
#define fi first
#define se second
using PII = std::pair<int, int>;
const int N = 50 + 5, M = 400 + 100, K = 820000 + 100;
int n, m;
bool vis[N];
std::vector<int> a[N];
std::vector<PII> ans;
void mv(int from, int to)
{
	ans.pb({from, to});
	a[to].pb(a[from].back());
	a[from].pop();
}
void work(int i, int j, int mid, int cmp)
{
	if (cmp) std::swap(i, j);
	int ct = 0;
	for (int c : a[i]) ct += (c <= mid) ^ cmp;
	for (int k = 1; k <= ct; ++k) mv(j, n + 1);
	for (int k = m - 1; ~k; --k)
		if ((a[i][k] <= mid) ^ cmp) mv(i, j);
		else mv(i, n + 1);
	for (int k = 1; k <= ct; ++k) mv(j, i);
	for (int k = m - ct; k; --k) mv(n + 1, i);
	for (int k = m - ct; k; --k) mv(j, n + 1);
	for (int k = m - ct; k; --k) mv(i, j);
	for (int k = m - 1; ~k; --k)
		if ((a[n + 1][k] <= mid) ^ cmp && a[i].size() < m) mv(n + 1, i);
		else mv(n + 1, j);
	vis[i] = true;
}
void sol(int l, int r)
{
	if (l == r) return ;
	int mid = (l + r) >> 1, ct;
	memset(vis + l, false, sizeof(bool) * (r - l + 1));
	for (int i = l; i <= mid; ++i) if (!vis[i])
		for (int j = mid + 1; j <= r; ++j) if (!vis[j])
		{
			ct = 0;
			for (int c : a[i]) ct += c <= mid;
			for (int c : a[j]) ct += c <= mid;
			work(i, j, mid, ct < m);
			if (vis[i]) break;
		}
	sol(l, mid), sol(mid + 1, r);
}
int main()
{
	scanf("%d %d", &n, &m);
	ans.reserve(K);
	for (int i = 1; i <= n + 1; ++i) a[i].reserve(m);
	for (int i = 1, c; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			scanf("%d", &c);
			a[i].pb(c);
		}
	sol(1, n);
	printf("%d\n", ans.size());
	for (PII as : ans) printf("%d %d\n", as.fi, as.se);
	return 0;
}