洛谷 P9570 「NnOI R2-T2」Glaciaxion

简要题意

给定一个数 和 表示有从 ~ 的正整数和 次操作。每次操作给出一个字母 N 或 Y，如果给出 N 说明有一个数字第一次被选中并输出，如果给出 Y 就要从刚刚选出来的数里再选一个输出出来。现在要求若干输出里字典序最小的序列，如果无解输出 No solution。

策略分析

无解情况

  • 当给出 N 的次数超过 时不合法，因为每个数第一次出现的次数总和至多为 。
  • 当还没有给出 N 就给出 Y 时不合法，因为 Y 不能选出以前没有选出来的数。
  • 或 等于 的时候不合法

构造

下面的分析基于所有合法条件。我们要求最后输出序列字典序最小，所以我们考虑建立一个从 开始的指针，当出现 N 时输出指针，然后指针移动到下一个数。给出 Y 前一定给出了 N，而第一次给出 N 时我们选出的数一定是 ，因为它的字典序最小。而既然已经选出来了，后面每一次 Y 我们都要在已经选出的数里选一个最小的，那么我们选出来的数必然是 。所以我们只需要在输入 N 的时候输出递增的那个指针并将其自增，输入 Y 的时候输出 就可以了。

参考代码

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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

namespace SHAWN {
    const int N = 1e6 + 7;
    int n, m, idx, ncnt, ycnt;
    // ncnt用来记录N的数量，ycnt记录Y的数量
    string s;
    vector<int> ans;// 用来记录答案
    int work()
    {
        cin >> n >> m;
        cin >> s;
        if (!n || !m) { cout << "No solution\n"; return 0; }
        // n或m为0无解
        for (int i = 0; i < m; ++i) {
            if (s[i] == 'N') {
                ++idx;// 指针自增
                ++ncnt;
                ans.emplace_back(idx);// 将指针放入答案序列
            }
            else if (s[i] == 'Y') {
                ++ycnt;
                ans.emplace_back(1);// 输入Y一定输出1
            }
            if (ncnt == 0 && ycnt) { cout << "No solution\n"; return 0; }
            // 还没输入N就输入了Y无解
        }
        if (ncnt > n) { cout << "No solution\n"; return 0; }
        // 输入N的数量大于n无解
        for (auto it : ans) { cout << it << ' '; }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}