本来想补了后面题再写的，不过这几天好像事有点多

1334A Level Statistics

有个关卡，给出每天$a-$挑战的人次，$b-$通关的人次，问一个序列是否满足逻辑。

就和现实一样，判断$a,b$关系和上一轮关系，$O(n)$。

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int a, b, n, ta, tb, f = 1;
        cin >> n;
        --n;
        cin >> a >> b;
        if (a < b) f = 0;
        while (n--) {
            cin >> ta >> tb;
            if (ta < tb) f = 0;
            if (a > ta || b > tb) f = 0;
            if (tb - b > ta - a) f = 0;
            a = ta, b = tb;
        }
        if (f) puts("YES");
        else puts("NO");
    }
    return 0;
}

1334B Middle Class

有一些数字，可以选择一些数，把他们变成和额度平均值，问最多能让多少个数$\geq x$。

排序后从大到小贪心，$O(n\log n)$。

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

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, x, num = 0;
        cin >> n >> x;
        vector<int> a;
        ll sum = 0;
        for (int i = 0, t; i < n; ++i) {
            cin >> t;
            if (t >= x) sum += t, ++num;
            else a.emplace_back(t);
        }
        sort(a.begin(), a.end());
        while (!a.empty()) {
            if ((sum + a.back()) / x < num + 1) break;
            sum += a.back();
            a.pop_back();
            ++num;
        }
        cout << num << endl;
    }
    return 0;
}

1334C Circle of Monsters

有一些怪在一个环上，开一枪可以让一个怪血量$-1$，一个怪死后会对背后的怪溅射伤害，如果背后的怪已经死了则无影响。问最少开几枪打死全部怪。

因为在打死一个怪以后，环就变成了链，那么开枪的顺序就固定下来了，因此枚举第一个打死哪个怪即可，$O(n)$。

C.cpp
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>
using namespace std;
const int N = 3e5 + 5;

ll a[N], b[N], ss[N];

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        ll sum = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i] >> b[i];
            ss[i] = max(0ll, a[i] - b[i - 1]);
        }
        ss[1] = max(0ll, a[1] - b[n]);
        for (int i = 1; i <= n; ++i) {
            sum += ss[i];
        }
        ll ans = INF64;
        for (int i = 1; i <= n; ++i) {
            ans = min(ans, sum - ss[i] + a[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

1334D Minimum Euler Cycle

一个有向的完全图，按字典序最小的方式走出欧拉环，然后问第$l\sims r$的数字是哪些。

这个顺序只要画画能发现，即$1,2,1,3,1,4…1,x,2,3,2,4…2,x,3,4……$，所以预处理下每一段长度再计算一下即可，$(r-l)$。

D.cpp
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n;
ll cnt[N];

int calc(ll x) {
    if (x > cnt[n]) return 1;
    int ptr = lower_bound(cnt, cnt + n, x) - cnt;
    int t = x - cnt[ptr - 1];
    if (t & 1) return ptr;
    else return t / 2 + ptr;
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        ll l, r;
        cin >> n >> l >> r;
        for (int i = 1; i <= n; ++i) {
            cnt[i] = cnt[i - 1] + 2 * (n - i);
        }
        for (ll i = l; i <= r; ++i) {
            cout << calc(i) << ' ';
        }
        cout << endl;
    }
    return 0;
}

1334E Divisor Paths

过阵子必补