Codeforces Round 912 (Div. 2)

Shiroha白羽的博客

Shiroha · 2024-02-11 · via Shiroha白羽的博客

A. Halloumi Boxes

大致题意

有一个数组，每次允许选择其中一段长度不超过 $k$ 的字串进行翻转，问是否可能将其排序好

思路

最有用的翻转就是两个值，那就是冒泡了，所以要么本身有序，要么 $k \geq 2$ 就行了

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        bool sorted = true;
        for (int i = 1; i < n; ++i) if (data[i] < data[i - 1]) sorted = false;
        cout << (sorted || k >= 2 ? "YES" : "NO") << endl;
    }
}

B. StORage room

大致题意

有一个矩阵，其中的每一项 $M_{i,j} = a_i | a_j$，问是否能得到原始数组的其中一种可能

思路

即然是 $M_{i,j} = a_i | a_j$，那么反过来可以得到 $a_i = M_{i,0} & M_{i,1} & M_{i,2} \dots$

这不一定是原始解，但是一定是正确的解。还原后再验证一下矩阵对不对就行了

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<vector<int>> data(n);
        for (auto& i: data) i.resize(n);
        for (auto& i: data) for (auto& j: i) cin >> j;
        vector ans(n, -1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (j != i) ans[i] &= data[i][j];
        bool check = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                if (data[i][j] != (ans[i] | ans[j])) check = false;
            }
        }
        if (!check) cout << "NO" << endl;
        else {
            cout << "YES" << endl;
            for (int i = 0; i < n; ++i) cout << (ans[i] == -1 ? 1 : ans[i]) << " \n"[i == n -1];
        }
    }
}

C. Theofanis’ Nightmare

大致题意

一个数组，其中有负值，将其拆成多个字串，然后按照原始顺序从左往右编号，从 1 开始编号

然后将每个字串内求和，乘上其的编号，最后再相加，问如何拆最大

思路

从最后一个值看，假如其为 $c$，那么如果其独立出去，和不独立出去，和前面的段合并，那么得到的差值就是 $c$，因为 $(n + 1) \times c - (n) \times c$

所以，如果 $c > 0$ 那么这样做是有意义的，反之则应该尽力避免拆

类推可以得到，如果当前值即之后的所有值加起来是 $< 0$，那么不要拆，反之则拆即可

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int sum = 0;
        for (auto& i: data) sum += i;
        int seg = 0, ans = 0;
        for (auto& i: data) {
            if (sum < 0) {
                if (seg == 0) seg = 1;
                ans += seg * i;
            }
            else {
                ++seg;
                ans += seg * i;
            }
            sum -= i;
        }
        cout << ans << endl;
    }
}

D1. Maximum And Queries (easy version)

大致题意

有一个数组，允许每次给其中一个值 $+1$，最多执行 $k$ 次，问最终得到的数组的每一项进行位与运算，问最大值可以是多少

思路

要从位运算上下思路

如果一个值的某个位不是 1，那么如果通过 $+1$ 的方式把它变成 1，带来的后果就是更低位置的都会归零

所以我们需要从高位开始枚举位置，假设把这个位置大家都变成 1，那么就可以带来结果上的增长，但是会需要消耗一定的 $k$

注意一旦消耗过 $k$，那么再试图对这个值进行累加的时候，要把低位都认为是 0 了

AC code

#define int long longvoid solve() {
    int n, q;
    cin >> n >> q;
    vector<int> data(n);
    for (auto& i: data) cin >> i;
    while (q--) {
        int k, ans = 0;
        cin >> k;
        vector flag(n, false);
        for (int i = 62; i >= 0; --i) {
            // try this bit
            int cost = 0;
            const int p = 1LL << i;
            vector tmp(n, false);
            for (int j = 0; j < n; ++j) {
                if (flag[j]) cost += p;
                else {
                    if (data[j] & p) continue;
                    cost += p - data[j] % p;
                    tmp[j] = true;
                }
                if (cost < 0) {
                    cost = k + 1;
                    break;
                }
            }
            if (k >= cost) {
                k -= cost;
                ans += p;
                for (int j = 0; j < n; ++j) flag[j] = tmp[j] | flag[j];
            }
        }
        cout << ans << endl;
    }
}

E. Geo Game

大致题意

有两个人博弈，二维屏幕上有一些点，其中一个固定为起始点，两个人轮流指定下一个点，不可以是之前选中的点，直到所有点都被走到

然后求算路径的欧几里得距离的平方和，问能否保证是偶数或者是奇数

思路

仔细思考就会发现很像是一笔画问题

如果某个点与开始点的欧几里得距离是奇数，我将其归为一类 A，另外的点为另外一类 B。那么显然，同一个类内的点相互走并不会变化结果的奇偶性。
但是不同类的路径就会变化奇偶性。非常巧的是，因为每个点都会被进入一次和出去一次，
所以理论如果要回到开始点，那么最终一定是偶数，因为一旦进入 A 类，就一定要回去 B 类，即每个 A 类的点会产生两条路径，也就是最终没有变化奇偶性

那么我们可以得到，如果 A 类点作为最后一个点，那么路径就是奇数的，否则就是偶数，然后再根据博弈再去模拟即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, sx, sy;
        cin >> n >> sx >> sy;
        set<int> data[2];
        for (int i = 0; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            const int cost = abs(u - sx) + abs(v - sy);
            data[cost % 2].insert(i + 1);
        }        if (data[0].size() >= data[1].size()) {
            // chose first
            cout << "First" << endl;
            for (int i = 0; i < n; ++i) {
                if (data[1].empty()) {
                    auto iter = data[0].begin();
                    cout << *iter << endl;
                    data[0].erase(iter);
                } else {
                    auto iter = data[1].begin();
                    cout << *iter << endl;
                    data[1].erase(iter);
                }
                ++i;
                if (i < n) {
                    // read
                    int tmp;
                    cin >> tmp;
                    data[0].erase(tmp);
                    data[1].erase(tmp);
                }
            }
        } else {
            // chose second
            cout << "Second" << endl;
            for (int i = 0; i < n; ++i) {
                int tmp;
                cin >> tmp;
                data[0].erase(tmp);
                data[1].erase(tmp);
                ++i;
                if (i < n) {
                    if (data[0].empty()) {
                        auto iter = data[1].begin();
                        cout << *iter << endl;
                        data[1].erase(iter);
                    } else {
                        auto iter = data[0].begin();
                        cout << *iter << endl;
                        data[0].erase(iter);
                    }
                }
            }
        }
    }
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Shiroha白羽的博客

A. Halloumi Boxes

大致题意

思路

AC code

B. StORage room

大致题意

思路

AC code

C. Theofanis’ Nightmare

大致题意

思路

AC code

D1. Maximum And Queries (easy version)

大致题意

思路

AC code

E. Geo Game

大致题意

思路

AC code