Codeforces Round #852 (Div. 2)（A~D）

A. Yet Another Promotion

在两天可以买东西，第一天的价格为a，第二天的价格为b，第一天买东西有优惠：买m个送一个。现在要求至少一买n个东西，最少用多少钱。

思路：前面的以m+1为单位，计算那种方式买m+1个用钱少；剩下的单独买即可。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N = 1e5 + 5;
ll t, a, b, n, m;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> t;
    while(t --) {
        std::cin >> a >> b >> n >> m;
        ll cc1 = (m + 1) * b, cc2 = a * m;
        ll res = std::min(cc1, cc2);
        ll cnt = n / (m + 1);
        ll ans = cnt * res;
        ll cc = n % (m + 1);
        std::cout << ans + cc * std::min(a, b) << '\n';
    }
    return 0;
}

B. Fedya and Array

现在有一个数组，局部最大值和局部最小值的定义如上。给出局部最大值的和、局部最小值的和，构造一个长度最小的数组。

思路：这个题很怪。因为给出的n的和不超过2e5，所以我们可以直接从较小值到较大值进行枚举，长度最小为2*(x - y)。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N = 1e5 + 5;
int t, x, y;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> t;
    while(t --) {
        std::cin >> x >> y;
        std::cout << 2 * (x - y) << '\n';
        for(int i = y; i <= x; i ++) {
            std::cout << i << ' ';
        }
        for(int i = x - 1; i > y; i --) {
            std::cout << i << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}

C. Dora and Search

给出一个permutation，找出一个区间，它的左右端点的值不是这个区间的最大值或最小值；若不存在，输出-1。

思路：因为是permutation，其实很容易判断极值，直接双指针搞一下就可以。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N = 2e5 + 5;
int t, n;
int a[N];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> t;
    while(t --) {
        std::cin >> n;
        for(int i = 1; i <= n; i ++) {
            std::cin >> a[i];
        }
        int L = 1, R = n;
        int l = 1, r = n;
        while(std::min(a[l], a[r]) == L || std::max(a[l], a[r]) == R) {
            if(a[l] > a[r] && a[l] == R) {
                l ++, R --;
            }
            else if(a[l] < a[r] && a[l] == L) {
                l ++, L ++;
            }
            if(a[r] > a[l] && a[r] == R) {
                r --, R --;
            }
            else if(a[r] < a[l] && a[r] == L) {
                r --, L ++;
            }
            if(l >= r)
                break;
        }
        if(l < r) 
            std::cout << l << ' ' << r << '\n';
        else
            std::cout << -1 << '\n';
    }
    return 0;
}

D. Moscow Gorillas

给出两个同样长度的permutation，求满足区间内两个数组的MEX值相同的区间有多少个。

思路：学习自严格鸽的思路，很清晰易懂！

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N = 2e5 + 5;
int t, n;
int a[N], b[N];
ll posa[N], posb[N];

ll num(ll x) {
    return x * (x + 1) / 2;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n;
    for(int i = 1; i <= n; i ++) {
        std::cin >> a[i];
        posa[a[i]] = i;
    }
    for(int i = 1; i <= n; i ++) {
        std::cin >> b[i];
        posb[b[i]] = i;
    }
    int l = posa[1], r = posb[1];
    if(l > r) std::swap(l, r);
    ll ans = num(l - 1) + num(n - r) + num(r - l - 1);
    for(int i = 1; i <= n; i ++) {
        if((posa[i + 1] < l || posa[i + 1] > r) && (posb[i + 1] < l || posb[i + 1] > r)) {
            ll L = 1, R = n;
            if(i + 1 <= n) {
                if(posa[i + 1] < l) L = std::max(L, posa[i + 1] + 1);
                if(posa[i + 1] > r) R = std::min(R, posa[i + 1] - 1);
                if(posb[i + 1] < l) L = std::max(L, posb[i + 1] + 1);
                if(posb[i + 1] > r) R = std::min(R, posb[i + 1] - 1);
            }
            ans += (R - r + 1) * (l - L + 1);
        }
        l = std::min({(ll)l, posa[i + 1], posb[i + 1]});
        r = std::max({(ll)r, posa[i + 1], posb[i + 1]});
    }
    std::cout << ans << '\n';
    return 0;
}