P7115 [NOIP2020] 移球游戏题解

(本蒟蒻的第一篇题解，不喜勿喷)

NOIP2020 移球游戏题解

题目描述

有 \(n + 1\) 根柱子（编号 \(1 \sim n+1\)），前 \(n\) 根柱子上有 \(m\) 个球，第 \(n+1\) 根为空。共有 \(n\) 种颜色，每种颜色恰好 \(m\) 个球。

目标：通过移动球（每次只能移动某柱顶部球到另一柱顶部，且每柱球数不超过 \(m\)），使得每根柱子上的球颜色相同。

要求操作次数不超过 \(820000\)。

解法思路

我们采用分治法，将颜色区间不断二分，利用空柱辅助，将柱子按颜色类别划分。

符号说明

\(\text{col}[i][j]\)：柱子 \(i\) 从底到顶的第 \(j\) 个球的颜色。

\(\text{top}[i]\)：柱子 \(i\) 当前的球数。

\(\text{ans}\)：存储操作序列 \((from, to)\)。

\(\text{empty}\)：当前可用的空柱编号（初始为 \(n+1\)）。

核心过程：双柱分离

设当前要分离的两类颜色为 \(A\)（颜色 \(\in [l, \text{mid}]\)）和 \(B\)（颜色 \(\in [\text{mid}+1, r]\)）。

对于两根柱子 \(X\) 和 \(Y\)，以及一个空柱 \(E\)，我们要将 \(X\) 变为纯 \(A\) 类柱或 \(Y\) 变为纯 \(B\) 类柱。

情形 1：\(A\) 类球数量 \(\ge m\)

目标：将 \(X\) 变为纯 \(A\) 类柱。

统计 \(X\) 中 \(A\) 类球的数量 \(s\)。

将 \(Y\) 顶部的 \(s\) 个球移到 \(E\)。

依次处理 \(X\) 的顶部球：

若为 \(A\) 类，移到 \(Y\)；

若为 \(B\) 类，移到 \(E\)。

将 \(Y\) 顶部的 \(s\) 个球（来自 \(X\) 的 \(A\) 类球）移回 \(X\)。

将 \(E\) 顶部的 \(m-s\) 个球（来自 \(X\) 的 \(B\) 类球）移回 \(X\)。

将 \(E\) 中剩下的 \(m-s\) 个球（原 \(Y\) 的顶部球）移回 \(Y\)。

此时 \(X\) 为纯 \(A\) 类柱，\(Y\) 和 \(E\) 恢复原状（但 \(Y\) 可能混有 \(A/B\) 类球）。

情形 2：\(A\) 类球数量 \(< m\)

目标：将 \(Y\) 变为纯 \(B\) 类柱。

统计 \(Y\) 中 \(B\) 类球的数量 \(s\)。

将 \(X\) 顶部的 \(s\) 个球移到 \(E\)。

依次处理 \(Y\) 的顶部球：

若为 \(B\) 类，移到 \(X\)；

若为 \(A\) 类，移到 \(E\)。

将 \(X\) 顶部的 \(s\) 个球（来自 \(Y\) 的 \(B\) 类球）移回 \(Y\)。

将 \(E\) 顶部的 \(m-s\) 个球（来自 \(Y\) 的 \(A\) 类球）移回 \(Y\)。

将 \(E\) 中剩下的 \(m-s\) 个球（原 \(X\) 的顶部球）移回 \(X\)。

此时 \(Y\) 为纯 \(B\) 类柱，\(X\) 和 \(E\) 恢复原状（但 \(X\) 可能混有 \(A/B\) 类球）。

复杂度分析

操作次数：每次双柱分离约需 \(5m\) 次操作，每层分治需 \(O(n)\) 次配对，深度 \(O(\log n)\)，总计约 \(5mn \log n\)。

代入 \(n \le 50, m \le 400\)，得 \(5 \times 400 \times 50 \times \log_2 50 \approx 5 \times 400 \times 50 \times 6 = 600000\)，满足要求。

时间复杂度：\(O(nm \log n)\)。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 60;
const int M = 410;
const int K = 820005;int n, m;
int t;
int top[N];
int a[N][M];
int em;
pair<int, int> ans[K];
bool impx[M], impy[M];void move(int x, int y)
{ans[++t] = make_pair(x, y);a[y][++top[y]] = a[x][top[x]--];
}int merge(int x, int y, int mid)
{int cx = 0, cy = 0;for(int i = 1; i <= m; i++){impx[i] = a[x][i] <= mid;impy[i] = a[y][i] <= mid;}for(int i = 1; i <= m; i++){cx += impx[i];cy += impy[i];}if(cx + cy > m){cx = m - cx;cy = m - cy;for(int i = 1; i <= m; i++){impx[i] ^= 1;impy[i] ^= 1;}}for(int i = 1; i <= m; i++){if(!impx[i] && cx + cy < m){impx[i] = 1;cx++;}}for(int i = cx; i; i--){move(y, em);}for(int i = m; i; i--){if(impx[i]){move(x, y);}else{move(x, em);}}for(int i = m - cx; i; i--){move(em, x);}for(int i = cx; i; i--){move(y, x);}for(int i = cx; i; i--){move(em, y);}for(int i = cx; i; i--){move(x, em);}for(int i = m; i; i--){if(impy[i]){move(y, em);}else{move(y, x);}}int p = em;em = y;return p;
}void solve(int l, int r)
{if(l == r){return;}int mid = (l + r) >> 1;vector<int> now;for(int i = 1; i <= n + 1; i++){if(i == em){continue;}if(l <= a[i][1] && a[i][1] <= r){now.push_back(i);}}for(int i = 0; i + 1 < now.size(); i++){now[i + 1] = merge(now[i], now[i + 1], mid);}solve(l, mid);solve(mid + 1, r);
}int main()
{scanf("%d%d", &n, &m);em = n + 1;for(int i = 1; i <= n; i++){top[i] = m;for(int j = 1; j <= m; j++){scanf("%d", &a[i][j]);}}t = 0;solve(1, n);printf("%d\n", t);for(int i = 1; i <= t; i++){printf("%d %d\n", ans[i].first, ans[i].second);}return 0;
}