Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P7115 [NOIP2020] 移球游戏

发表于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟
标签：            

P7115 [NOIP2020] 移球游戏

考虑当前两个柱子 $A, B$ ，借助柱子 $C$ ，如果只有两种颜色 $1, 2$，怎样将其分开。

  • 统计柱子 $A$ 中颜色 $1$ 的个数 $s$；
  • 将柱子 $B$ 中最上方 $s$ 移动到 $C$ 处；
  • 将柱子 $A$ 中颜色 $1$ 的 $s$ 个移动到 $B$ 处，颜色 $2$ 的移动到 $C$ 处；
  • 将柱子 $B, C$ 中原来 $A$ 的部分重新回到 $A$ ；
  • 将柱子 $B$ 的剩余部分移动到 $C$ 处；
  • 将柱子 $A$ 的两种颜色的上面一种移动到 $B$ 处；
  • 将 $C$ 处（原来 $B$ 的部分）按照上面颜色的划分分到 $A, B$ 处；

对于更多颜色，考虑分治，每次将 $[l, mid]$ 部分当作颜色 $1$ ，$[mid + 1, r]$ 部分当作颜色 $2$ 。任意选择考虑将颜色 $[l, mid]$ 移动到 $[l, mid]$ 柱子上，颜色 $[mid + 1, r]$ 移动到 $[mid + 1, r]$ 柱子上，每次在两侧任选一个不符合条件的柱子，注意到至少有一个颜色满足不小于 $m$ ，考虑使该颜色对应的柱子满足条件，并打上标记，剩下放在另一个柱子上继续处理。

时间复杂度 $T(n) = 2 T(\frac n 2) + n ^ 2 m = n ^ 2 m$ ，操作次数 $T(n) = 2T(\frac n 2) + 5nm = 5nm \log n$ ，可过。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <vector>
#define fi first
#define se second
#define ep emplace_back
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef pair <int, int> PII;
const int N = 60;
bool vis[N];
int n, m;
vector <int> w[N];
vector <PII> ans;
void move (int x, int y)
{
    ans.ep(x, y);
    w[y].ep(w[x].back()), w[x].pop_back();
}
void solve (int l, int r)
{
    if (l == r) return;
    int mid = l + r >> 1;
    for (int i = l; i <= r; ++i) vis[i] = false;
    for (int i = l; i <= mid; ++i)
        for (int j = mid + 1; j <= r; ++j) if (!vis[i] && !vis[j])
        {
            bool op;
            {
                int s = 0;
                for (int k : w[i]) s += k <= mid;
                for (int k : w[j]) s += k <= mid;
                op = s < m;
            }
            int a = i, b = j;
            if (op) swap(a, b);
            int s = 0;
            for (int k : w[a]) s += (k <= mid) ^ op;
            for (int k = 1; k <= s; ++k) move(b, n + 1);
            while (!w[a].empty())
                move(a, (w[a].back() <= mid) ^ op ? b : n + 1);
            for (int k = 1; k <= s; ++k) move(b, a);
            for (int k = 1; k <= m - s; ++k) move(n + 1, a);
            for (int k = 1; k <= m - s; ++k) move(b, n + 1);
            for (int k = 1; k <= m - s; ++k) move(a, b);
            while (!w[n + 1].empty())
                move(n + 1, w[a].size() == m || (w[n + 1].back() > mid) ^ op ? b : a);
            vis[a] = true;
        }
    solve(l, mid), solve(mid + 1, r);
}
int main ()
{
    read(n, m);
    for (int i = 1; i <= n; ++i)
    {
        w[i].resize(m);
        for (int j = 0; j < m; ++j) read(w[i][j]);
    }
    solve(1, n);
    write(ans.size()), puts("");
    for (PII i : ans)
        write(i.fi), putchar(' '), write(i.se), puts("");
    return 0;
}
相关文章