[NOIP2020] 移球游戏

心路历程

嘶, 去年做的时候根本就不会, 而且 \(CCF\) 又是第一次出 \(SPJ\) 的题, 当时的我, 真的一脸蒙蔽...

好, 来看一下这道题.

给出 \(n\) 种颜色的球, 每种颜色有 \(m\) 个, 有 \(n + 1\) 个柱子, 初始有一个是空的, 其他的上面都有 \(m\) 个球, 要让我们把相同颜色的球放到同一个柱子上.

看完题, 我的感觉告诉我, 球的数量与做法没有任何关系, 只要找到移动的规律即可. 移动的方法的话, 我感觉应该是先将某一个颜色全都移到空柱子上, 然后再腾出一个柱子, 这样就可以化繁为简, 将问题逐渐简化.

看一下数据范围, \(n \le 50, m \le 400\) , 没有特殊数据, 一共有 \(50 * 400 = 2e4\) 个球, 我们最多只能进行 \(8.2e5\) 次操作, 如果匀一下的话, 每个球应该有 \(41\) 次操作, 越向后需要移动的球就越少, 所以我们每个球的移动次数应该在 \(50\) 左右, 可以分配的次数应该远大于 \(50\) .

我们考虑如何让某一个柱子上的某一个颜色全都移动到某个特定的柱子上.

首先, 由于 \(n\) 个柱子都是满的, 所以我们就以某一个柱子的最下面的球开始, 将这个柱子全都变成这个颜色. 我们先将上面的 \(m - 1\) 个球移走, 移到空柱子上, 然后我们找到这个颜色的球的所有位置, 将该位置上面的球都移到我们的目标柱子上, 再把当前颜色的球移到最开始的空柱子上, 然后把目标柱子上的没用的球都移回来, 再把最开始的空柱子上的那个球给弄到目标柱子上, 移动次数大概在 \(2n\) 左右, 然后由于我们的次数其实是带常数的, 所以完全够用.

有点像维护了 \(n\) 个栈的感觉.

好! 遇到新的问题了, 按照上面写完了, 疯狂 \(RE\) , 现在解决了, 但是又出现了新的问题.

也就是我们的目标柱子只有一个, 如果放满了, 怎么办.

我想的是, 挨个放, 比如, 我们当前的目标柱子是 \(now\) , 当前的柱子是 \(i\) , 那我们就从 \(now\) 到 \(i - 1\) 挨个放, 哦! 好像是这样, 我刚才还在想复原的事, 其实仔细一想, 没必要复原. 好耶 ヽ(✿ﾟ▽ﾟ)ノ \(ヽ(✿ﾟ▽ﾟ)ノ\)

好, 正常的样例都过了, 现在出现了一点小情况, 就是不知道怎么回事, 出现了 \(Move(i, i)\) 的情况, 也就是说, 死循环了. 我以为是没有重新置 \(now\) 为缓冲区, 但是事实上我这样做了.

可以, 自己造了一组小数据, 发现了问题所在, 然后改出来了, 大样例也过了, 可惜只有 \(45pts\) , 全是 \(RE\) , 检查一下是不是次数多了.

好的, 果然不出所料, 是策略的问题, 移动次数过多.

那么我们来看一下, 如何减少移动次数, 在这之前, 先求一下极限情况下我们的移动次数.

好的, 优化了一波(或者说两波), 现在比之前少移动了一半, 但是还是不够, 可以用一个堆优化一波? 每次放到堆顶? 来, 似乎可行.

没写堆的, 感觉不好写...先写了个类似排序的, 每次选底下相同的最多的进行 \(Solve\) , 代码难度低, 直接改就行.

写完了, 还是不行, 优化太小...唉...

换了一个写法, 大体思路一样, 但是步骤优化了一下, 我们记最后一个柱子为 \(ed\) , 最开始是 \(n + 1\) , 显然 \(> ed\) 的柱子都已经收拾好了, 所以我们每次从 \(1 \sim ed - 1\) 里找到在顶端连续出现的次数和最多的一个颜色的球, 然后全部挪到 \(ed\) , 之后找到 \(1 \sim n\) 中当前颜色的球, 每次将该颜色的球上面的球挪到没满的柱子上, 优先选择当前柱子之前的柱子, 其次是从 \(ed - 1\) 向前选.

唉, 想太久了, 再久就得不偿失了, 思考了这么久, 收获已经很大了, 看看题解, 理解一下吧.

我靠, 太妙了, 利用分治的思想, 每次找到一个阈值 \(x\) , 将 \(> x\) 的看作 \(1\) , \(< x\) 的看作 \(0\) , 这样其实每次操作就转化成了对两个颜色进行复原, 而对两个颜色进行复原的操作数为 \(m^2 n \log n\)

嘶, 在写正解的过程中突然发现之前的优化写锅了, 然后又改了一下之前的代码 \(95pts\) !!!就一个 \(while\) , 高了 \(50pts\) !!!

尝试了各种优化, 最终还是 \(95pts\) 了. 果然, 只凭我自己, 还是无法切掉 \(NOIP\) 的 \(T3\) ...写题解做法去了.

刚才其实又调了一会...因为又想到一个做法, 那个应该是能过的, 毕竟现在只差 \(6w\) 次了, 但是考场上写这个属于一种赌吧, 如果想不到正解, 赌一把也不错, 毕竟能拿到 \(95pts\) 虽然不一定能猜到.

歪解

每次贪心的选择底部连续相同的最多的柱子作为当前柱子 \(now\) , 然后贪心的移动, 这里有个小技巧, 写两个贪心, 一个正着跑, 一个倒着跑, 感谢 @EdisonBa 提供的奇妙骗分思路, 其实这两个贪心在随机情况下都很优, 都可以获得 \(95pts\) 的高分, 然后 在时间充足 的情况下, 我们可以跑多个贪心, 以取最优解, 代码较长, 但是两个 \(Solve\) 函数本质区别不大, 只是有一点细节差异, 注意一下即可, 注释较为详细, 不多赘述.

\(code:\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define Top(x) ball[x][top[x]]

inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  return x * f;
}

const int N = 55, M = 405, K = 1e7;

struct Solve {
  int n, m, ball[N][M];
  int now, have[N], top[N], col[N];
  int ans, ans1[K], ans2[K];
  bool vis[N];

  void Find() {
    memset(have, 0, sizeof(have));
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (ball[i][j] == col[now]) have[i]++;
      }
    }
  }

  inline void Move(int x, int y) {
    ball[y][++top[y]] = ball[x][top[x]--];
    ans1[++ans] = x, ans2[ans] = y;
  }
  
  void Solve1() { //正着解决.
    int x = now;
    for (int i = 2; i <= m; i++) { //将当前柱子上除了最下面的颜色相同的球都移到 n + 1 上.
      if (ball[now][i] != col[now]) {
        for (; i <= m; i++) Move(now, n + 1);
      }
    }
    for (int i = 1; i <= n; i++) { //将 n 个柱子上的当前颜色的球归位.
      if (vis[i] || i == now) continue;
      x = 1; //充当缓冲区的柱子.
      if (have[i]) {
        while (have[i]) {
          while (top[x] == m || x == i || vis[i]) x++; //缓冲区满了, 换下一个.
          if (x == n + 1 && top[now] < m) x = now;
          if (Top(i) != col[now]) Move(i, x); //颜色不对, 将该柱子上的其他颜色的球暂时扔到缓冲区里.
          else { //颜色对, 先将颜色正确的球挪到 n + 1 上, 然后颜色不对的球回归原位, 再将颜色正确的球放到 now 上.
            have[i]--, Move(i, n + 1); //颜色对的暂时放到 n + 1 .
            if (top[n + 1] == m) { //如果 n + 1 满了, 直接操作, 没满就不操作.
              while (Top(now) != col[now]) Move(now, i); //把 now 当缓冲区时上面放的都挪回去.
              while (Top(n + 1) == col[now]) Move(n + 1, now);
            }
          }
        }
        while (Top(now) != col[now]) Move(now, i); //将 now 上的颜色不对的挪走.
        while (Top(n + 1) == col[now]) Move(n + 1, now); //将 n + 1 上颜色对的挪回来.
      }
    }
    x = n;
    while (top[n + 1]) { //清空 n + 1 .
      while (top[x] == m || x == now) x--;
      if (Top(n + 1) == col[now]) Move(n + 1, now); //颜色对的归位.
      else Move(n + 1, x);
    }
  }

  void Solve2() { //倒着解决.
    int x = n;
    for (int i = 2; i <= top[now]; i++) { //将当前柱子上除了最下面的颜色相同的球都移到 n + 1 上.
      if (ball[now][i] != col[now]) {
        while (i <= top[now]) Move(now, n + 1);
      }
    }
    for (int i = 1; i <= n; i++) { //将 n 个柱子上的当前颜色的球归位.
      if (vis[i] || i == now) continue;
      x = n; //充当缓冲区的柱子.
      if (have[i]) {
        while (have[i]) {
          while (top[x] == m || x == i) x--; //缓冲区满了, 换下一个.
          if (x == 0) { //说明除了 now 的柱子都满了.
            if (top[now] == m) x = n + 1; //判断 now 满没满, 如果满了就只能扔到 n + 1 了.
            else x = now;
          }
          if (Top(i) != col[now]) Move(i, x); //颜色不对, 将该柱子上的其他颜色的球暂时扔到缓冲区里.
          else { //颜色对, 先将颜色正确的球挪到 n + 1 上, 然后颜色不对的球回归原位, 再将颜色正确的球放到 now 上.
            have[i]--, Move(i, n + 1); //颜色对的暂时放到 n + 1 .
            if (top[n + 1] == m) { //如果 n + 1 满了, 直接操作, 没满就不操作.
              while (Top(now) != col[now]) Move(now, i); //把 now 当缓冲区时上面放的都挪回去.
              while (Top(n + 1) == col[now]) Move(n + 1, now);
            }
          }
        }
        while (Top(now) != col[now]) Move(now, i); //将 now 上的颜色不对的挪走.
        while (Top(n + 1) == col[now]) Move(n + 1, now); //将 n + 1 上颜色对的挪回来.
      }
    }
    x = n;
    while (top[n + 1]) { //清空 n + 1 .
      while (top[x] == m || x == now) x--;
      if (Top(n + 1) == col[now]) Move(n + 1, now); //颜色对的归位.
      else Move(n + 1, x);
    }
  }

  inline void Run1() { //正着跑.
    for (int i = 1; i <= n; i++) { //每次找在最下面连续的一段最长的.
      int Max = 0, id = 0;
      for (int j = 1; j <= n; j++) {
        if (vis[j]) continue;
        int k = 1;
        while (ball[j][++k] == ball[j][1]);
        k--;
        if (k > Max) Max = k, id = j;
      }
      now = id, col[id] = ball[id][1];
      Find();
      Solve1();
      vis[id] = 1;
    }
  }

  inline void Run2() { //倒着跑.
    for (int i = 1; i <= n; i++) { //每次找在最下面连续的一段最长的.
      int Max = 0, id = 0;
      for (int j = 1; j <= n; j++) {
        if (vis[j]) continue;
        int k = 1;
        while (ball[j][++k] == ball[j][1]);
        k--;
        if (k > Max) Max = k, id = j;
      }
      now = id, col[id] = ball[id][1];
      Find();
      Solve2();
      vis[id] = 1;
    }
  }
} S1, S2;

int main() {
  int n = read(), m = read();
  S1.n = n, S1.m = m;
  for (int i = 1; i <= n; i++) {
    S1.top[i] = m;
    for (int j = 1; j <= m; j++) {
      S1.ball[i][j] = read();
    }
  }
  S2 = S1;
  S1.Run1();
  S2.Run2();
  if (S1.ans < S2.ans) { //选更优的一个.
    printf("%d\n", S1.ans);
    for (int i = 1; i <= S1.ans; i++) printf("%d %d\n", S1.ans1[i], S1.ans2[i]);
  } else {
    printf("%d\n", S2.ans);
    for (int i = 1; i <= S2.ans; i++) printf("%d %d\n", S2.ans1[i], S2.ans2[i]);
  }
  return 0;
}