题解 P7115 【移球游戏】
Warriors_Cat
2020-12-16 17:05:25
Life is continuing……
---
[题面传送门](https://www.luogu.com.cn/problem/P7115)，题意可以从这里看。
这里仅仅讲正解，如果需要知道暴力怎么打可以去其他题解看。
---
### $Solution:$
以下把柱子看作栈，球看作数字，颜色看作权值。
先考虑一个小问题：
给 $A$，$B$ 两个满栈和一个空栈 $C$，数字权值均为 $0$ 或 $1$，**$A$，$B$ 的数字合并起来可以有一种权值的个数 $> m$**。现假设权值 $0$ 的个数 $\ge m$，如何利用这三个栈使得 $A$，$B$ 栈为满栈且 $A$ 栈数字权值均为 $0$。
这个问题是可以解决的，具体操作如下：
1. 记 $A$ 栈中 $0$ 的个数为 $x$，将 $B$ 栈前 $x$ 个数字放至 $C$ 栈。
2. 依次枚举 $A$ 栈的数字，如果权值为 $0$ 则放入 $B$ 栈，否则放入 $C$ 栈，显然 $A$ 栈空后 $B$，$C$ 栈均满。
3. 将 $B$ 栈前 $x$ 个元素放至 $A$ 栈，再将 $C$ 栈中前 $m - x$ 个元素放入 $A$ 栈，最后将 $C$ 栈中剩下 $x$ 个元素放入 $B$ 栈。
4. 记 $B$ 栈中 $0$ 的个数为 $y$，将 $A$ 栈前 $y$ 个数字放至 $C$ 栈。由小问题题面可知 $x + y \ge m$。
5. 依次枚举 $B$ 栈的数字，如果权值为 $0$ 则放入 $A$ 栈，否则放入 $C$ 栈。$B$ 栈空后，因为 $x + y \ge m$，所以此时 $A$ 栈数字权值均为 $0$。
6. 将 $C$ 栈中所有的数字放至 $B$ 栈，以保证 $C$ 还是空栈。
显然这里的操作次数是 $4m + 2x + y$ 次，最坏为 $7m$ 次。
当然在实际代码可能是权值为 $1$ 的个数 $> m$，原理相同，这里不再多讲。
我们记这个操作叫做 “利用 $B$ 填充 $A$ 的 $0$” 或 “利用 $B$ 填充 $A$ 的 $1$”。
考虑分治。假设我们现在要操作的区间为 $(L, R)$，$mid = \dfrac{L + R}{2}$。
我们将 $L$ 到 $R$ 上所有的数字中颜色 $> mid$ 的权值记为 $1$，否则记为 $0$。
分治的目标是：**将 $L$ 到 $mid$ 上所有的数字的权值都变为 $0$，将 $mid + 1$ 到 $R$ 上所有的数字的权值都变为 $1$**。
跟普通的快排一样，我们运用双指针 $l$ 和 $r$，一开始分别指向 $L$ 和 $R$。然后统计其中权值为 $1$ 的个数。如果这个个数 $> m$ 就利用 $l$ 填充 $r$ 的 $1$，同时 $r$ 左移；否则利用 $r$ 填充 $l$ 的 $0$，同时 $l$ 右移。
然后就可以变成 $(L, mid)$ 和 $(mid + 1, R)$ 两个区间的子问题了。如此归并下去，到 $L = R$ 的时候自然排好了。
另外，这里的快排是不会退化到 $O(n^2)$ 的。普通的快排退化到 $O(n^2)$ 是因为 $mid$ 处的权值可能是最大的，或者是最小的，这样就使得操作数大大增加。而在这里权值为 $0$ 的个数与权值为 $1$ 的个数是绝对的，而且相差为 $m$，所以很平均，不会被卡。
根据快排的时间复杂度，可得总操作次数为 $7nm\left\lceil\log_2n\right\rceil$，算一下大约是 $840000$，还差一点。
这里膜拜一下铃酱（[鏡音リン](https://www.luogu.com.cn/user/90893)），学了 TA 的优化这题就做完了。
我们发现在“利用 $B$ 填充 $A$ 的 $0$ / $1$” 的常数特别大，能不能有办法减小常数呢？
答案是有的。在这个操作中，如果 $x > \dfrac{m}{2}$，那么我们可以只把 $B$ 栈前 $m - x$ 个数字放到 $C$，然后在 $2.$ 中交换一下 $B$、$C$ 的性质，最后再把 $C$ 中剩下的 $m - x$ 个元素还回去即可。
于是操作次数降为 $4m + 2\min\{x, m - x\}+y$，最坏为 $6m$。
总操作次数就变为了 $6nm\left\lceil\log_2n\right\rceil$，大约是 $700000$，时间复杂度也是此级别，对于这道题来说算是绰绰有余了。
---
### $Code:$
代码不长，2KB 都不到，而且很好写。
以下代码仅供参考。
```cpp
#include <cstdio>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 60, M = 410, K = 820010;
int n, m, a[N][M], len[N], ans, q[K], b[N][M];
inline void Move(int x, int y){ a[x][++len[x]] = a[y][len[y]]; b[x][len[x]] = b[y][len[y]]; --len[y]; q[++ans] = y * 65 + x; }//单次移动 y -> x
inline void movenum(int x, int y, int z){ while(z--) Move(x, y); }//多次移动 y -> x
inline void movecol(int x, int y, int z){// 利用 y 填充 x 为 z
int num = 0; for(int i = 1; i <= m; ++i) num += (b[x][i] == z);
if(num == m) return; if(num > m / 2){
movenum(n + 1, y, m - num);
for(int i = m; i; --i){ if(b[x][i] == z) Move(n + 1, x); else Move(y, x); }
movenum(x, n + 1, num); movenum(x, y, m - num); movenum(y, n + 1, m - num);
}else{
movenum(n + 1, y, num);
for(int i = m; i; --i){ if(b[x][i] == z) Move(y, x); else Move(n + 1, x); }
movenum(x, y, num); movenum(x, n + 1, m - num); movenum(y, n + 1, num);
}
num = 0; for(int i = 1; i <= m; ++i) num += (b[y][i] == z); movenum(n + 1, x, num);
for(int i = m; i; --i){ if(b[y][i] == z) Move(x, y); else Move(n + 1, y); } movenum(y, n + 1, m);
}
inline void Qsort(int l, int r){//分治
if(l == r) return; int mid = l + r >> 1, x = l, y = r;
for(int i = l; i <= r; ++i) for(int j = 1; j <= m; ++j) b[i][j] = (a[i][j] > mid);
while(x <= mid && y > mid){
int num = 0;
for(int i = 1; i <= m; ++i) num += b[x][i] + b[y][i];
if(num > m) movecol(y--, x, 1); else movecol(x++, y, 0);
}
Qsort(l, mid); Qsort(mid + 1, r);
}
inline void print(){ printf("%d\n", ans); for(int i = 1; i <= ans; ++i) printf("%d %d\n", q[i] / 65, q[i] % 65); }
int main(){
n = read(); m = read();
for(int i = 1; i <= n; ++i){
len[i] = m;
for(int j = 1; j <= m; ++j){
a[i][j] = read();
}
}
Qsort(1, n); print(); return 0;
}
```
---
总的来说这题思维难度还是很高的，特别是得先想到一个小问题再转换为大问题，同时还要运用分治思想。尽管在 NOIp 中出构造题可能会有些不妥，但不可否认这题质量之高。