Educational Codeforces Round#155 (Div. 2)

Shiroha白羽的博客

Shiroha · 2023-10-02 · via Shiroha白羽的博客

A. Rigged!

大致题意

有 $n$ 个人，每个人都可以举起最高一定重量的哑铃 $b_i$ 次，而每个人举的哑铃是同一个，最终举起次数最多的人获胜，裁判希望第一个人获胜，问应该陪多少的哑铃，或者不可能

思路

简单题，只要没有人既能举起比第一个人更重的同时，能够举起更多次就行，重量很直接选第一个人能举起的上线就行

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, s, e;
        cin >> n >> s >> e;
        bool flag = true;
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            if (u >= s && v >= e) {
                flag = false;
            }
        }        cout << (flag ? s : -1) << endl;
    }
}

B. Chips on the Board

大致题意

有一个棋盘，每个位置的价值是对应的横坐标价格和纵坐标价格相加。现在可以往棋盘上放棋子，费用上位置的价值。放上数个后，使得棋盘上每一个位置，其所在的行或者所在的列中至少存在一个棋子，问最小费用

思路

简单题，容易得出，必定每一行或者每一列都有一个棋子，这是最低的要求，然后就很简单了

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        int ma = LONG_LONG_MAX, mb = LONG_LONG_MAX, sa = 0, sb = 0, tmp;
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            ma = min(ma, tmp);
            sa += tmp;
        }
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            mb = min(mb, tmp);
            sb += tmp;
        }
        cout << min(sa + n * mb, sb + n * ma) << endl;
    }
}

C. Make it Alternating

大致题意

有一个 $01$ 串，允许按照一定顺序删除掉一些字符，使得整个字符串没有连续的相同字符，问有多少种删除方式

思路

拿一个例子进行考虑，比如 $11000$，明显，我们需要在前两个中删除一个，在后面三个中删除两个，然后这三个值的顺序任意都可，所以就是

$$ \begin{pmatrix} 2 \\ 1 \end{pmatrix} \times \begin{pmatrix} 3 \\ 2 \end{pmatrix} \times A^3_3 $$

看懂了公式就能算出来了

AC code

#define int long longvoid solve() {
    const int mod = 998244353;
    vector<int> p(2e5 + 10);
    p[0] = p[1] = 1;
    for (int i = 2; i < p.size(); ++i) p[i] = (i * p[i - 1]) % mod;
    int _;
    cin >> _;
    string str;
    for (int ts = 0; ts < _; ++ts) {
        str.reserve(2e5+10);
        cin >> str;
        int ans = 1, tot = 0, cnt = 1;
        for (int i = 1; i < str.size(); ++i) {
            if (str[i] != str[i - 1]) {
                ans = (ans * cnt) % mod;
                cnt = 1;
            } else {
                cnt++;
                tot++;
            }
        }
        ans = (ans * cnt) % mod;
        ans = (ans * p[tot]) % mod;
        cout << tot << ' ' << ans << endl;
    }
}

D. Sum of XOR Functions

大致题意

有一个数组，需要求算 $\sum^n_{l=1}\sum^n_{r=l} f(l,r) \times (r-l+1)$，其中 $f(l,r)$ 表示 $[l, r]$ 区间的异或和

思路

首先要明确异或和的本质，对于任意一个比特位而言，若所有值中此比特位为 1 的数量为奇数，则最终为奇数。所以需要统计任意区间内的某个比特位的奇偶情况，故可以先做一次前缀异或和，这样得到的就是累积的奇偶情况了。

对于一个区间，如果其左区间（前一个）的前缀异或和的某个位的结果是 1（奇数），而右区间则为 0（偶数），则说明这个区间内这个比特位出现奇数次，那么就可以计算其贡献，为 $(r-l+1) \times 2^p)$，拆解一下公式可以得到 $r \times 2^p - (l-1) \times 2^p$。

对于每一个比特位，我们考虑遍历所有可能的右区间，对于每一个右区间，要找出左边出现了几次和右区间的前缀和的比特位结果不同的次数，那么就是这个 $r \times 2^p$ 部分的价值出现的次数，同时减去左边所有不同的 $(l-1) \times 2^p$ 的价值，就可以得到当前位置作为右区间的时候，能够带来的价值。而计算后的 $r \times 2^p$ 部分，恰好是其作为左区间的时候的 $(l-1) \times 2^p$ 的价值。

所以只需要遍历一遍，记录左边出现了几次 $0$ 和几次 $1$，同时对于 $0$ 而言，产生了多少价值，同理对 $1$ 也一样，然后作为下一个节点的计算输入

AC code

#define int long longvoid solve() {
    int n;
    cin >> n;
    vector<int> data(n);
    for (auto &i: data) cin >> i;
    for (int i = 1; i < n; ++i) data[i] = data[i] ^ data[i - 1];
    const int mod = 998244353;
    int ans = 0;
    for (int e = 0; e <= 32; ++e) {
        int s1 = 0, c1 = 0, s0 = 0, c0 = 1;
        for (int i = 0; i < n; ++i) {
            int rp = ((i + 1) * (1LL << e)) % mod;
            if (data[i] & (1LL << e)) {
                ans = (ans + rp * c0 - s0) % mod;
                s1 = (s1 + rp) % mod;
                c1++;
            } else {
                ans = (ans + rp * c1 - s1) % mod;
                s0 = (s0 + rp) % mod;
                c0++;
            }
        }
    }
    cout << ans << endl;
}

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

推荐订阅源

Shiroha白羽的博客

A. Rigged!

大致题意

思路

AC code

B. Chips on the Board

大致题意

思路

AC code

C. Make it Alternating

大致题意

思路

AC code

D. Sum of XOR Functions

大致题意

思路

AC code