P7115 [NOIP2020] 移球游戏
大意
有 \(n+1\) 根柱子（编号 \(1 \sim n+1\)），其中 \(1 \sim n\) 号柱子初始时各有 \(m\) 个球（球按自底向上的顺序摆放），\(n+1\) 号柱子初始为空；所有球共包含 \(n\) 种颜色，且每种颜色的球恰好有 \(m\) 个。
允许执行的操作是：将某根柱子最上方的球移动到另一根柱子的最上方，操作需满足两个条件：
- 源柱子（移出球的柱子）非空；
- 目标柱子（移入球的柱子）上的球数量不超过 \(m-1\)。
要求通过不超过 \(820000\) 次上述操作，使得所有同一种颜色的球都汇聚到同一根柱子上（每种颜色最终对应哪根柱子无限制）。
思路
首先，这个题是个构造题，然后我们考虑构造方法，先看特殊性质 \(n = 2\) 的时候，也就是说此时只有 \(3\) 个柱子和 \(2\) 种颜色，那么我们应该怎么去放这个东西呢？
我们将两种颜色用白和黑表示，那么我们很容易想到去分离黑白，如何做呢？如上图，我们先在第二个柱子上空出第一个柱子中黑的个数，这样就可以将第一根柱子黑白分离，再把分离好的放回去，把剩下的没分的整到一根柱子上，再把第一根的黑白分离到两个不同的柱子上，然后把没分离的那根柱子直接按黑白分离即可。
总操作次数是：\(5m - k\)，\(k\) 表示第一个柱子中黑的个数。
我们继续考虑 \(n\) 比较大的时候怎么办，我们可以像刚刚的操作一样，对于每一个颜色 \(i \in [1, n]\) 依次操作，对于颜色 \(i\)，先把 \([i + 1, n]\) 的柱子中的颜色 \(i\) 全放在柱头，然后直接如下图进行操作即可：
但是经过计算发现以上的构造方式并不能通过本题，我们需要考虑其他的方法。
考虑分治。
我们发现对于 \(n = 2\) 的情况处理起来很容易，要是全部都能当成两个颜色做就好了，于是我们就可以对于当前处理的区间 \([l, r]\) 进行分治 \([l, mid], [mid + 1, r]\)，我们将 \([l, mid]\) 的柱子全部整理成颜色小于等于 mid 的，将 \([mid + 1, r]\) 的柱子全部整理成颜色大于 mid 的，每次分治时，可以 \(\mathcal{O}(n ^ 2)\) 的去枚举 \(i \in [l, mid], r \in [mid + 1, r]\)，对 \(i\) 和 \(j\) 的颜色整理。如果两个柱子中颜色小于等于 mid 的大于 \(m\)，就将 \(i\) 整理，反之。
因此就解决了这道题。
代码
#include<iostream>
using namespace std;const int MAXN = 55;
const int MAXM = 405;
const int OPTION = 820005;
int a[MAXN][MAXM];
int top[MAXN];
int path[OPTION][2];
int tot = 0;
int n, m;void Move(int x, int y){path[++ tot][0] = x;path[tot][1] = y;a[y][++ top[y]] = a[x][top[x] --];
}bool cmp(int x, int y, int ball, int mid){if(x < y){return ball <= mid;}return ball > mid;
}void order(int x, int y, int z, int mid){int k = 0;for(int i = 1;i <= m;i ++){if(cmp(x, y, a[x][i], mid)){k ++;}}//空出 k 个位置 便于后面分解 x 柱子的 0 / 1for(int i = 1;i <= k;i ++){Move(y, z);}//按 0 / 1 分离for(int i = m;i >= 1;i --){if(cmp(x, y, a[x][i], mid)){Move(x, y);}else{Move(x, z);}}for(int i = 1;i <= k;i ++){Move(y, x);}for(int i = 1;i <= m - k;i ++){Move(z, x);}for(int i = 1;i <= m - k;i ++){Move(y, z);}for(int i = 1;i <= m - k;i ++){Move(x, y);}for(int i = m;i >= 1;i --){// if(top[z] == 0) break;if(top[x] < m && cmp(x, y, a[z][top[z]], mid)){Move(z, x);}else{Move(z, y);}}
}void solve(int l, int r){if(l == r) return;bool flag[MAXN] = {0};int mid = (l & r) + ((l ^ r) >> 1);for(int i = l;i <= mid;i ++){for(int j = mid + 1;j <= r;j ++){if(flag[i] || flag[j]) continue;int s = 0;for(int k = 1;k <= m;k ++){if(a[i][k] <= mid){s ++;}}for(int k = 1;k <= m;k ++){if(a[j][k] <= mid){s ++;}}if(s >= m){order(i, j, n + 1, mid);flag[i] = 1;}else{order(j, i, n + 1, mid);flag[j] = 1;}}}solve(l, mid);solve(mid + 1, r);
}int main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){cin >> a[i][j];}}for(int i = 1;i <= n;i ++){top[i] = m;}top[n + 1] = 0;solve(1, n);cout << tot << '\n';for(int i = 1;i <= tot;i ++){cout << path[i][0] << ' ' << path[i][1] << '\n';}return 0;
}