AtCoder Beginner Contest 216

发表于2021-09-01更新于2023-09-15字数统计1.6k阅读时长17分

比赛链接

D Pair of Balls

Description

题目链接

Solution

模拟题，用 MM 个栈存储各个圆柱中的球，如果某个颜色的球在栈顶出现两次则将它们弹出，最后看是否有栈非空即可。

Code

Pair of Balls
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;

int n, m;
stack<int> s[MAXN];
vector<int> pos[MAXN];
int cnt[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int a;
            cin >> a;
            s[i].push(a);
            pos[a].push_back(i);
        }
    }

    queue<int> q;
    for (int i = 1; i <= m; i++) {
        cnt[s[i].top()]++;
        if (cnt[s[i].top()] == 2) q.push(s[i].top());
    }

    while (!q.empty()) {
        int c = q.front();
        q.pop();
        s[pos[c][0]].pop(), s[pos[c][1]].pop();
        if (s[pos[c][0]].size()) {
            int ca = s[pos[c][0]].top();
            cnt[ca]++;
            if (cnt[ca] == 2) q.push(ca);
        }
        if (s[pos[c][1]].size()) {
            int ca = s[pos[c][1]].top();
            cnt[ca]++;
            if (cnt[ca] == 2) q.push(ca);
        }
    }

    for (int i = 1; i <= m; i++)
        if (s[i].size()) {
            puts("No");
            return 0;
        }
    puts("Yes");
    return 0;
}

E Amusement Park

Description

题目链接

Solution

二分满足 ∑i=1Nmax(0,Ai−x+1)≤K\sum \limits_{i=1}^{N} max(0,A_i-x+1) \le K 的最小值 xx。对于公园 ii，若 Ai≥xA_i \ge x，那么 Takahashi 可获得的满足度为 x+(x+1)+⋯+Aix+(x+1)+\dots+A_i。除此之外，他还会获得 (x−1)∗(K−∑i=1Nmax(0,Ai−x+1))(x-1)*(K-\sum \limits_{i=1}^{N} max(0,A_i-x+1)) 的满足度。

Code

Amusement Park
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
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

#define int long long

int n, k;
int a[MAXN], mx;
unsigned int ans;

bool check(int mid) {
    int tot(0);
    for (int i = 1; i <= n; i++) 
        if (a[i] >= mid) tot += a[i] - mid + 1;
    return tot <= k;
}

signed main() {
    boost;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i], mx = max(mx, a[i]);
    int l = 1, r = 2e9, tmp = 2e9;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, tmp = mid;
        else l = mid + 1;
    }
    int tot(0);
    for (int i = 1; i <= n; i++) {
        if (a[i] >= tmp) {
            tot += a[i] - tmp + 1;
            ans += (a[i] + tmp) * (a[i] - tmp + 1) / 2;
        }
    }
    ans += (k - tot) * (tmp - 1);
    cout << ans << "\n";
    return 0;
}

F Max Sum Counting

Description

题目链接

Solution

若指定 AiA_i 为最大值，取 S={j∣(j<i∧Aj≤Ai)∣(j>i∧Aj<Ai)}S = \{j|(j<i ∧ A_j \le A_i)|(j>i ∧ A_j<A_i)\}，那么问题转化成求满足 S′⊂S∧∑j∈S′Bj≤Ai−BiS' \subset S ∧ \sum \limits_{j∈S'} B_j \le A_i-B_i 的 S′S' 的数目，这可以用 O(N2)O(N^2) 的 DPDP 求解。如果 AA 不是单增的，那么不同的 ii 对应的 SS 可能没有包含关系，这时需要重新 DPDP，从而总的时间复杂度为 O(N3)O(N^3)。将 AA 升序排列，那么当前 SS 是从之前的 SS 扩展得到的，因此可以延用之前 DPDP 的结果，从而时间复杂度降至 O(N2)O(N^2)。

Code

Max Sum Counting
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 debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 5E3 + 5;
const int MOD = 998244353;
int n, ans;
int dp[MAXN][MAXN];

void add(int& a, int b) { a = (a + b) % MOD; }

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    vector<pair<int, int>> v;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i].first;
    for (int i = 1; i <= n; i++) cin >> v[i].second;
    sort(v.begin(), v.end());
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int s = 0; s <= v[n].first; s++) {
            add(dp[i][s], dp[i - 1][s]);
            if (s - v[i].second >= 0) add(dp[i][s], dp[i - 1][s - v[i].second]);
        }
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++) {
        int mx = v[i].first;
        int s = mx - v[i].second;
        for (int j = 0; j <= s; j++) add(ans, dp[i - 1][j]);
    }
    cout << ans;
    return 0;
}

G 01Sequence

Description

题目链接

Solution

将区间按右端点升序排列，将 1 尽可能放在区间右边即可。实现过程中需要求解区间内 1 的个数，查询区间内从右往左第一个不为 1 的位置，将不为 1 的位置用 1 覆盖，这些操作用树状数组和并查集便可快速实现。

Code

01Sequence
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
83
84
85
86
87
88
89
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, fa[MAXN];

vector<tuple<int, int, int>> v;

struct BIT {  // Binary Index Trees, 1based
    int lowbit(int x) { return x & (~x + 1); }
    /* O(n) build tree*/
    BIT() {
        for (int i = 1; i <= n; i++) c[i] = 0;
    }
    void build() {
        for (int i = 1; i <= n; i++) {
            int j = i + lowbit(i);  // j is father of i
            if (j <= n) c[j] += c[i];
        }
    }
    /*@param x the position to add val*/
    void add(int x, LL val) {
        while (x <= n) c[x] += val, x += lowbit(x);
    }
    /*range [1, x] sum query*/
    LL query(int x, LL res = 0) {
        while (x) res += c[x], x -= lowbit(x);
        return res;
    }
    array<LL, MAXN> c;
} bit[3];
/*range [l, r] add val*/
inline void add(int l, int r, LL val) {
    bit[1].add(l, val), bit[1].add(r + 1, -val);
    bit[2].add(l, val * l), bit[2].add(r + 1, -val * (r + 1));
}
/*range [l, r] sum query*/
inline LL query(int l, int r, LL res = 0) {
    res = bit[0].query(r) + bit[1].query(r) * (r + 1) - bit[2].query(r);
    res -= bit[0].query(l - 1) + bit[1].query(l - 1) * l - bit[2].query(l - 1);
    return res;
}

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

signed main() {
    read(n, m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    v.resize(m);
    for (auto& [r, l, x] : v) read(l, r, x);
    sort(v.begin(), v.end());
    for (auto& [r, l, x] : v) {
        int v = query(l, r);
        if (v >= x) continue;
        x -= v;
        int p = r;
        while (x) {
            p = find(p);
            add(p, p, 1);
            fa[p] = p - 1;
            x--;
        }
    }
    for (int i = 1; i <= n; i++) printf("%d ", query(i, i));
    return 0;
}