Codeforces Round #843 (Div. 2)【A - E】

做完 D 还有 15 分钟，E 题没来得及仔细想，其实蛮简单的……

比赛链接：https://codeforces.com/contest/1775

A2. Gardener and the Capybaras (hard version)

题解

如果中间有 a ，可以单取一个 a 将 $b$ 构造为最小串，否则取所有 b 将 $b$ 构造为最大串。

代码

#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        string s;
        cin >> s;

        int m = s.size();

        int pos = -1;
        for (int i = 1; i < m - 1; i++) {
            if (s[i] == 'a') {
                pos = i;
                break;
            }
        }

        if (pos == -1) {
            cout << s[0] << ' ';
            cout << s.substr(1, m - 2) << ' ';
            cout << s[m - 1] << "\n";
        } else {
            cout << s.substr(0, pos) << ' ';
            cout << 'a' << ' ';
            cout << s.substr(pos + 1) << "\n";
        }
    }

    return 0;
}

B. Gardener and the Array

题解

如果存在某两个序列满足条件，那么向这两个序列同时添加某个数仍满足条件，最终可以添加至两个序列一个为整个数组，一个为整个数组去掉一个数。

所以只需判断去掉某个数后是否不影响整个数组的 | 值即可。

代码

#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> p(n);
        map<int, int> mp;
        for (int i = 0; i < n; i++) {
            int k;
            cin >> k;
            p[i].resize(k);
            for (int j = 0; j < k; j++) {
                cin >> p[i][j];
                mp[p[i][j]] += 1;
            }
        }

        bool ok = false;
        for (int i = 0; i < n; i++) {
            bool no_influence = true;
            for (auto x : p[i]) {
                if (mp[x] == 1) {
                    no_influence = false;
                }
            }
            if (no_influence) {
                ok = true;
            }
        }
        cout << (ok ? "Yes" : "No") << "\n";
    }

    return 0;
}

C. Interesting Sequence

题解

由于是 & 操作，所以 $x$ 中的 $1$ 是 $n$ 中的子集， $x \le n$ 。

当 $n$ 与 $x$ 第一个不同的位，该位为 $^1 _0$ ，为了置 $0$ ， $n$ 必须 & 上一个该位为 $0$ 的数，同时这个数又必须大于 $n$ ，所以该位前的某个 $0$ 位需要置 $1$ ，置 $1$ 的这位后面不能有 $1$ ，因为一定会取到置 $1$ 这位后面全为 $0$ 的某个值，所以第一个不同的位前一位及后面所有位必须是 $0$ ；

设在第 $i$ 位 $n$ 与 $x$ 不同， $m$ 即 $(n\ |\ (1 << (i + 1)))\ \&\ (\sim((1 << (i + 1)) - 1))$ 。

代码

#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        long long n, x;
        cin >> n >> x;

        if ((n & x) != x) {
            cout << -1 << "\n";
        } else if (n == x) {
            cout << n << "\n";
        } else {
            bool ok = true;
            bitset<64> bit_n(n), bit_x(x);
            for (int i = 63; i >= 0; i--) {
                if (bit_n[i] == 1 and bit_x[i] == 0) {
                    if (bit_n[i + 1] == 1) {
                        ok = false;
                    }
                    if ((bit_x & bitset<64>((1LL << i) - 1)).any()) {
                        ok = false;
                    }
                    if (ok) {
                        cout << ((bit_n | bitset<64>(1LL << (i + 1))) & bitset<64>(~((1LL << (i + 1)) - 1))).to_ullong() << "\n";
                    } else {
                        cout << -1 << "\n";
                    }
                    break;
                }
            }
        }
    }

    return 0;
}

D. Friendly Spiders

题解

对每个数内的素因子进行 BFS 。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 3e5 + 10;

vector<int> p(N);

void Init() {
    iota(p.begin(), p.end(), 0);
    for (int i = 2; i < N; i++) {
        if (p[i] != i) {
            continue;
        }
        for (int j = i; j < N; j += i) {
            p[j] = i;
        }
    }
}

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

    Init();

    int n;
    cin >> n;

    vector<int> a(n);
    vector<vector<int>> div(N);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int x = a[i];
        while (x != 1) {
            int y = p[x];
            while (x % y == 0) {
                x /= y;
            }
            div[y].push_back(i);
        }
    }

    int s, t;
    cin >> s >> t;
    --s, --t;

    vector<int> dis(n, 1e9), prv(n, -1);
    vector<bool> vis(N);

    queue<int> pque;
    
    pque.push(s);
    dis[s] = 0;

    while (not pque.empty()) {
        auto u = pque.front();
        pque.pop();

        if (u == t) {
            break;
        }

        int x = a[u];
        while (x != 1) {
            int y = p[x];
            while (x % y == 0) {
                x /= y;
            }
            if (vis[y]) {
                continue;
            }
            vis[y] = true;
            for (auto v : div[y]) {
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    prv[v] = u;
                    pque.push(v);
                }
            }
        }
    }

    if (dis[t] == 1e9) {
        cout << -1 << "\n";
        return 0;
    }

    vector<int> path;
    while (t != s) {
        path.push_back(t);
        t = prv[t];
    }
    path.push_back(s);
    reverse(path.begin(), path.end());

    cout << path.size() << "\n";
    for (auto x : path) {
        cout << x + 1 << ' ';
    }

    return 0;
}

E. The Human Equation

题解

对于当前的数 $x$ ：

• 如果 $x \gt 0$ ，则需要执行 $x$ 次 - 操作，如果之前有最后执行 + 操作的序列，可以将 $x$ 添加至这些序列的末尾，同时最后执行 - 操作的序列个数增加 $x$ 个
• 如果 $x \lt 0$ ，则需要执行 $x$ 次 + 操作，如果之前有最后执行 - 操作的序列，可以将 $x$ 添加至这些序列的末尾，同时最后执行 + 操作的序列个数增加 $x$ 个

所以维护最后执行 加/减 操作的序列个数，从前往后遍历一遍数组，最终答案即两个序列的个数之和。

代码

#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

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

        long long add = 0, sub = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                continue;
            }
            if (a[i] > 0) {
                add -= min(add, a[i]);
                sub += a[i];
            } else {
                sub -= min(sub, -a[i]);
                add += -a[i];
            }
        }
        cout << add + sub << "\n";
    }

    return 0;
}