Educational Div.2 Round 151 总结

比赛链接

---

A 「Forbidden Integer」

这个没啥好说的，分类讨论一下就行。

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

空间复杂度：\(O(1)\)

#include <iostream>

void solve() {
    int n, k, x;
    std::cin >> n >> k >> x;
    if (x != 1) {
        std::cout << "YES\n" << n << '\n';
        for (int i = 0; i < n; i++) std::cout << 1 << " \n"[i == n - 1];
        return;
    }
    
    // x == 1
    if (k == 1) {
        std::cout << "NO\n";
        return;
    }
    if (k == 2) {
        if (n & 1) {
            std::cout << "NO\n";
            return;
        }
        else {
            std::cout << "YES\n" << n / 2 << '\n';
            for (int i = 0; i < n; i += 2) {
                std::cout << 2 << " \n"[i == n - 2];
            }
            return;
        }
    }
    // k >= 3
    if (n == 1) {
        std::cout << "NO\n";
        return;
    }
    // n >= 2
    std::cout << "YES\n" << n / 2 << '\n';
    while (n) {
        if (n & 1) {
            n -= 3;
            std::cout << 3 << " \n"[n == 0];
        }
        else {
            n -= 2;
            std::cout << 2 << " \n"[n == 0];
        }
    }
}

int main() {

    int numTest;
    std::cin >> numTest;
    while (numTest--) {
        solve();
    }

    return 0;
}

B 「Come Together」

这个也没啥好说的，只需要看 B、C 和 A 的相对位置然后分类讨论一下即可。

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

空间复杂度：\(O(1)\)

#include <iostream>
#include <cmath>

using i64 = long long;

void solve() {
    int xa, ya, xb, yb, xc, yc;
    std::cin >> xa >> ya >> xb >> yb >> xc >> yc;
    xb -= xa, xc -= xa;
    yb -= ya, yc -= ya;
    int res = 1;
    bool same_x = (i64)xb * xc >= 0;
    bool same_y = (i64)yb * yc >= 0;
    if (same_x) {
        // xb xc 同号
        if (same_y) {
            res += std::min(abs(xb), abs(xc)) + std::min(abs(yb), abs(yc));
        }
        else {
            res += std::min(abs(xb), abs(xc));
        }
    }
    else {
        // xb xc 异号
        if (same_y) {
            res += std::min(abs(yb), abs(yc));
        }
    }

    std::cout << res << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) {
        solve();
    }

    return 0;
}

C 「Strong Password」

考虑贪心策略，每一次从限定条件中选取最晚在 database string 中出现的字符，这样可以尽可能快地消耗掉 database string 的前缀，如果中途出现了后缀中不存在的限定条件内的字符，则说明存在答案，反之说明不存在。

为了记录 database string 所有后缀中字符的出现时间，我们需要一个数组来维护每个后缀所有字符出现的最小索引。

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

空间复杂度：\(O(nm)\)

#include <iostream>
#include <vector>

#define INF 0x7f7f7f7f

void solve() {
    std::string dat;
    std::cin >> dat;

    int n;
    std::cin >> n;
    std::string l, r;
    std::cin >> l >> r;

    int len = dat.size();
    // 记录区间 [i, len - 1] 中每个数出现的最早下标
    std::vector<std::vector<int>> nextIdx(len + 1);
    nextIdx.back() = std::vector<int>(10, INF);
    for (int i = len - 1; i >= 0; i--) {
        nextIdx[i] = nextIdx[i + 1];
        nextIdx[i][dat[i] - '0'] = i;
    }
    
    int p = 0;
    for (int i = 0; i < n; i++) {
        p = *std::max_element(nextIdx[p].begin() + l[i] - '0', nextIdx[p].begin() + r[i] - '0' + 1) + 1; // 找到最晚出现的数字
        if (p >= INF) {
            // 出现无法找到的数字
            std::cout << "YES\n";
            return;
        }
    }
    
    std::cout << "NO\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) {
        solve();
    }

    return 0;
}