Codeforces Round 921 (Div. 2)

发表于 更新于 分类于 阅读次数： 本文字数： 365 阅读时长 ≈ 1 分钟
The best revenge is massive success.

A. We Got Everything Covered!

思路：

  • 直接输出 \(n\) 个连续的 \('a' \sim char('a' + k - 1)\)​ 的字符串即可

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    int n, k;
    std::cin >> n >> k;

    std::string s = "";
    for (int i = 0; i < n; i++) {
        for (char c = 'a'; c < 'a' + k; c++) {
            s += c;
        }
    }
    std::cout << s << "\n";
}

B. A Balanced Problemset?

思路：

  • 找到大于等于 \(n\)​ 的最大下取整的除数的最小因子即可

时间复杂度：\(O(\sqrt x)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int x, n;
    std::cin >> x >> n;

    int ans = 0;
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            if (n <= x / i) {
                ans = std::max(ans, i);
            } 
            if (n <= i) {
                ans = std::max(ans, x / i);
            }
        }
    }
    std::cout << ans << "\n";
}

C. Did We Get Everything Covered?

思路：

  • 序列自动机，首先开一个 \(nxt\) 数组记录当前位置 \(i\) 后面字母 \(j\) 出现的位置，每次跳最大的 \(nxt[i][0 \sim 25]\) ，由于 \(p\) 数组初始化为 \(0\)，那么当 \(nxt[now][j]\) 为 \(0\)​ 就说明跳不动了，输出跳的路径即可。

时间复杂度：\(O(nk+m)\)

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
void solve() {
    int n, k, m;
    std::cin >> n >> k >> m;

    std::string s;
    std::cin >> s;
    s = '&' + s;

    std::vector nxt(m + 1, std::vector<int>(26, 0));
    std::array<int, 26> p {};
    for (int i = m; i >= 0; i--) {
        for (int j = 0; j < k; j++) {
            nxt[i][j] = p[j];
        }
        if (i > 0) p[s[i] - 'a'] = i;
    }

    int now = 0;
    std::string ans;
    for (int i = 1; i <= n; i++) {
        int temp = 0;
        for (int j = 0; j < k; j++) {
            if (!nxt[now][j]) {
                std::cout << "NO\n";
                std::cout << ans << char('a' + j) << std::string(n - i, 'a') << "\n";
                return ;
            }
            temp = std::max(temp, nxt[now][j]);
        }
        now = temp;
        ans.push_back(s[now]);
    }
    std::cout << "YES\n";
}