Codeforces Round #840 (Div. 2)A~C

我焯，稳定三题居然有时候也这么爽，直接哐哐上分。也不用苦苦坐牢想D了，写完C直接润。

Problem - A - Codeforces

问题解析

把所有的数或运算就能得到mx。

把所有的数与运算就能得到mn。

输出mx-mn即可。

AC代码

int a[N];
void solve()
{
    int mx = 0, mn = 0, n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mx |= a[i];
        if (i == 1)
        {
            mn = a[i];
        }
        else mn &= a[i];
    }
    cout << mx - mn << endl;
}

Problem - B - Codeforces

问题解析

题目是说有n个怪物攻打你，给出这n个怪物的血量和攻击，你每次可以对他们全体造成k点伤害，每次攻击完后，还活着的攻击力最小的怪物会让你的k降低它攻击力的数值，问你有没有机会把怪物全干掉。

对怪物的血量和攻击分别升序排序，用一个变量ans记录下你一共造成的伤害，根据生命值遍历所有的怪兽，如果血量低于ans说明它寄了，把它记录下来。

然后根据攻击力遍历所有的怪兽，如果当前怪兽死了就跳到下一个，选第一个还活着的怪兽，用他的攻击力削减k。

如果怪物全死了就是yes，如果过程中k变成了0就是no。

也不知道开不开longlong会不会有影响，我是开了（指#define int ll）

AC代码

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<PII>v(n), a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i].first;
        v[i].second = i;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    map<int, int>mymap;
    sort(v.begin(), v.end());
    sort(a.begin(), a.end());
    int idx = 0, ans = 0, l = 0;
    while (idx < n && k > 0)
    {
        ans += k;
        while (idx < n && v[idx].first <= ans)
        {
            mymap[v[idx].second] = 1;
            idx++;
        }
        if (idx >= n)
        {
            cout << "YES" << endl;
            return;
        }
        while (l < n && mymap.count(a[l].second))l++;
        if (l < n)
        {
            k -= a[l].first;
        }
    }
    if (idx >= n)cout << "YES" << endl;
    else cout << "NO" << endl;
}

Problem - C - Codeforces

问题解析

题目是说给你一个长度为n的数组，你每次可以选择两个下标i和j，把i到j的全部元素都变成|ai - aj|。操作次数不限，问你能得到的最大数组和是多少。

首先我们知道，操作一次后，i到j的元素会全部相等。
再操作一次后，i到j的元素就会全部变成0了。
此时我们选一个不在i~j范围内的最大值k，那么我们是不是就可以把这一个范围和到最大值k之间的全部数都变成了最大值。

这就是这一道题的突破点了！

我们可以想一下，如果数组的最大值mx在最左边，那么它的右边只要有两个数，就可以把整个数组都变成mx了。mx在最右边的话同理。

如果mx不在最左边或最右边会咋样，比如在正数第二个位置，举个例子：1 5 2 3 1.

我们可以先把最右边的两个数变成0 0，此时数组变成1 5 2 0 0.
这下我们可以把数组变成1 5 5 5 5.
此时我们选择最左边的1和5，把他们也通过两次操作变成0 0，数组就变成了0 0 5 5 5 .
那么最后数组仍然可以变成5 5 5 5 5.

所以可以知道，只要最大值的左边或右边有两个数，那么数组的答案就是：n * mx.

思考一下，发现只要n>3的情况都是满足的，所以：如果n>3，直接输出n * mx即可

当n==2时，我们只要计算操作一次前和操作一次后哪个大就行。

比较麻烦的是n==3的情况（当时写的太激动没想好结果wa了，亏死）

总共可以分为以下8种情况：

一次也不操作，即数组原本的和：a1+a2+a3;
把最右边的两个数都变成左边的数，即：a1*3;
同上还有：a3*3；
选择头尾两个元素进行一次操作，即： abs(a1-a3) * 3;
我们也可以选择最左边的两个元素进行一次操作，即：*abs(a1-a2)2+a3;
同上还有：abs(a2-a3) * 2+a1;
或者我们对最左边的两个元素操作一次后，把最右边的数也变成这个差值，即：*abs(a1-a2)3;
同上还有：abs(a2-a3) * 3;

对于n==3时，我们输出以上8种结果的最大值。

AC代码

int a[N];
void solve()
{
    int n, mx = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    if (n > 3)
    {
        cout << n * mx << endl;
    }
    else if (n == 2)
    {
        cout << max(a[1] + a[2], abs(a[1] - a[2]) * 2) << endl;
    }
    else if (n == 3)
    {
        int sum = 0;
        for (int i = 1; i <= 3; i++)
        {
            sum += a[i];
        }
        sum = max(sum, a[3] + abs(a[1] - a[2]) * 2);
        sum = max(sum, a[1] + abs(a[2] - a[3]) * 2);
        sum = max(sum, abs(a[1] - a[3]) * 3);
        sum = max(sum, abs(a[1] - a[2]) * 3);
        sum = max(sum, abs(a[2] - a[3]) * 3);
        sum = max(sum, a[1] * 3);
        sum = max(sum, a[3] * 3);
        cout << sum << endl;
    }
}