Atcoder Beginner Contest 389 题解

发表于 更新于 分类于 阅读次数： 本文字数： 5.9k
二分这东西久了不写就错漏百出，借助E和F好好复习下二分和树状数组。

A

题意

以字符串形式给出99乘法表内的算式，输出答案。

题解

没什么好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    string s;
    cin >> s;
    cout << (s[0] - '0') * (s[2] - '0') << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定一个阶乘的结果，判断是多少的阶乘。

题解

不会溢出，直接从1开始乘就行。

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

void solve() {
    int n;
    cin >> n;
    int a = 1;
    int cnt = 1;
    while (a != n) {
        a *= ++cnt;
    }
    cout << cnt << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

有三种操作：1. 向序列中新添加一个数，它的索引是之前序列总长，长度为 \(l\) 。2. 弹出序列前 \(k\) 个数，3. 输出当前序列第 \(k\) 个数的索引。

题解

模拟即可，不需要真的弹出，维护序列起点坐标即可。

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

void solve() {
    int q;
    cin >> q;
    vector<pair<int, int>> que;
    int cnt = 0;
    int st = 0;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l;
            cin >> l;
            if (que.empty()) {
                que.emplace_back(0, l);
            } else {
                que.emplace_back(que.back().first + que.back().second, l);
            }
        } else if (op == 2) {
            cnt += (que[st]).second;
            st++;
        } else {
            int k;
            cin >> k;
            cout << que[st + k - 1].first - cnt << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

边长为 1 的方格纸上画一个圆，圆心位于中心方格的中心，给定圆的半径，求出有多少个方格被完全包含在圆内。

题解

最中心的方格一定被包含在答案内，由于对称性，我们可以只考虑圆右上角的部分和 \(x\) 轴上的方格，最后把答案乘 4 加 1。

对于右上角的部分（不含 \(x,y\)轴），考虑到从右往左的顺序下，纵坐标一定不会减少，可以使用双指针维护答案。

对于 \(x\) 轴上的部分，只需要找到最远的一格即可，满足不等式 \((x+0.5)^2 + 0.5^2\le r^2\)。

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

void solve() {
    int r;
    cin >> r;
    int ans = 0;
    int cmp = r * r;
    int y = 1;
    for (int i = r - 1; i > 0; i--) {
        while ((y + 0.5) * (y + 0.5) + (i + 0.5) * (i + 0.5) <= cmp) {
            y++;
        }
        ans += y - 1;
    }
    ans += sqrt(cmp - 0.25) - 0.5;
    cout << ans * 4 + 1 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

有 \(N\) 个商品，每种商品无穷多，第 \(i\) 个商品的初始价格为 \(P_i\)，但是买 \(k\) 个的价格是 \(k^2P_i\)，现在你有 \(M\) 元，求出最多能买多少商品。

\(N\le 2\times 10^5,M\le 10^{18},P\le2\times10^9\)

题解

买 \(k\) 个商品的价格是 \(k^2P_i\)，说明第 \(j\) 个的价格是 \((2j-1)P_i\)，为了买到最多，显然可以贪心地把所有价格排序，从便宜到贵购买，然而肯定会 TLE。

设我们能购买价格小于 \(x\) 的所有商品，我们就可以把商品分为三个部分：

  1. 价格小于 \(x\) 的，我们全部购买，
  2. 价格等于 \(x\) 的，我们尽量购买，
  3. 价格大于 \(x\) 的，我们选择不买。

这样做，我们就能求出 \(x\) 后用尽量多的钱去购买类型 2 的商品。

接下来的关键就是求出 \(x\)，我们想让 \(x\) 尽可能大（考虑到如果没有价格为 \(x\) 的商品，\(x\) 一定可以继续增大到有对应价格的商品），可以考虑二分，判断条件为购买的金额小于 \(M\) 且购买尽可能多的商品数量 \(k\) ，满足 \((2*k-1)*P_i < x\)。

对于 \(k\) 的求法，我们同样可以选择二分。

这题还需要注意一下二分时数据过大溢出，需要使用__int128。

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

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }
    int lo = 0, hi = 1e18 + 1;
    int res = 0;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        ll cnt0 = 0, cnt1 = 0, sum = M;
        for (int i = 0; i < N; i++) {
            auto get = [&](int p, int mid) {
                int lo = 1, hi = 1e18 + 1;
                int res = 0;
                while (lo < hi) {
                    int k = lo + (hi - lo) / 2;
                    if ((__int128)(2 * k - 1) * p < mid) {
                        res = k;
                        lo = k + 1;
                    } else {
                        hi = k;
                    }
                }
                return res;
            };
            ll k = get(P[i], mid);
            cnt0 += k;
            sum -= k * k * P[i];
            if ((2 * k + 1) * P[i] == mid) {
                cnt1++;
            }
            if (sum < 0) {
                break;
            }
        }
        if (sum >= 0) {
            res = max(res, (int)(cnt0 + min(cnt1, sum / mid)));
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    cout << res << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

有 \(N\) 场比赛，第 \(i\) 场比赛只给分数为 \(L_i\) ～ \(R_i\) 的人加 1 分，现在给定 \(Q\) 次询问，每次给定一个人的初始分数，这个人会按顺序依次参加所有比赛，求最后的分数。

\(N\le 2\times 10^5, L_i,R_i\le 5\times10^5,Q\le3\times 10^5\)

题解

显然直接模拟 \(O(NQ)\) 的时间复杂度会 TLE，一个自然的想法是，一个人参加比赛的分数会一直改变，我们能不能根据初始分直接计算出会加多少分。

考虑到参加比赛是按照顺序的，考虑以下情形：一个人原本的分数不能在第二场比赛中加分，但是在第一场比赛中加分了，恰好达到第二场比赛的左端点，导致了第二场比赛也加分。因此，我们可以考虑对给定的 \(L_i,R_i\)，维护出初始状态下就能加分的区间\([lans,rans]\)，然后求出区间对单点的和即可。也就是说 \(x + \text{query(x)}\) 即为答案。

接下来的问题就是求出 \(lans\) 和 \(rans\)，这同样会受到之前参加的比赛的影响，因此我们考虑二分分别求出答案。\(lans\) 需要满足的条件即\(lans + \text{query(lans)}\) 恰好等于 \(L_i\)，否则要么不能被这场比赛加分，要么还能继续往左。同理，\(rans\) 需要满足 \(rans + \text{query(rans)}\)恰好等于 \(R_i\)。

涉及到的操作有区间加，单点和，使用树状数组 + 差分数组即可。

这里注意一下模版的使用：区间下标采用的是0-index，区间和是左闭右开的，存储树状数组的数组也是0-index的。

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

template <typename T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int n_ = 0) { init(n_); }
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    T sum(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    T rangeSum(int l, int r) { return sum(r) - sum(l); }
};

void solve() {
    int N;
    cin >> N;
    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++) {
        cin >> L[i] >> R[i];
    }
    Fenwick<int> bit(5e5 + 5);
    for (int i = 0; i < N; i++) {
        int lo = 1, hi = L[i] + 1;
        int lans = 1, rans = 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid + bit.sum(mid) >= L[i]) {
                lans = mid;
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        lo = 1, hi = R[i] + 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid + bit.sum(mid) <= R[i]) {
                lo = mid + 1;
                rans = mid;
            } else {
                hi = mid;
            }
        }
        bit.add(lans - 1, 1);
        bit.add(rans, -1);
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int x;
        cin >> x;
        cout << x + bit.sum(x) << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}