「4th Ucup Stage 10」A. Automatized Mineral Classification

发表于 分类于 本文字数： 977 阅读时长 ≈ 4 分钟

Description

Link：QOJ 16000

This is an interactive problem.

对于 1,⋯ ,n1, \cdots, n，有一个隐藏的序列 aia_i，其中 aia_i 表示数字 ii 的颜色。

有一个队列（初始为空），可以进行以下两种操作：

  • + id：将元素 id\mathrm{id} 加入队列末尾。
  • -：将队列开头的元素弹出。

每次操作之后，你都会得知当前队列中共有多少种不同的元素。

你的目标是，将所有元素按照颜色分组，依次给出每个组中的元素。

数据范围：1≤n≤5001 \leq n \leq 500，操作至多进行 3500035000 次。交互器不自适应。

时空限制：11s / 256256MiB。

Solution

生日悖论：O(nn)\mathcal{O}(n\sqrt{n})

将序列 aa 的元素依次加入队列，直到第一次出现重复的元素时，最后加入的元素 xx 一定与之前的某一个元素 yy 相同。然后我们清空队列，在清空队列的过程中我们就可以找到元素 yy 与 xx。然后从序列 aa 中删除 xx，重复上述的步骤。

直接这样暴力肯定有问题，不过我们可以将其打乱一下。在元素的顺序是随机的情况下，可以证明一次迭代的操作次数期望为 O(n)\mathcal{O}(\sqrt{n})。

这就是生日悖论，假设我们有 nn 个元素，分别来自 kk (k≤n2k \leq \frac{n}{2}) 种不同的颜色。随机抽取 O(k)\mathcal{O}(\sqrt{k}) 个元素，就会出现重复的元素。该结论即使在颜色的分布是有偏的情况下，依然成立。

分治：O(nlog⁡n)\mathcal{O}(n \log n)

首先将序列 aa 的元素依次加入队列，每次当前颜色增加时，说明出现了一个新的颜色，将当前的元素视作该颜色的代表元素。这些代表元素构成集合 RR。

设 solve(l,r,R)\mathrm{solve}(l, r, R) 表示求解区间 [l,r][l, r] 中所有元素的颜色，其中区间 [l,r][l, r] 所有颜色的并集构成 RR。

假设往左半段递归，我们先将区间 [l,mid][l, \mathrm{mid}] 中所有元素加入队列，然后将集合 RR 中的元素加入队列，若 r∈Rr \in R 加入队列的时候当前颜色数量不变，则说明区间 [l,mid][l, \mathrm{mid}] 中存在颜色为 rr 的元素，需要将 rr 加入 R1R_1；否则说明区间 [l,mid][l, \mathrm{mid}] 不存在颜色为 rr 的元素。

然后我们将队列清空，并递归求解 solve(l,mid,R1)\mathrm{solve}(l, \mathrm{mid}, R_1)。当然 solve(mid+1,r,R2)\mathrm{solve}(\mathrm{mid} + 1, r, R_2) 也是同理。

期望操作次数 O(nlog⁡n)\mathcal{O}(n \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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>

using i64 = long long;

#define debug(a) std::cout << #a << '=' << (a) << ' '

template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

const int N = 510;

int n, B;

int times;

int push(int x) {
    assert(++ times <= 35000);
    std::cout << "+ " << x << std::endl;
    int res;
    std::cin >> res;
    return res;
}
int pop() {
    assert(++ times <= 35000);
    std::cout << "-" << std::endl;
    int res;
    std::cin >> res;
    return res;
}

std::vector<int> key0;

std::vector<int> hold[N];

void solve(int l, int r, std::vector<int> key) {
    if (l == r) {
        assert(key.size() == 1);
        hold[key[0]].push_back(l);
        return;
    }
    int mid = (l + r) >> 1;

    std::vector<int> lkey, rkey;
    {
        int lst = 0;
        for (int x : key) {
            lst = push(x);
        }
        for (int i = l; i <= mid; i ++) {
            lst = push(i);
        }

        for (int x : key) {
            int net = pop();
            if (net == lst) {
                lkey.push_back(x);
            }
            lst = net;
        }
        for (int i = l; i <= mid; i ++) {
            pop();
        }
    }
    {
        int lst = 0;
        for (int x : key) {
            lst = push(x);
        }
        for (int i = mid + 1; i <= r; i ++) {
            lst = push(i);
        }

        for (int x : key) {
            int net = pop();
            if (net == lst) {
                rkey.push_back(x);
            }
            lst = net;
        }
        for (int i = mid + 1; i <= r; i ++) {
            pop();
        }
    }

    solve(l, mid, lkey);
    solve(mid + 1, r, rkey);
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n;

    {
        int lst = 0;
        for (int i = 1; i <= n; i ++) {
            int net = push(i);
            if (net == lst + 1) {
                key0.push_back(i);
                lst = net;
            }
        }
        for (int i = 1; i <= n; i ++) {
            pop();
        }
    }

    solve(1, n, key0);

    int anslen = 0;
    for (int i = 1; i <= n; i ++) {
        if (hold[i].size()) {
            anslen ++;
        }
    }
    std::cout << "! " << anslen << std::endl;
    for (int i = 1; i <= n; i ++) {
        if (hold[i].size()) {
            std::cout << hold[i].size() << ' ';
            for (int x : hold[i]) {
                std::cout << x << ' ';
            }
            std::cout << std::endl;
        }
    }

    return 0;
}