Div.2 Round 882 总结

这一场整体下来感觉难度适中，对位运算性质的考查较多，个人感觉 A、B、C 比较简单。

A 「The Man who became a God」

我们不妨假设起初所有村庄都是一个整体，那么 suspicion 的值就是所有相邻村庄的怀疑值差值的绝对值总和，Kars 对村庄进行 \(k - 1\) 次分割将其划分为 \(k\) 个部分，假设分割村庄 \((i, i + 1)\) ，那 suspicion 就在原来的基础上减去一个 \(|a_i - a_{i +1}|\) ，要得到最小的 suspicion ，换言之我们只需要找到最大的 \(k - 1\) 个相邻元素差值的绝对值即可。

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

空间复杂度：\(O(n)\)

#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>

#define MAX_N 105

int arr[MAX_N];
int diff[MAX_N];

void solve() {
    int n, k;
    std::cin >> n >> k;
    for (int i = 0; i < n; i++) std::cin >> arr[i];
    for (int i = 1; i < n; i++) diff[i] = abs(arr[i] - arr[i - 1]);
    std::sort(diff + 1, diff + n, std::greater<int>());

    int s1 = std::accumulate(diff + 1, diff + n, 0);
    int s2 = std::accumulate(diff + 1, diff + k, 0);

    std::cout << s1 - s2 << '\n';
}

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

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

B 「Hamon Odyssey」

注意到，对于正整数 \(x\)、\(y\) 而言，一定有 \(x + y \geq x\ \&\ y\)，\((x, y) = (0, 0)\) 时取等，因此如果合并后的有两个相邻的数不全为 0，则可以继续合并使结果严格减小。

综上所述，我们可以得到：

若所有数的数位与不为 0，那将所有数字合并为一个整体一定最小，且只能将所有数合并为一个整体时取最小值。
若所有数的数位与为 0，则考虑将数组分割为尽可能多的片段，每个片段的所有数的数位与为 0。

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

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

#include <iostream>

void solve() {
    int n;
    std::cin >> n;
    int res = 0;
    for (int i = 0, s = 0xffffffff, x; i < n; i++) {
        std::cin >> x;
        s &= x;
        if (!s) {
            s = 0xffffffff;
            res++;
        }
    }

    std::cout << (res == 0 ? 1 : res) << '\n';
}

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

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

C 「Vampiric Powers, anyone?」

不难证明每一次操作得到的数都是某段连续序列的异或值。因此本题只需要找到最大的连续异或值即可。暴力求解显然会超时，所以最开始我想的是怎么用 DP，后面发现 \((0 \leq a_i < 2 ^ 8)\)，也就是说所有数字只有 256 种取值，因此我们使用一个哈希表维护前缀异或即可。

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

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

#include <iostream>
#include <algorithm>
#include <unordered_set>

void solve() {
    int n;
    std::cin >> n;
    std::unordered_set<int> s;
    s.insert(0);
    for (int i = 0, r = 0, x; i < n; i++) {
        std::cin >> x;
        r ^= x;
        s.insert(r);
    }
    int res = 0;
    for (int x : s) {
        for (int y : s) {
            res = std::max(res, x ^ y);
        }
    }

    std::cout << res << '\n';
}

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

    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

D 「Professor Higashikata」

贪心策略，我们假设 \(f(i)\) 表示 \(t(s)[i]\) 对应原字符串的下标，那么最右策略就是最大化 \(k\) 使得 \(s_{f(0)} = 1、s_{f(1)} = 1, ..., s_{f(k)} = 1\)。事实上，若存在 \(i\) 和 \(j\) 满足 \(f(i) = f(j) \ (i < j)\) ，则可以不考虑 \(f(j)\) ，因为 \(s_{f(i)}\) 和 \(s_{f(j)}\) 是一样的，且下标 \(i\) 更靠前，若 \(s_{f(i)} = 1\) 则必然有 \(s_{f(j)} = 1\) ，所以我们只要求每个下标第一次出现的时间顺序即可，然后将其按照从早到晚进行排序，以题目的第二个输入为例：

根据题目依次输入的区间，每个下标的出现时间顺序为 5, 6, 2, 3, 7, 8。

假设原字符串为 \(str\)，接下来我们只需要最大化 \(pat = [str[5]、str[6]、str[2]、str[3]、str[7]、str[8]]\) 的字典序，即最大化其前缀 1 的数量，其初始状态为 100010，第一次翻转了下标为 3 的字符，\(str\) 更新为 10111010，\(pat\) 更新为 100110，只需要分别将 \(str[1]\)、\(str[4]\) 和 \(str[6]\)、\(str[2]\) 交换位置即可使得 \(pat\) 字典序最大，共需要两次操作，不难发现，每次的最小操作数量都等于 \(pat\) 在区间 \([1, min\{num\_of\_ones,\ pat.size\}]\)（\(num\_of\_ones\) 表示 \(str\) 中有多少个 1）中 0 的个数。

综上所述，完成本题需要两个步骤：

求出每个字符串下标的出现次序。
根据出现次序构造新字符串 \(pat\)，每一轮更新后区间 \([1, min\{num\_of\_ones, pat.size\}]\) 中 0 的个数即最小操作数。这一步涉及单点修改和区间查询，可以考虑使用线段树。

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

空间复杂度：\(O(n + m)\)

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

class SegTree {
private:
    int n;
    std::vector<int> tree;

    void update(int idx, int val, int node, int start, int end) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int leftNode = 2 * node + 1, rightNode = 2 * node + 2;
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(idx, val, leftNode, start, mid);
        }
        else {
            update(idx, val, rightNode, mid + 1, end);
        }

        tree[node] = tree[leftNode] + tree[rightNode];
    }

    int query(int left, int right, int node, int start, int end) {
        if (start > right || end < left) return 0;
        if (start >= left && end <= right) return tree[node];

        int leftNode = 2 * node + 1, rightNode = 2 * node + 2;
        int mid = (start + end) / 2;

        return query(left, right, leftNode, start, mid) + query(left, right, rightNode, mid + 1, end);
    }

public:
    SegTree(int _n): n(_n), tree(4 * _n) {}

    void update(int idx, int val) {
        update(idx, val, 0, 0, n - 1);
    }

    int query(int left, int right) {
        
        return query(left, right, 0, 0, n - 1);
    }
};

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::string str;
    std::cin >> str;
    std::vector<int> pat; // 记录在区间内出现过的数，按照第一次出现的时间排序
    std::vector<int> pos(n, -1); // 原字符串在 pat 串的索引，-1 表示不存在
    std::vector<std::pair<int, int>> ranges;
    for (int i = 0, l, r; i < m; i++) {
        std::cin >> l >> r;
        ranges.push_back(std::make_pair(l - 1, r - 1));
    }
    std::set<int> s;
    for (int i = 0; i < n; i++) s.insert(i); // s 存储没有目前出现过的数字
    for (const auto& r : ranges) {
        auto iter = s.lower_bound(r.first); // *iter >= r.first
        std::vector<int> toErase; // 将要删除的数字
        while (iter != s.end() && *iter <= r.second) {
            toErase.push_back(*iter);
            pat.push_back(*iter);
            pos[*iter] = pat.size() - 1;
            iter++;
        }
        for (int x : toErase) {
            s.erase(x);
        }
    }
    
    int np = pat.size();
    SegTree st(np);
    for (int i = 0; i < np; i++) st.update(i, str[pat[i]] == '1');
    int cntOne = 0; // 1 的数量
    for (char ch : str) cntOne += ch == '1';

    for (int i = 0, p; i < q; i++) {
        std::cin >> p;
        int idx = pos[p - 1]; // 对应的 pat 串下标
        if (str[p - 1] == '1') {
            str[p - 1] = '0';
            cntOne--;
            if (idx != -1) st.update(idx, 0);
        }
        else {
            str[p - 1] = '1';
            cntOne++;
            if (idx != -1) st.update(idx, 1);
        }

        int d = std::min(np, cntOne);
        std::cout << d - st.query(0, d - 1) << '\n';
    }
}

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

    solve();

    return 0;
}

ACM

#Codeforces #Div.2 #贪心算法 #哈希表 #前缀异或 #线段树

Div.2 Round 882 总结

https://goer17.github.io/2023/07/09/Div.2 Round 882 总结/

作者

Captain_Lee

发布于

2023年7月9日

许可协议

深度学习鱼书学习笔记上一篇

哈尔滨避暑记下一篇