现代汽车CodeFaster挑战赛（初赛）官方题解

出题人：世界第一可爱的嘤嘤嘤。

题解：WIDA 、bandiaozi 。

祖玛游戏

【诈骗+模拟】

注意到题目中“有一次机会调整数组中球的顺序”，这里没有做出更多限定，所以可以随便排！至此，只需要统计每种颜色的球是否小于 即可。注意到取值范围较大，使用哈希表处理会非常方便。复杂度 。

#include <bits/stdc++.h>

using ll = long long;

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

    int n;
    std::cin >> n;
    std::map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        cnt[x]++;
    }

    int ans = 0;
    for (auto [x, c] : cnt) {
        if (c < 3) {
            ans += 3 - c;
        }
    }

    std::cout << ans << "\n";

    return 0;
}

小红的彩带

【模拟+数据结构】

按照题意直接模拟即可。注意由于取值范围较大，需要使用堆、哈希等数据结构辅助处理。复杂度 。

#include <bits/stdc++.h>

using ll = long long;

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

    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }

    int left = 0, right = 0;
    while (m--) {
        char ch;
        int len;
        std::cin >> ch >> len;

        std::set<int> st;
        if (ch == 'L') {
            for (int i = left; i < left + len; i++) {
                st.insert(a[i]);
            }
            left += len;
        } else {
            for (int i = n - right - len; i < n - right; i++) {
                st.insert(a[i]);
            }
            right += len;
        }
        std::cout << st.size() << "\n";
    }

    return 0;
}

小红的数组构造（easy）

【位运算+构造+思维】

由于是按位或，故 显然输出 ，随后将 后拆位处理，准备补足直到 。具体而言，从大到小检查每一个为 的位置，遍历全部的 ，如果 或上这一位依旧不超过 ，则如此操作。复杂度 。

#include <bits/stdc++.h>

using ll = long long;

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

    int n, x, y;
    std::cin >> n >> x >> y;

    if (y > x) {
        std::cout << "-1\n";
        return 0;
    }

    std::vector<int> a(n);
    a[0] = y;
    x -= y;
    for (int j = 20; j >= 0 && x; j--) {
        for (int i = 1; i < n && x; i++) {
            if (x >= (1 << j) && (y >> j & 1)) {
                a[i] |= 1 << j;
                x -= 1 << j;
            }
        }
    }

    if (x) {
        std::cout << "-1\n";
    } else {
        for (int i = 0; i < n; i++) {
            std::cout << a[i] << " \n"[i == n - 1];
        }
    }

    return 0;
}

小红的特殊数组2.0

【组合数学】

不妨设子序列中 出现一次， 出现两次。枚举每一个可能的 ，根据组合数学知识，答案即为 ，暴力计算复杂度显然无法通过，但是我们有二项式定理 ！通过容斥定律得到上式等价于 。

记得乘上 的数量 。复杂度 。

需要注意取模，标程中使用自定义封装的自动取模类 Z 实现。

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

    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::map<int, int> cnt;
    for (auto &x : a) {
        std::cin >> x;
        cnt[x]++;
    }

    Z ans = 0;
    for (auto [k, v] : cnt) {
        if (v >= 2) {
            ans += (power<Z>(2, v) - 1 - v) * (n - v);
            std::cout << power<Z>(2, v) << " " << 1 + v << "\n";
        }
    }

    std::cout << ans << "\n";

    return 0;
}