Codeforces Round #695 (Div. 2)

A. Wizard of Orz

(a[2] = 8)时暂停掉(a[2])，所以答案类似为989012345.....

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
 
 
int t, n;
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        if (n == 1) {
            printf("9");
        } else if (n == 2) {
            printf("98");
        } else if (n == 3) {
            printf("989");
        } else {
            printf("989");
            for (int i = 0; i < n-3; i++) {
                printf("%d", i%10);
            }
        }
        printf("
");
    }
}

B. Hills And Valleys

修改一个数最多会消掉3个峰或谷。怎么消呢？假设有5个数组成峰谷峰或者谷峰谷的情况，那么将最中间的数字修改为与左边或者右边相同可以同时消除这三个。

再考虑谷峰的情况，此时看似可以两个一起消除，但是还得考虑，会不会制造出别的峰或谷，比如1 2 3 1 2 3，若将3修改为1或将1修改为3来消除这个峰谷，会制造另一个峰或者谷。

最后是单峰单谷的情况，此时只能消除一个，不会有其它影响。

WA自闭了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MAXN = 3e5 + 10;

int t, n;
int a[MAXN];

bool check(int x) {
    if (x-1 < 1) return false;
    if (x+1 > n) return false;
    return 1ll*(a[x] - a[x-1]) * (a[x] - a[x+1]) > 0;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += check(i);
        }
        int max_val = 0;
        for (int i = 2; i < n; i++) {
            if (!check(i)) continue;
            int before = check(i) + check(i-1) + check(i+1), after;
            int tmp = a[i];

            a[i] = a[i-1];
            after = check(i) + check(i-1) + check(i+1);
            max_val = max(max_val, before - after);

            a[i] = a[i+1];
            after = check(i) + check(i-1) + check(i+1);
            max_val = max(max_val, before - after);
            a[i] = tmp;
        }

        printf("%d
", ans - max_val);

    }
}

C. Three Bags

可以把某两个袋子的数，借助另一个袋子，统一移动到回一个袋子中产生贡献。

因为对于(a)袋子里的所有数，借助(b)袋子移动到(c)袋子中，或者移回(a)袋子中，只亏损了另一个袋子的最小数的两倍。(b)的数也可能借助a和c的最小值移动。所以(ans1 = sum - 三个袋子中的最小数的较小两个)。

如果(b)袋子中的数总和小于三个袋子中的最小数的较小两个，那我们干脆可以放弃(b)袋子，让它产生负贡献。即(ans2 = sum - 三个袋子数值之和的最小值)。

(ans = max(ans1, ans2))。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e6 + 10;
typedef long long LL;
const int inf = 0x3f3f3f3f;

int n1, n2, n3;
int main() {
    scanf("%d%d%d", &n1, &n2, &n3);
    int x, min1 = inf, min2 = inf, min3 = inf;
    LL sum1 = 0, sum2 = 0, sum3 = 0;
    for (int i = 1; i <= n1; i++) {
        scanf("%d", &x);
        sum1 += x;
        min1 = min(min1, x);
    }
    for (int i = 1; i <= n2; i++) {
        scanf("%d", &x);
        sum2 += x;
        min2 = min(min2, x);
    }
    for (int i = 1; i <= n3; i++) {
        scanf("%d", &x);
        sum3 += x;
        min3 = min(min3, x);
    }

    int val = min1+min2+min3 - max(max(min1, min2), min3);
    LL ans1 = sum1 + sum2 + sum3 - val * 2;
    LL ans2 = sum1 + sum2 + sum3 - min(sum3, min(sum1, sum2)) * 2;
    printf("%lld
", max(ans1, ans2));
}

剩下的题明天补。