AtCoder Beginner Contest 216

E. Amusement Park

给定 \(n\) 个数，最多 \(k\) 次操作，每次可以拿走某个数 \(a_i\) 加入得分，然后把 \(a_i-1\) 放回，问得分最大值，\(k,a_i\le 2\times 10^9\)

二分最后剩下的所有数里的最大值为 \(x\) ，答案是把所有数都拿到 \(x\) 的得分，然后加上剩下次数个 \(x\) 的得分。

需要注意二分上界 \(r = 2\times 10^9\) ，所以二分 mid = (l + r) / 2 的时候可能会爆 int 。坑死我了

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
#include <bits/stdc++.h>
#define N 200007
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) f |= (c == '-');
    for(; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

ll n, k, a[N];

inline bool valid(ll x) {
    ll cnt = 0;
    for (int i = 1; i <= n; ++i) 
        if (a[i] > x) cnt += a[i] - x;
    return cnt <= k;
}

inline ll sum(ll l, ll r) {
    return (l + r)  * (r - l + 1) / 2;
}

int main() {
    n = rd(); k = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    ll l = 0, r = 2e9;
    while (l < r) {
        ll mid = (l + r) / 2;
        valid(mid) ? r = mid : l = mid + 1;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) 
        if (a[i] > l) {
            ans += sum(l + 1, a[i]);
            k -= a[i] - l;
        }
    ans += k * l;
    printf("%lld\n", ans);
    return 0;
}

F. Max Sum Counting

有 \(n\) 个数对 \((A_i, B_i)\)构成一个集合，问有多少个子集，满足子集内 \(A\) 的最大值大于 \(B\) 的和。

考虑枚举最大的 \(A\) 是谁，将所有数对按照 \(A\) 从小到大排序，问题转化为选哪些 \(B\) 。

假设现在考虑排序后第 \(i\) 个数对，则 \(B_i\) 必选，相当于计数 \(B_1,\cdots,B_{i-1}\) 中选出若干，且总和不超过 \(A_i-B_i\) 的方案数。

因为 \(A\) 的值域很小，搞一个 01 背包计数即可，复杂度 \(O(n\times \max A_i)\) 。

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>
#define N 5007
#define mod 998244353
using namespace std;
typedef long long ll;

int n, f[N] = {1};

struct node {int a, b;} c[N];

inline bool operator < (const node &a, const node &b) {
    return a.a == b.a ? a.b < b.b : a.a < b.a;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &c[i].a);
    for (int i = 1; i <= n; ++i) scanf("%d", &c[i].b);
    sort(c + 1, c + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int v = 0; v <= c[i].a - c[i].b; ++v) 
            ans = (ans + f[v]) % mod;
        for (int v = N - 1; v >= c[i].b; --v) 
            f[v] = (f[v] + f[v - c[i].b]) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

G. 01Sequence

构造长度为 \(n\) 的 \(01\) 序列，满足 \(k\) 个形如 “ \([l_i,r_i]\) 内至少有 \(x_i\) 个 \(1\) ” 的条件，且 \(1\) 的个数最少。

将约束条件按照右端点从小到大排序，考虑每个条件当前还未满足的个数。

则对于每个 \(1\) ，在可行的范围内往右放的贡献不低于往左放，因此从右边界依次放过来即可。

查询未满足的个数需要维护一个树状数组，复杂度 \(O(n\log n)\) 。

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
#include <bits/stdc++.h>
#define N 200007
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) f |= (c == '-');
    for(; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int cur[N], vis[N];

#define lowbit(x) (x & -x)

inline void add(int x) {
    for (; x < N; x += lowbit(x)) ++cur[x];
}

inline int calc(int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += cur[x];
    return res;
}

struct node {int l, r, k;} c[N];

inline bool operator < (const node &a, const node &b) {return a.r < b.r;}

int main() {
    int n = rd();
    int m = rd();
    for (int i = 1; i <= m; ++i) {
        c[i].l = rd(); c[i].r = rd(); c[i].k = rd();
    }
    sort(c + 1, c + 1 + m);
    for (int i = 1; i <= m; ++i) {
        int nw = calc(c[i].r) - calc(c[i].l - 1);
        for (int ptr = c[i].r; nw < c[i].k; --ptr) 
            if (!vis[ptr]) {
                add(ptr); ++nw; vis[ptr] = 1;
            }
    }
    for (int i = 1; i <= n; ++i) printf("%d ", vis[i]);
    return 0;
}

H. Random Robots