deforces Round #852 (Div. 2) 1793

发表于 更新于 分类于 ，

    题意

    思路

    代码

    题意

    思路

    代码

    题意

    思路

    代码

    题意

    思路

    代码

Codeforces Round #852 (Div. 2) 1793

Complete problemset

A. Yet Another Promotion

题意

现在需要买至少n斤土豆，有a元每斤和b元每斤两种不同单价的土豆。

其中每买m斤a元每斤就送一斤。

问需要的最小金额是多少。

思路

如果$a\le b$，显然选择a更优，花费为$(n-n/(m+1))*a$

否则$a>b$, 两种不同的单价的土豆在买$m+1$斤分别的花费是$ma$和$(m+1)b$，我们选择较小者。剩余n%(m+1)则买b。花费$min(ma, (m+1)b)*n/(m+1) + n%(m+1)b$

因此答案为$min((n-n/(m+1))a, min(ma, (m+1)b)*n/(m+1) + n%(m+1)b)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll a, b, n, m;
    cin >> a >> b >> n >> m;
    cout << min((n - n / (m + 1)) * a,
                n / (m + 1) * min(m * a, (m + 1) * b) + n % (m + 1) * b)
         << "\n";
    // if (a <= b) {
    //     cout << n * a - n / (m + 1) * a << "\n";
    // } else if (m * (a - b) < b) {
    //     ll ca = n / (m + 1) * (m + 1), cb = n - ca;
    //     cout << ca * a - ca / (m + 1) * a + cb * b << "\n";
    // } else {
    //     cout << n * b << "\n";
    // }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B. Fedya and Array

题意

构造一个最短的数组，使得环形数组中相邻元素之差为1，数组中最大值是x，最小值是y。

思路

长度2(x-y)，从x到y再到x即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, x, y;
    cin >> x >> y;
    cout << 2 * (x - y) << endl;
    ll u = x;
    for (ll i = x; i >= y; i--) {
        cout << i << " ";
    }
    for (ll i = y + 1; i <= x - 1; i++) {
        cout << i << " ";
    }
    cout << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C. Dora and Search

题意

给出一个数组，找到一个区间[l,r] 使得l和r位置不是最大值和最小值。

思路

双指针，左右指针分别指向起始和末尾，当有指针为最大或最小值时则移动，左指针向右移动，右指针向左移动。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

ll a[N];

void sol() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int mn = 1, mx = n, l = 1, r = n;
    while (l < r && (a[l] == mn || a[l] == mx || a[r] == mn || a[r] == mx)) {
        if (a[l] == mn)
            mn++, l++;
        else if (a[l] == mx)
            mx--, l++;
        else if (a[r] == mn)
            mn++, r--;
        else if (a[r] == mx)
            mx--, r--;
    }
    if (l != r) {
        cout << l << " " << r << "\n";
    } else {
        cout << "-1\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D. Moscow Gorillas

题意

给出两个数组，问有多少个区间的mex相同。

思路

一个区间只要包含了1到n的最小区间那么这个区间的MEX至少为n。利用这一点，一个区间只要包含了1到n+1的最小区间那么这个区间的MEX至少为n+1，由此包含了1到n的最小区间但是没有包含1到n+1的最小区间，就得到了MEX恰好为n的区间数。

对两个数组相同的MEX值区间范围求交集。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> p(n), q(n), wp(n + 1), wq(n + 1);
    vector<pair<int, int>> a, b;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        wp[p[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        cin >> q[i];
        wq[q[i]] = i;
    }
    ll l1 = min(wp[1], wq[1]), r1 = max(wp[1], wq[1]);
    auto cpt = [](ll x) -> ll { return x * (x + 1) / 2; };
    ll ans = cpt(l1) + cpt(n - r1 - 1) + cpt(max(r1 - l1 - 1, 0LL)) + 1;
    for (int i = 1; i <= n; i++) {
        if (i == 1) {
            a.emplace_back(wp[i], wp[i]);
            b.emplace_back(wq[i], wq[i]);
        } else {
            auto [x1, y1] = a.back();
            a.emplace_back(min(x1, wp[i]), max(y1, wp[i]));
            auto [x2, y2] = b.back();
            b.emplace_back(min(x2, wq[i]), max(y2, wq[i]));
        }
    }
    for (int i = 1; i < n; i++) {
        // auto [x1, y1] = a[i - 1];
        // auto [x2, y2] = a[i];
        // auto [x3, y3] = b[i - 1];
        // auto [x4, y4] = b[i];
        int la = a[i - 1].first, ra = a[i - 1].second;
        int lla = a[i].first, rra = a[i].second;
        if (lla < la) {
            // lla++;
            // rra = n - 1;
            rra = n;
        } else {
            // rra--;
            // lla = 0;
            lla = -1;
        }
        int lb = b[i - 1].first, rb = b[i - 1].second;
        int llb = b[i].first, rrb = b[i].second;
        if (llb < lb) {
            // llb++;
            // rrb = n - 1;
            rrb = n;
        } else {
            // rrb--;
            // llb = 0;
            llb = -1;
        }
        ll lcnt = max(0, min(la, lb) - max(lla, llb));
        ll rcnt = max(0, min(rra, rrb) - max(ra, rb));
        ans += lcnt * rcnt;
    }
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}