Codeforces Round 510(Div.2)

Posted on | In

今天这波大号+49分，感觉还行，另吐槽一波predictor越来越不准了。

A.Benches

原有$n$张长凳，第$i$张长凳上坐着$a_i$个人，现在又来了$m$个人，问长凳所需容量的最大值和最小值

显然，这个数据量直接暴力一波就最稳了。

Code：

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
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    priority_queue<int> Q;

    int mx = -1;
    for (int i = 0; i < n; i++) {
        int k; cin >> k;
        mx = max(mx, k);
        Q.push(-k);
    }
    mx += m;
    for (int i = 0; i < m; i++) {
        int top = Q.top(); Q.pop();
        Q.push(top - 1);
    }
    int mn = 0;
    while (!Q.empty()) {
        mn = min(mn, Q.top());
        Q.pop();
    }
    cout << -mn << " " << mx << endl;
}

B.Vitamin

商店有$n$种饮料，每种饮料的价格为$c_i$，含有A、B、C中任意种维生素，Petya需要ABC三种维生素，问达到要求的最小花费or不存在方案。

简单dp，分别以1b、10b、100b代表A、B、C，将每种饮料的维生素种类状态压缩，于是可得状态转移方程：$dp[i + 1][j | status[i + 1]] = dp[i][j] + c[i], 1 \leq i < n$。最终答案为dp[n][7]。

Code:

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>
using namespace std;

#define endl "\n"

int v[1005], inc[1005];
long long dp[1005][10];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        char s[10]; cin >> v[i] >> s;
        for (int j = strlen(s) - 1; j >= 0; j--) {
            if (s[j] == 'A') inc[i] |= 1;
            else if (s[j] == 'B') inc[i] |= 2;
            else if (s[j] == 'C') inc[i] |= 4;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 7; j++) {
            dp[i][j] = 0x3f3f3f3f3f3f3f3f;
        }
    }

    dp[1][inc[1]] = v[1];

    for (int i = 1; i <= n - 1; i++) {
        for (int j = 0; j <= 7; j++) {
            dp[i + 1][j] = dp[i][j];
        }
        for (int j = 0; j <= 7; j++) {
            if (dp[i + 1][j | inc[i + 1]] > dp[i][j] + v[i + 1]) {
                dp[i + 1][j | inc[i + 1]] = dp[i][j] + v[i + 1];
            }
        }
    }
    if (dp[n][7] != 0x3f3f3f3f3f3f3f3f) {
        cout << dp[n][7] << endl;
    }
    else {
        cout << -1 << endl;
    }
}

C.Array Product

给定一个有$n$个元素的序列，可以无限次将序列中某两个元素合并替换为他们的乘积，只有一次机会删去某一个元素。需要使序列最终剩下的一个元素最大，输出操作方案。

Solution:

1、按小到大顺序使负数两两合并。
2、将剩下的非正数两两合并。
3、此时应只剩下一个非正数or没有， 若有则将它删去。
4、合并所有正数。
(注: 显然，这题中只有负数的大小是有用的，可以将正数用1代替。 )

Code：

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
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

const int maxn = 2e5 + 5;

struct Node {
    int v, i;
    Node(int vv = 0, int ii = 0) : v(vv), i(ii) {}
    bool operator< (const Node& b) const { return v > b.v; }
};

int a[maxn];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    priority_queue<Node> Q;
    for (int i = 1; i <= n; i++) {
        Q.emplace(a[i], i);
    }

    while (!Q.empty()) {
        Node u1 = Q.top(); Q.pop();
        if (Q.empty()) break;
        Node u2 = Q.top(); Q.pop();

        if ((u1.v < 0 && u2.v < 0) || (u1.v > 0 && u2.v > 0)) {
            Q.emplace(1, u2.i);
            cout << 1 << " " << u1.i << " " << u2.i << endl;
        }
        else if (u2.v == 0) {
            Q.emplace(0, u2.i);
            cout << 1 << " " << u1.i << " " << u2.i << endl;
        }
        else if (u2.v > 0) {
            Q.emplace(u2);
            cout << 2 << " " << u1.i << endl;
        }
    }
}

D.Petya and Array

给定一个有$n$个元素的数列和一个整数$t$, 求: $\sum_{l = 1}^{n} \sum_{r = l}^{n} [(\sum_{i = l}^{r} a_i) < t]$

即求$\sum_{i = 1}^{n} \sum_{j = i}^{n} [prefix_i + t > prefix_j]$, 先离散化前缀和，然后树状数组维护一下就好。

Code:

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
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

typedef long long ll;

const int maxn = 2e5 + 5;

int n;
ll t, a[maxn], sum[maxn];
int b[maxn];

void upd(int i) {
    for (; i < maxn; i += (i & (-i))) {
        b[i]++;
    }
}

int query(int i) {
    int res = 0;
    for (; i > 0; i -= (i & (-i))) {
        res += b[i];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        a[i] += a[i - 1];
    }

    sort(sum + 1, sum + 1 + n);
    int m = unique(sum + 1, sum + 1 + n) - sum - 1;

    ll res = 0;
    for (int i = n; i >= 1; i--) {
        int pos = lower_bound(sum + 1, sum + 1 + m, a[i]) - sum;
        upd(pos);

        ll tmp = t + a[i - 1];
        pos = lower_bound(sum + 1, sum + 1 + m, tmp) - sum - 1;

        res += query(pos);
    }
    cout << res << endl;
}