Codeforces 979 div2[A~D] 个人题解

A - A Gift From Orangutan

原题链接

思路分析

贪心

第一个位置无论是几都没有贡献

为了让max(a) 的贡献尽可能大，min(a) 的贡献尽可能小

我们构造 a[0] = max(a), a[1] = min(a)

这样我们的答案就是 (max(a) - min(a)) * (n - 1)

时间复杂度：O(N)

AC代码

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

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

    int ma = 0, mi = inf32;


    for (int i = 0; i < n; ++ i) {
        int a;
        std::cin >> a;
        ma = std::max(ma, a);
        mi = std::min(mi, a);
    }

    std::cout << (ma - mi) * (n - 1) << '\n';
}

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

#ifdef DEBUG
    int cur = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - cur << '\n';
#endif
    return 0;
}

B - Minimise Oneness

原题链接

思路分析

构造

记0的个数为c0

那么：
f = 2^c0 - 1

g = 2^n-1 - (2^c0-1) = 2^n - 2^c0

f - g = 2^(c0 + 1) - 2^n + 1

f - g 最小时，c0 = n - 1
那么构造 s = string(n - 1, 0) + "1\n" 即可

时间复杂度：O(N)

AC代码

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

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

    if (n == 1) {
        std::cout << "0\n";
        return;
    }

    std::cout << std::string(n - 1, '0') + "1\n";
}

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

#ifdef DEBUG
    int cur = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - cur << '\n';
#endif
    return 0;
}

C - A TRUE Battle

原题链接

思路分析

贪心

由于 题目要求 or 的优先级低于 and，那么我们发现如果开头或结尾为1，我们在开头的后面或者结尾的前面放一个or，最后结果都是1

如果有连续的2个1，那么 Alice 在 第一个1左边先手放or，无论bob 在 2个1中间还是右边放and，Alice 总能在剩下那个位置放or，来使得结果为1

其他情况，二者都最优操作就是 交替放 or、and，每次and 都会消除掉 or 构造的1

因此只有两种情况能赢

时间复杂度：O(N)

AC代码

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

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

    if (s[0] == '1' || s.back() == '1') {
        std::cout << "YES\n";
        return;
    }

    for (int i = 0; i + 1 < n; ++ i) {
        if (s[i] == '1' && s[i + 1] == '1') {
            std::cout << "YES\n";
            return;
        }
    }

    std::cout << "NO\n";
}

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

#ifdef DEBUG
    int cur = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - cur << '\n';
#endif
    return 0;
}

D - QED's Favorite Permutation

原题链接

思路分析

差分+模拟

对于一个逆序对(i, j)，我们消除的办法就是把 i 一路移动到 j

途中要在 [i, j) 上进行右移操作

由于这是一个排列，我们记 x 出现位置为pos[x]，对于 每一个 p[i] != i 的 i

显然要进行 min(pos[i], i) -> max(pos[i], i) 的 交换 

那么 [min(pos[i], i)， max(pos[i], i)) 要进行右移操作，我们可以用差分数组diff维护 每个位置进行右移操作的次数

对于i，如果 diff[i] > 0 并且 s[i] = 'L' s[i + 1] = 'R'，那么 i 是一个非法位置，因为它不能右移，也不能被右边的位置带着右移

那么对于 q 次操作我们模拟维护 非法位置的数目 cnt 即可

如果 cnt = 0, 就是 YES

否则为 NO

时间复杂度：O(N)

AC代码

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> p(n), pos(n);
    for (int i = 0; i < n; ++ i) {
        std::cin >> p[i];
        pos[-- p[i]] = i;
    }

    std::vector<int> diff(n);

    for (int i = 0; i < n; ++ i) {
        ++ diff[std::min(pos[i], i)];
        -- diff[std::max(pos[i], i)];
    }

    for (int i = 1; i < n; ++ i) {
        diff[i] += diff[i - 1];
    }

    std::vector<bool> bad(n);
    int cnt = 0;
    auto insert = [&](int i) {
        if (bad[i]) {
            return;
        }
        bad[i] = true;
        ++ cnt;
    };
    auto erase = [&](int i) {
        if (!bad[i]) {
            return;
        }
        bad[i] = false;
        -- cnt;
    };

    std::string s;
    std::cin >> s;

    for (int i = 0; i + 1 < n; ++ i) {
        if (diff[i] && s.substr(i, 2) == "LR") {
            insert(i);
        }
    }

    for (int i = 0; i < q; ++ i) {
        int x; 
        std::cin >> x;
        -- x;

        if (s[x] == 'L') {
            s[x] = 'R';
        } else {
            s[x] = 'L';
        }

        if (diff[x] && s.substr(x, 2) == "LR") {
            insert(x);
        } else {
            erase(x);
        }

        if (diff[x - 1] && s.substr(x - 1, 2) == "LR") {
            insert(x - 1);
        } else {
            erase(x - 1);
        }

        if (cnt == 0) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

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

#ifdef DEBUG
    int cur = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - cur << '\n';
#endif
    return 0;
}