Znzryb's Blog
0%

Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)（我们可以使用这个数学归纳法，得到一个关于 a 的一个关键性质）（我们还是没有想到怎么做？那应该是对 a 的性质探索的还不够多）

Posted on Edited on

题目大意

题目描述
定义集合 SS 的 kk-mex 为未在 SS 中出现的第 kk 小的非负整数。例如，集合 [1,2,1][1, 2, 1] 的 11-mex 是 00，22-mex 是 33。

给定一个长度为 nn 的非负整数数组 a1,a2,…,ana_1, a_2, \ldots, a_n。你需要判断是否存在一个非负整数数组 b1,b2,…,bnb_1, b_2, \ldots, b_n（其中 0≤bi≤1090 \le b_i \le 10^9），使得对于所有 1≤i≤n1 \le i \le n，前缀 [b1,…,bi][b_1, \ldots, b_i] 的 (n−i+1)(n-i+1)-mex 恰好等于 aia_i。

如果存在这样的数组，请构造并输出任意一个满足条件的数组 bb；如果不存在，请报告无解。

输入格式
第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例的第一行包含一个整数 nn（1≤n≤2⋅1051 \le n \le 2 \cdot 10^5），表示数组 aa 的长度。
第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n（0≤ai≤1090 \le a_i \le 10^9）。
保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式
对于每个测试用例，如果存在满足条件的数组 bb，第一行输出 YES（不区分大小写），第二行输出 nn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_n（0≤bi≤1090 \le b_i \le 10^9）。
如果不存在，仅输出一行 NO。

样例数据

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
Input:
6
3
3 3 1
3
2 1 3
1
0
1
2
4
7 5 2 2
6
6 6 6 4 3 3

Output:
YES
2 0 2
NO
YES
67
NO
NO
YES
5 2 1 5 2 0

样例解释
在第一组测试用例中，a=[3,3,1]a = [3, 3, 1]。我们可以验证数组 b=[2,0,2]b = [2, 0, 2] 满足条件：

  • 当 i=1i=1 时，需要计算前缀 [b1]=[2][b_1] = [2] 的 (3−1+1)(3-1+1) 即 33-mex。未在数组中出现的非负整数依次为 0,1,3,4,…0, 1, 3, 4, \dots，其中第 33 小的是 33，等于 a1a_1。

  • 当 i=2i=2 时，需要计算前缀 [b1,b2]=[2,0][b_1, b_2] = [2, 0] 的 (3−2+1)(3-2+1) 即 22-mex。未在数组中出现的非负整数依次为 1,3,4,…1, 3, 4, \dots，其中第 22 小的是 33，等于 a2a_2。

  • 当 i=3i=3 时，需要计算前缀 [b1,b2,b3]=[2,0,2][b_1, b_2, b_3] = [2, 0, 2] 的 (3−3+1)(3-3+1) 即 11-mex。未在数组中出现的非负整数依次为 1,3,4,…1, 3, 4, \dots，其中第 11 小的是 11，等于 a3a_3。

在第二组测试用例中，a=[2,1,3]a = [2, 1, 3]。可以证明不存在任何满足条件的数组 bb，因此输出 NO。

在第三组测试用例中，a=[0]a = [0]。构造 b=[67]b = [67] 满足条件，因为前缀 [b1]=[67][b_1] = [67] 的 11-mex 是 00，恰好等于 a1a_1。

思路讲解

首先，需要这样子想，每一个 a 代表什么？可以这样子想：

image

不难发现：（使用归纳法）

image

当然，我们可以换成这个 i。

image

为什么可以 = 呢？

image

其实这个规律还是没有那么难以观察出来的，毕竟这个 a1 代表第 n 个空，a2 代表第 n-1 个空，你也很难想象第 n-1 个空在第 n 个空后面是吧？

我觉得上面 AI 的这个角度还是挺好的，但是我其实觉得稍微有点扯。

然后我们还是没有想到怎么做？那应该是对 a 的性质探索的还不够多！（继续沿着探索 a 的性质的这条路走）

其实光有这个递减性质，其实还是不够的，我们不妨多探索一些性质，比如说 ai+1 其取值范围到底是在哪里？

image

image

通过上面的推导，我们不难得出如下结论：

image

这道题目，我们的做法需要用到 dsu on next 技巧。那么要注意这个合并方向。

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
vector<ll> B(N + 2);
ll cur;
vector<ll> wp;
ll top_b = 0;
for (int i = 1; i <= N; ++i) {
  // 我觉得一般来说，你还是不要用哨兵节点，老老实实特判比较好，确保初值正确
    if (i == 1) {
        if (A[i] > N) {
            cout << "NO\n";
            return;
        }
        if (A[i] == N) {
            wp.push_back(i);
            cur = N;
        } else if (A[i] == N - 1) {
            B[i] = mod;
            cur = N - 1;
        } else {
            cout << "NO\n";
            return;
        }
        merge(A[i], A[i] - 1);
        continue;
    }
    if (A[i] == cur) {
      // wp 存储的就是我们存下来的，等待填充的 B 数组中的位置
        wp.push_back(i);
    } else {
        ll fcur = find(cur);
        if (fcur < A[i]) {
            cout << "NO\n";
            return;
        }
        // 之所以要 merge A[i] 和 A[i-1]，是因为 A[i] 是一个空，也不要填充 b 了。
        merge(A[i], A[i] - 1);
        for (ll j = fcur; j > A[i]; --j) {
            merge(j, j - 1);
            if (wp.empty()) {
                cout << "NO\n";
                return;
            }
            B[wp.back()] = j;
            wp.pop_back();
        }
        cur = A[i];
        B[i] = mod;
    }
}
while (!wp.empty()) {
    if (!merge(top_b, top_b - 1)) {
        cout << "NO\n";
        return;
    }
    B[wp.back()] = top_b;
    wp.pop_back();
    top_b++;
}
cout << "YES\n";
for (int i=1;i<=N;++i) {
    cout<<B[i]<<" ";
}

AC代码

AC
https://codeforces.com/contest/2207/submission/367198322

心路历程（WA，TLE，MLE……）

对拍拍出来的数据。

1
2
3
4
1
4
4 4 3 1