Codeforces Round 916 (Div. 3)

发表于 更新于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 4 分钟
I love you not because of who you are, but because of who I am when I am with you.

A. Problemsolving Log

思路：

  • 按题意模拟即可

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    std::array<int, 26> a {};
    for (int i = 0; i < n; i++) {
        a[s[i] - 'A']++;
    }
    int ans = 0;
    for (int i = 0; i < 26; i++) {
        if (a[i] >= i + 1) ans++;
    }
    std::cout << ans << "\n";
}

B. Preparing for the Contest

思路：

  • 比前一个数大，直接枚举 \(n - k - 1\) 个连续降序数字和 \(k + 1\)​ 个连续升序的序列

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    int n, k;
    std::cin >> n >> k;

    for (int i = n; i > k + 1; i--) {
        std::cout << i << " ";
    }
    for (int i = 1; i <= k + 1; i++) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

C. Quests

思路：

  • 维护序列 \(b\) 的 \(1-i\) 区间最大值就行，甚至不需要线段树，直接枚举维护前 \(i\) 个数的最大值
  • 运用前缀和，\(O(1)\) 的处理当前位置的经验值，最后在 \(0 \sim n\) 取 \(max\)​

时间复杂度：\(O(nlogn)\)

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Info {
    int v;

    Info(int v = 0) : v(v) {};

    Info &operator+=(const Info &now) {
        this->v = std::max(now.v, this->v);
        return *this;
    };
};

Info operator+(Info a, Info b) {
    Info c = a;
    c += b;
    return c;
}

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }

    SegmentTree<Info> seg(n);
    seg.init(b);

    std::vector<int> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }
    i64 ans = 0;
    for (int i = 0; i < std::min(k, n); i++) {
        i64 tmp = s[i + 1] + (k - i - 1) * seg.rangeQuery(0, i + 1).v;
        ans = std::max(ans, tmp);
    }
    
    std::cout << ans << "\n";
}

D. Three Activities

思路：

  • 我们会发现，因为就三个不同的日子，那么只要在每个项目的人数大小前三，求一个\(\Sigma^{3}_{i=1}a_i+a_j+a_k(i \neq j \neq k)\)​

时间复杂度：\(O(10 \times nlogn)\)

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
void solve() {
    int n;
    std::cin >> n;

    std::vector<std::array<int, 2>> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i][0];
        a[i][1] = i;
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i][0];
        b[i][1] = i;
    }
    for (int i = 0; i < n; i++) {
        std::cin >> c[i][0];
        c[i][1] = i;
    }

    std::sort(a.rbegin(), a.rend());
    std::sort(b.rbegin(), b.rend());
    std::sort(c.rbegin(), c.rend());

    i64 ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (a[i][1] != b[j][1] && b[j][1] != c[k][1] && c[k][1] != a[i][1]) {
                    i64 sum = a[i][0] + b[j][0] + c[k][0];
                    ans = std::max(ans, sum);
                }
            }
        }
    }
    std::cout << ans << "\n";
}

E. Game with Marbles (Hard & Easy Version)

思路：

  • 贪心的去丢弹珠，任何一个人一定会首先丢掉对方最多的弹珠，以保证自己的优势
  • 所以，只需要把 Alice 和 Bob的弹珠和从大到小排序，然后按奇偶进行取弹珠即可
  • 最后输出 A - B

时间复杂度：\(O(nlogn)\)

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
void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }
    
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(), [&](int i, int j) {
        return a[i] + b[i] > a[j] + b[j];
    });

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        int j = p[i];
        if (i % 2 == 0) {
            ans += a[j] - 1;
        } else {
            ans -= b[j] - 1;
        }
    }
    std::cout << ans << "\n";
}