Codeforces Round 827 (Div. 4)

发表于 2024-05-07 更新于 2024-07-19 分类于题解阅读次数：本文字数： 932 阅读时长 ≈ 3 分钟

The miracle appear in bad luck.

A. Sum

思路：

基础的判断结构

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

void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;

    std::cout << ((a + b == c || b + c == a || a + c == b) ? "YES\n" : "NO\n");
}

B. Increasing

思路：

直接排序，比较相邻位置是否可能相等即可

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

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            std::cout << "NO\n";
            return ;
        }
    }
    std::cout << "YES\n";
}

C. Stripes

思路：

由于题目保证了一定存在，那么我们只需要找到一个可能的一整行全部为R或者一整列都是一个字符B，否则直接输出另外一个字符即可

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

void solve() {
    std::vector<std::string> s(8);
    for (int i = 0; i < 8; i++) {
        std::cin >> s[i];
    }

    for (int i = 0; i < 8; i++) {
        bool ok = true;
        for (auto c : s[i]) {
            if (c != 'R') {
                ok = false;
                break;
            }
        }
        if (ok) {
            std::cout << "R\n";
            return ;
        }
    }
    std::cout << "B\n";
}

D. Coprime

思路：

题目把 \(a_i\) 的范围设置到 \(\le 10^3\)，那么一定是一个 \(hash\) 之类的，我们把每个元素的位置存起来，然后暴力枚举互质的二元组即可
需要注意，一个从前向后，一个从后向前，这个可以使得互质二元组的和近可能的大

时间复杂度：\(O(10^6)\)

constexpr int N = 2E5 + 10;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(N);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> p(N);
    for (int i = 1; i <= n; i++) {
        p[a[i]] = i;
    }

    int ans = -1;
    for (int i = 1000; i >= 1; i--) {
        if (!p[i]) {
            continue ;
        }
        for (int j = 1; j <= 1000; j++) {
            if (p[j] && std::gcd(i, j) == 1) {
                ans = std::max(ans, p[i] + p[j]);
            }
        }
    }
    std::cout << ans << "\n";
}

E. Scuza

思路：

用一个 \(max_i\) 数组维护截止到第 \(i\) 个位置的最大数是多少，然后我们询问的时候直接二分查找下标即可，这样就可以得到

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

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<i64> s(n + 1), max(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        max[i] = std::max(1LL * x, max[i - 1]);
        s[i] = s[i - 1] + x;
    }

    while (q--) {
        i64 x;
        std::cin >> x;

        std::cout << s[std::upper_bound(max.begin() + 1, max.end(), x) - max.begin() - 1] << " ";
    }
    std::cout << "\n";
}

F. Smaller

思路：

我们要找到是否可能让 \(s\) 按照字典序排列小于 \(t\) 的方案，首先字典序的大小怎么判断？
- 要比较两个字符串谁小，我们要逐位比较，当比较完较短的字符串，仍然判断不出来谁大谁小，那么这时，就比较长度，长度大的较大，反之较小
然后，我们可以直接记录将 \(s\) 里的每个字符复制 \(k\) 遍，比较结果串里的首位字符，如果首位字符相等，且其他字符都相等，这时就比较长度即可

时间复杂度：\(O(n \times len(s_i))\)

void solve() {
    int n;
    std::cin >> n;

    char mins = 'a', mint = 'a';
    char maxs = 'a', maxt = 'a';

    i64 A = 1, B = 1;
    for (int i = 0; i < n; i++) {
        int d, k;
        std::string s;
        std::cin >> d >> k >> s;

        for (auto c : s) {
            if (d == 1) {
                mins = std::min(mins, c);
                maxs = std::max(maxs, c);
                A += k;
            } else {
                mint = std::min(mint, c);
                maxt = std::max(maxt, c);
                B += k;
            }
        }
        if (mins < maxt || (mins == maxt && mins == maxs && mint == maxt && A < B)) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

G. Orray

思路：

在 \(10^9\) 以内，也就 \(30\) 位，我们直接把最高位放在最前面，然后排序 \(30\) 次就行，每次更新当前的 \(sum_{or}\)

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

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    i64 p = 0;
    for (int i = 0; i < std::min(n, 30); i++) {
        std::sort(a.begin(), a.begin() + n - i, [&](int i, int j) {
            return (i | p) < (j | p);
        });
        p |= a[n - i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
        std::cout << a[i] << " \n"[i == 0];
    }
}