Description

题目链接

Solution

fclose(stdin);
fclose(stdout);
freopen("ball.in", "w", stdout);
puts("2 3");
puts("1 1 2");
puts("2 1 2");
fclose(stdout);
freopen("ball.out", "w", stdout);
puts("5");
puts("1 3");
puts("2 3");
puts("2 1");
puts("3 2");
puts("3 2");
fclose(stdout);

嘛,玩个梗。

首先不妨考虑只有两个柱子,两个颜色的情况。这种小情况很可能帮助我们得出正解。

我们假设这三个柱子的情况如下:

1 2 2 1 1 1 2 2 2
2 1 1 2 2 2 1 1 1

仔细观察,我们不难发现一种方法:首先将第二根柱子上的 $4$ 个元素移动到第三根柱子上:

1 2 2 1 1 1 2 2 2
2 1 1 2 2
1 1 1 2

然后移动第一根柱子上的球,把 $1$ 放在第二根柱子上,把 $2$ 放在第三根柱子上:


2 1 1 2 2 1 1 1 1
1 1 1 2 2 2 2 2 2

然后先把 $1$ 放在第一根柱子上,再把 $2$ 放在第一根柱子上,之后再把第二根柱子上所有的球移动到第三根柱子上:

1 1 1 1 2 2 2 2 2

1 1 1 2 2 2 1 1 2

之后再把第一根柱子上的 $2$ 移动到第二根柱子上,然后我相信大家都会做了。

设第一根柱子中有 $x$ 个 $1$,这样做的操作次数是 $x + m + m + (m - x) + (m - x) = 5m - x$。

如果是多种颜色的话,当然可以直接 $n^2$ 移球,然后你会发现操作次数比 $1000000$ 还要多,不好。

考虑分治,每次将大于中间值的球看作 $2$,小于中间值的球看作 $1$,然后分治操作,同时贪心两边选 $x$ 较小的那一边操作。

然后就可以过了。最差的点只需要 $400000$ 次操作。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

std::vector< std::pair<int, int> > ans;
int a[60][410];
int top[60];
int n, m, tot;
bool b[60];

inline void move(int x, int y) {
    ans.emplace_back(x, y);
    a[y][++top[y]] = a[x][top[x]--];
}

void solve(int l, int r) {
    if (l >= r)    return ;
    int mid = (l + r) >> 1;
    memset(b, false, sizeof(b));
    for (int i = l; i <= mid; ++i) {
        for (int j = mid + 1; j <= r; ++j) {
            if (b[i] || b[j])    continue;
            int s = 0;
            for (int k = 1; k <= m; ++k)    s += (a[i][k] <= mid);
            for (int k = 1; k <= m; ++k)    s += (a[j][k] <= mid);
            if (s >= m) {
                s = 0;
                for (int k = 1; k <= m; ++k)    s += (a[i][k] <= mid);
                for (int k = 1; k <= s; ++k)    move(j, n + 1);
                while (top[i]) {
                    if (a[i][top[i]] <= mid)    move(i, j);
                    else    move(i, n + 1);
                }
                for (int k = 1; k <= s; ++k)    move(j, i);
                for (int k = 1; k <= m - s; ++k)    move(n + 1, i);
                for (int k = 1; k <= m - s; ++k)    move(j, n + 1);
                for (int k = 1; k <= m - s; ++k)    move(i, j);
                while (top[n + 1]) {
                    if (top[i] == m || a[n + 1][top[n + 1]] > mid)    move(n + 1, j);
                    else    move(n + 1, i);
                }
                b[i] = true;
            } else {
                s = 0;
                for (int k = 1; k <= m; ++k)    s += (a[j][k] > mid);
                for (int k = 1; k <= s; ++k)    move(i, n + 1);
                while (top[j]) {
                    if (a[j][top[j]] > mid)    move(j, i);
                    else    move(j, n + 1);
                }
                for (int k = 1; k <= s; ++k)    move(i, j);
                for (int k = 1; k <= m - s; ++k)    move(n + 1, j);
                for (int k = 1; k <= m - s; ++k)    move(i, n + 1);
                for (int k = 1; k <= m - s; ++k)    move(j, i);
                while (top[n + 1]) {
                    if (top[j] == m || a[n + 1][top[n + 1]] <= mid)    move(n + 1, i);
                    else    move(n + 1, j);
                }
                b[j] = true;
            }
        }
    }
    solve(l, mid), solve(mid + 1, r);
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            read(a[i][++top[i]]);
        }
    }
    solve(1, n);
    printf("%d\n", ans.size());
    for (auto i : ans)    printf("%d %d\n", i.first, i.second);
    return 0;
}

Reference

Dzhao 在洛谷上的题解

Rin 博客上的题解

Last modification:September 2nd, 2021 at 02:17 am