Educational Codeforces Round 98 (Rated for Div. 2) A-E 题解

A. Robot Program

题意

给定 $x,y$ ，一个机器人要从$(0,0)$点走到$(x,y)$点，每次操作能上下左右移动或者不动，且每次操作不能和上次操作相同，问最小操作次数。

思路

面 向 样 例 编 程

其实就是每次向下或向右走，先交替，若到底还需要向右走，则一开始就向右走，之后每走一秒停一秒。反之亦然，不影响答案。

答案为$x+y+max(0,abs(x-y)-1)$

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;
        cout << x + y + max(0, abs(x - y) - 1) << '\n';
    }
    return 0;
}

B. Toy Blocks

题意

有 $n（2\le n\le 10^5）$ 堆玩具，选取其中任意一堆，把这一堆所有（原题面就是加粗的）玩具都任意分配到其它堆上。

现给你每一堆分别有多少玩具，要达成的条件是，选取任意一堆，都能通过上述的操作，使得剩下的 $n-1$ 堆相等。问你最少加多少个玩具使条件成立。

思路

一开始漏了加粗的关键字，想半天搞不出来导致这场掉分了淦。

考虑任意一堆分配完都要使剩下的堆相等。且一定要达到原本最高的那一堆的高度。

即$ans=max(\lceil \frac{sum}{n-1}\rceil ,mx)\ast (n-1)$

$mx$表示最高那一堆的高度。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N];

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        ll sum = 0;
        for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
        sort(a + 1, a + 1 + n);
        ll ans = 0;
        ll need = max((sum + n - 2) / (n - 1) * (n - 1), a[n] * (n - 1));
        cout << need - sum << '\n';
    }
    return 0;
}

C. Two Brackets

题意

括 号 匹 配

不会有人不会括号匹配吧（

题意是给一个字符串，仅由括号组成，每次可以移除一对匹配上的括号，问你能移除多少对。

这不就是求有多少对括号匹配吗。

思路

可以直接堆栈模拟，当然懒狗直接用map了，其实两个cnt就解决了

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        map<int, int> mp;
        int ans = 0;
        string s;
        cin >> s;
        for (char ch : s) {
            if (ch == '(') {
                mp[1]++;
            } else if (ch == '[') {
                mp[2]++;
            } else if (ch == ')') {
                if (mp[1]) {
                    ans++;
                    mp[1]--;
                }
            } else if (ch == ']') {
                if (mp[2]) {
                    ans++;
                    mp[2]--;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

吐槽

这场的梯度真的离谱，C过的比B多贼多，到E直接难度起飞。

D. Radio Towers

题意

在$[1,n]$每个城镇都有 $\frac{1}{2}$ 的概率安装天线，你可以指定天线的辐射范围，至少会辐射天线所在的位置，左右对称（如天线2可以辐射$[2,2]$或$[1,3]$），问，安装的天线能使所有信号不相交且恰好覆盖$[1,n]$的概率是多少。$mod998244353$

思路

把整个看成一个01状态，每个状态的概率都是$\frac{1}{2^n}$

其实就是把 $n$ 给划分成任意个奇数的方案数。

记方案数为 $f$ , $f(i)$是所有$f(i-1),f(i-3)\dots$ 的和，因为只能划分成奇数。

那么就是当前为奇数，则加上偶数的和，反之亦然。

整个过程其实就是个斐波那契。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 998244353;

ll qpow(ll a, ll b) {
    ll ret = 1;
    a %= mod;
    while (b) {
        if (b & 1) {
            ret = ret * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

const int N = 2e5 + 10;

int main() {
    int n;
    cin >> n;
    ll tmp = qpow(qpow(2, n), mod - 2);
    ll ans = 0;
    ll sum1 = 1, sum2 = 0;
    for (int i = 2; i <= n; i++) {
        if (i % 2) {
            sum1 += sum2;
            sum1 %= mod;
        } else {
            sum2 += sum1;
            sum2 %= mod;
        }
    }
    if (n % 2) {
        ans = tmp * sum1 % mod;
    } else {
        ans = tmp * sum2 % mod;
    }
    cout << ans;
    return 0;
}

E. Two Editorials

题意

现有 $n$ 道题，$m$ 个听题人，每个人想听 $[l,r]$ 区间内的题的题解。

两个讲题人，每个人会讲 $k$ 题（必须连续），对于每个听题人，他会选择重合题数多的那个讲题人去听。

对于每个人，他的满意度就是他听到的题数。

问讲题人如何选题，使满意度总和最大，输出最大满意度总和。

思路

考虑出题人区间和听题人区间的重合度和他们中间点位置的关系。

出题人区间中点从左到右移动。一开始，它逐渐接近听题人区间的中点，重合度上升，一直到两个中点重合过后，重合度开始下降。从这里我们可以看出，两个区间中点越近，重合度就越高。

那么我们根据中点排序所有听题人的区间，左边部分听第一个人，右边部分听第二个人。先枚举第一个人的讲题区间，并枚举听题人数，算出贡献。然后枚举第二个人的讲题区间，枚举听题人数，对应上刚才枚举保存的第一个人的贡献，加起来更新答案即可。

代码

#include <bits/stdc++.h>

using namespace std;

struct seg {
    int l, r;

    bool operator<(const seg &ano) const {
        return l + r < ano.l + ano.r;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<seg> vec(m);
    for (int i = 0; i < m; ++i) {
        cin >> vec[i].l >> vec[i].r;
    }
    sort(vec.begin(), vec.end());
    vector<int> sum(m + 1);
    for (int i = 0; i < n - k + 1; ++i) {
        int now = 0;
        for (int j = m - 1; j >= 0; --j) {
            now += max(0, min(i + k, vec[j].r) - max(vec[j].l, i + 1) + 1);
            sum[j] = max(sum[j], now);
        }
    }
    int ans = 0;
    for (int i = 0; i < n - k + 1; ++i) {
        int now = 0;
        for (int j = 0; j < m; ++j) {
            now += max(0, min(i + k, vec[j].r) - max(vec[j].l, i + 1) + 1);
            ans = max(ans, now + sum[j + 1]);
        }
    }
    cout << ans;
    return 0;
}

By Boboge.

本文地址：https://blog.csdn.net/avgstuBoboge/article/details/110132463