Contest Notes

AtCoder Beginner Contest 382

比赛链接

Problems AC
A. Daily Cookie ○
B. Daily Cookie 2 ○
C. Kaiten Sushi ○
D. Keep Distance ○
E. Expansion Packs ⊕
F. Falling Bars ○
G. Tile Distance 3

A 签到

Code >folded
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int n = read();
    int k = read();

    string s;
    cin >> s;

    int m = s.size();
    for (int i = m - 1; i >= 0 and k; i--) {
        if (s[i] == '@') {
            s[i] = '.';
            k--;
        }
    }

    cout << s;
}

B 签到

Code >folded
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int n = read();
    int k = read();

    string s;
    cin >> s;

    int m = s.size();
    for (int i = m - 1; i >= 0 and k; i--) {
        if (s[i] == '@') {
            s[i] = '.';
            k--;
        }
    }

    cout << s;
}

C 签到

Code >folded
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
void solve() {
    int n = read();
    int m = read();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    vector<int> b(m + 1);
    for (int i = 1; i <= m; i++) {
        b[i] = read();
    }

    using pii = std::pair<int, int>;
    #define fi first
    #define se second
    std::priority_queue<pii> q;
    for (int i = 1; i <= m; i++) {
        q.ep(b[i], i);
    }

    vector<int> c(m + 1, -1);
    // cout << q.size() << '\n';

    for (int i = 1; i <= n; i++) {
        while (!q.empty() and q.top().fi >= a[i]) {
            // cout << q.top().fi << " " << q.top().se << '\n';
            c[q.top().se] = i;
            // q.pop();
            q.pop();
        }
    }

    for (int i = 1; i <= m; i++) {
        cout << c[i] << '\n';
    }
}

D 签到

Code >folded
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
void solve() {
    int n = read();
    int m = read();

    int ans = 0;
    vector<int> a(n + 1);
    auto dfs1 = [&](auto&& self, int now) {
        if (now == n + 1) {
            ans++;
            return;
        }

        if (now == 1) {
            for (int i = 1; i <= m; i++) {
                a[now] = i;
                if (i + (n - now) * 10 <= m) self(self, now + 1);
            }
        } else {
            for (int i = max(1, a[now - 1] + 10); i <= m; i++) {
                a[now] = i;
                if (i + (n - now) * 10 <= m) self(self, now + 1);
            }    
        }
    };
    dfs1(dfs1, 1);
    a.assign(n + 1, 0);
    cout << ans << '\n';

    auto dfs2 = [&](auto&& self, int now) {
        if (now == n + 1) {
            for (int i = 1; i <= n; i++) {
                cout << a[i] << " \n"[i == n];
            }
            return;
        }

        if (now == 1) {
            for (int i = 1; i <= m; i++) {
                a[now] = i;
                if (i + (n - now) * 10 <= m) self(self, now + 1);
            }
        } else {
            for (int i = max(1, a[now - 1] + 10); i <= m; i++) {
                a[now] = i;
                if (i + (n - now) * 10 <= m) self(self, now + 1);
            }    
        }
    };

    dfs2(dfs2, 1);
}

E 期望 DP

可以通过 dp 得到 $dp_i$ 表示开一个卡包得到 $i$ 张牌的概率。

令 $f_i$ 表示得到 $i$ 张牌期望开的卡包数量。

$$
f_i = 1 + \sum_{j = 0}^{i - 1} f_{i - j} dp_j
$$

\begin{aligned}
f_i &= 1 + \sum_{j = 0}^{i - 1} f_{i - j} \cdot dp_j \\
f_i &= 1 + f_i \cdot dp_0 + \sum_{j = 1}^{i - 1} f_{i - j} \cdot dp_j \\
f_i (1 - dp_0) &= 1 + \sum_{j = 1}^{i - 1} f_{i - j} \cdot dp_j \\
f_i &= \frac{1 + \sum_{j = 1}^{i - 1} f_{i - j} \cdot dp_j}{1 - dp_0} \\
\end{aligned}

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
void solve() {
    int n = read();
    int m = read();

    // int ans = 0;
    vector<double> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read() * 1.0 / 100;
    }

    vector<double> dp(n + m + 1);
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        vector<double> ndp(n + 1 + m);
        ndp[0] = dp[0] * (1 - a[i]);
        for (int j = 1; j <= i; j++) {
            ndp[j] = dp[j] * (1 - a[i]) + dp[j - 1] * a[i];
        }
        dp = std::move(ndp);
    }

    // for (int i = 0; i <= n; i++) {
    //     cout << dp[i] << " \n"[i == n];
    // }

    vector<double> f(m + n + 1);

    for (int i = 0; i <= m; i++) {
        double t = 1;
        for (int j = 1; j < i; j++) {
            t += dp[j] * f[i - j];
        }
        f[i] = t / (1 - dp[0]);
    }

    // cout << f[m];
    printf("%.16f", f[m]);
}

F 线段树

Notice: 线段树带区间操作的时候必须要加懒标记，否则时间复杂度会退化。

Code >folded
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
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using i64 = long long;
// #define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::cerr;
using std::max, std::min, std::swap, std::array;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;

struct SGT {
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid (l + r >> 1)
    int mx[N << 2], tag[N << 2];

    void pushup(int p) {
        mx[p] = max(mx[ls], mx[rs]);
    }
    void pushdown(int p) {
        if (tag[p] == 0) return;
        mx[ls] = max(mx[ls], tag[p]);
        mx[rs] = max(mx[rs], tag[p]);
        tag[ls] = max(tag[ls], tag[p]);
        tag[rs] = max(tag[rs], tag[p]);
        tag[p] = 0;
    }

    int qry(int p, int l, int r, int ql, int qr) {
        if (ql <= l and r <= qr) {
            return mx[p];
        }
        int res = 0;
        pushdown(p);
        if (ql <= mid) res = max(res, qry(ls, l, mid, ql, qr));
        if (mid < qr) res = max(res, qry(rs, mid + 1, r, ql, qr));
        pushup(p);
        return res;
    }
    void upd(int p, int l, int r, int ql, int qr, int x) {
        if (ql <= l and r <= qr) {
            mx[p] = max(mx[p], x);
            tag[p] = max(tag[p], x);
            return;
        }
        pushdown(p);
        if (ql <= mid) upd(ls, l, mid, ql, qr, x);
        if (mid < qr) upd(rs, mid + 1, r, ql, qr, x);
        pushup(p);
    }
} sgt;

void solve() {
    int h = read();
    int w = read();
    int n = read();

    using tup = std::tuple<int, int, int>;
    vector<vector<tup>> a(h + 1);

    for (int i = 1; i <= n; i++) {
        int r = h - read() + 1;
        int c = read();
        int l = read();

        // cerr << r << " " << c << " " << c + l - 1 << '\n';
        a[r].eb(c, c + l - 1, i);
    }

    vector<int> ans(n + 1);
    for (int i = 1; i <= h; i++) {
        for (auto [l, r, idx] : a[i]) {
            // cout << i << " " << sgt.qry(1, 1, w, l, r);
            ans[idx] = sgt.qry(1, 1, w, l, r) + 1;
            sgt.upd(1, 1, w, l, r, ans[idx]);

            // cout << " " << ans[idx] << '\n';
        }
    }

    for (int i = 1; i <= n; i++) {
        // cout << ans[i] << "\n";
        cout << h - ans[i] + 1 << "\n";
    }
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

AtCoder Beginner Contest 382

https://tosakaucw.github.io/atcoder-beginner-contest-382/

Author

TosakaUCW

Posted on

2024-12-01

Updated on

2024-12-01

Licensed under

#

Comments

Catalogue

×