A - Candies for Nephews

EZ.jpg

AC 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
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

void Run() {
    int n;
    std::cin >> n;
    if (n % 3 == 0) std::cout << 0;
    else std::cout << 3 - n % 3;
    std::cout << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

B - Deck of Cards

因为每一次操作都是只能去头或者去尾，令 aa 为操作一的次数、bb 为操作二的次数、cc 为操作三的次数，那么最终的序列必定是前缀的 [1,a][1,a]、后缀的 [n−b+1,n][n-b+1,n] 和中间的首尾 cc 个被删除。

考虑这 cc 个能怎么删。如果全部去头，那么剩余的部分就是 [a+c+1,n−b][a+c+1, n-b]；如果全部去尾，那么剩余部分是 [a+1,n−b−c][a+1, n-b-c]。所以无论怎么取，一定可以保留下来的部分是 R=[a+c+1,n−b−c]R=[a+c+1,n-b-c]，[a+1,n−b]−R[a+1,n-b]-R 则是可能会被删的部分，剩余部分是一定会被删的。

此外还有特殊情况 n=kn=k，此时无论如何一定被删完。

AC 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;

int n, k;
int a[N], b[N], c[3];

void Run() {
    std::cin >> n >> k;
    c[0] = c[1] = c[2] = 0;
    repeat(i, 1, n) b[i] = -1;
    repeat(i, 1, k) {
        char d;
        std::cin >> d;
        a[i] = d - '0';
        c[a[i]]++;
    }

    if (n == k) {
        repeat(i, 1, n) std::cout << "-";
        std::cout << "\n";
        return;
    }

    repeat(i, c[0] + c[2] + 1, n - c[1] - c[2]) b[i] = 1;
    repeat(i, c[0] + 1, n - c[1]) if (b[i] == -1) b[i] = 0;

    repeat(i, 1, n) {
        if (b[i] == 1) std::cout << "+";
        else if (b[i] == 0) std::cout << "?";
        else std::cout << "-";
    }
    std::cout << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

C - Monocarp’s String

设 di=ai−bid_i=a_i-b_i，其中 ai=∣{j:j≤i∧xj=’a’}∣,bi=∣{j:j≤i∧xj=’b’}∣a_i=\Big|\{j:j\le i \land x_j=\texttt{'a'}\}\Big|,b_i=\Big|\{j:j\le i \land x_j=\texttt{'b'}\}\Big|. 那么我们想要删除的段 [l,r][l,r] 应该满足这一段的 ′a′\tt 'a' 比 ′b′\tt 'b' 多 dnd_n 个. 即 dr−dl−1=dnd_r-d_{l-1}=d_n

于是我们从左向右枚举右端点，用 std::map 维护 d↦{ i:di=d }d\mapsto \set{i:d_i=d}. 对于每个 rr，首先找 d=dr−dnd=d_r-d_n，然后因为要求段长最小，直接取 max⁡{ i:di=dr−dn }\max \set{i:d_i=d_r-d_n} 然后作差算段长，再对段长取 min⁡\min 即可。

时间复杂度 O(nlog⁡n)O(n\log{n})

AC 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
int n, a[N], b[N];
char v[N];

void Run() {
    std::cin >> n;
    repeat(i, 1, n) {
        std::cin >> v[i];
        a[i] = a[i - 1] + (v[i] == 'a');
        b[i] = b[i - 1] + (v[i] == 'b');
    }

    // repeat(i, 1, n) std::cout << a[i] - b[i] << " \n"[i == n];

    int s = a[n] - b[n];
    if (s == 0) {
        std::cout << "0\n";
        return;
    }

    std::map<int, std::vector<int>> mp;
    mp[0].push_back(0);
    int ans = 1e9;

    for (int i = 1; i <= n; i++) {
        if (mp.count(a[i] - b[i] - s)) ans = std::min(ans, i - mp[a[i] - b[i] - s].back());
        mp[a[i] - b[i]].push_back(i);
    }

    std::cout << (ans >= n ? -1 : ans) << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

D - Inversion Value of a Permutation

一共最多有 T=n(n−1)2T=\frac{n(n-1)}{2} 对逆序对，而我们只需要 kk 对，所以剩下的 T−kT-k 对“顺序对”一定是由若干段严增段提供的。也就是说，我们希望找到一种分解方案 R={ r }R=\set{r} 使得

∑r∈Rr≤n∑r∈R(r2)=T−k \sum_{r\in R}r \le n \\ \sum_{r\in R} \binom{r}{2}=T-k

我们考虑 dp\tt dp 进行分解。因为 r≥1r\ge 1，所以 dpdp 最多 nn 个位置。令 dpi,v=truedp_{i,v}=\texttt{true} 表示已经填完 1∼i1\sim i 号位置，且 aia_i 恰好是某个递增序列的最后一项，并且 1∼i1\sim i 位的 ∑(r2)=v\sum\binom{r}{2}=v.

所以我们可以得出这样一个 dpdp 转移方程

dp[i,v]=⋀j<idp[j,v−(i−j2)] dp[i,v]=\bigwedge_{j\lt i} dp\Big[j,\quad v-\binom{i-j}{2}\Big]

最后首先检查 dp[n,T−k]dp[n, T-k] 是否为 true，然后在 dpdp 时记录回溯，最后构造即可。

dpdp 的时间复杂度为 O(n4)O(n^4)

AC 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
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
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

int n, k;
std::array<std::bitset<1000>, 50> dp;
int pL[50][1000], pj[50][1000];

int c(int d) { return d * (d - 1) / 2; }
void Run() {
    std::cin >> n >> k;
    dp.fill(0);
    int s = c(n) - k; // increasing

    dp[0].set(0);
    for (int i = 0; i < 50; ++i)
        for (int j = 0; j < 1000; ++j) pL[i][j] = pj[i][j] = -1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            int shift = c(i - j);
            for (int x = shift; x <= s; x++) {
                if (dp[j].test(x - shift) && !dp[i].test(x)) {
                    dp[i].set(x);
                    pL[i][x] = i - j;
                    pj[i][x] = x - shift;
                }
            }
        }
    }

    if (!dp[n].test(s)) {
        std::cout << 0 << "\n";
        return;
    }

    std::vector<int> lens_rev;
    for (int i = n, x = s; i > 0;) {
        int L = pL[i][x];
        if (L == -1) {
            std::cout << 0 << "\n";
            return;
        }
        lens_rev.push_back(L);
        int px = pj[i][x];
        i -= L;
        x = px;
    }
    std::reverse(lens_rev.begin(), lens_rev.end());

    std::vector<int> ans;
    ans.reserve(n);
    int cur = n;
    for (int L : lens_rev) {
        for (int v = cur - L + 1; v <= cur; ++v) ans.push_back(v);
        cur -= L;
    }

    for (int i = 0; i < n; ++i) {
        if (i) std::cout << ' ';
        std::cout << ans[i];
    }
    std::cout << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

E - Predicting Popularity

首先我们对条件进行转化，令 si=max⁡(ai−ac,0)+max⁡(di−dr,0)s_i=\max(a_i-ac,0)+\max(d_i-dr, 0)，记录桶 F[s]=∣i:si=s∣F[s]=\bigg|{i: s_i=s}\bigg|，那么对于 pp，只要至少有 pp 个人其 si≤ps_i\le p，那么 pp 就可以继续增加，直到最终答案为 first pp such that ∑i=0pF[i]=p\sum_{i=0}^p F[i]=p.

考虑用线段树维护 b[i]=F[i]−1b[i]=F[i]-1，那么答案的条件变为 first pp such that ∑i=0pb[i]=−1\sum_{i=0}^p b[i]=-1.

我们预处理出前缀和，那么我们需要在线段树上维护区间的最小值。对于修改操作，由于是在桶上 ±1\plusmn 1，于是对前缀和而言，就是区间加减。所以我们需要的是区间加减的线段树。

对于求取 first pp，由于我们已经维护了前缀和的最小值，可以直接线段树上二分，或者二分套线段树。时间复杂度 O(nlog⁡n)O(n\log n) 或者 O(nlog⁡2n)O(n\log^2 n)

AC 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
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
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 5e5 + 10;

int ac, dr;
int n, m;
int s[N], a[N], d[N];
int bucket[N];

int compute(int i) { return std::max(0, a[i] - ac) + std::max(0, d[i] - dr); }

struct Node {
    int sum, minpre;
} T[N * 5];

void pushup(int p) {
    T[p].sum = T[p << 1].sum + T[p << 1 | 1].sum;
    T[p].minpre = std::min(T[p << 1].minpre, T[p << 1].sum + T[p << 1 | 1].minpre);
}
void build(int p = 1, int l = 0, int r = n) {
    if (l == r) {
        T[p].sum = bucket[l] - 1;
        T[p].minpre = std::min(0, bucket[l] - 1);
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void add(int pos, int v, int p = 1, int l = 0, int r = n) {
    if (l == r) {
        T[p].sum += v;
        T[p].minpre = std::min(0, T[p].sum);
        return;
    }
    int mid = l + ((r - l) >> 1);
    if (pos <= mid) add(pos, v, p << 1, l, mid);
    else add(pos, v, p << 1 | 1, mid + 1, r);
    pushup(p);
}

int query(int ad, int p = 1, int l = 0, int r = n) {
    if (l == r) return (ad + T[p].sum >= 0 ? l : l - 1);
    int mid = l + ((r - l) >> 1);
    auto &L = T[p << 1], &R = T[p << 1 | 1];
    if (L.minpre + ad >= 0) return query(ad + L.sum, p << 1 | 1, mid + 1, r);
    else return query(ad, p << 1, l, mid);
}

void Run() {
    std::cin >> ac >> dr >> n;
    repeat(i, 0, n) bucket[i] = 0;

    repeat(i, 1, n) std::cin >> a[i];
    repeat(i, 1, n) std::cin >> d[i];
    repeat(i, 1, n) {
        s[i] = compute(i);
        if (s[i] <= n) bucket[s[i]]++;
    }

    build();

    std::cin >> m;
    while (m--) {
        int k, na, nd;
        std::cin >> k >> na >> nd;
        int oldv = compute(k);
        a[k] = na, d[k] = nd;
        int newv = compute(k);

        if (oldv <= n) add(oldv, -1);
        if (newv <= n) add(newv, 1);

        int t = query(0) + 1;
        t = (t > n ? n : t);

        std::cout << t << "\n";
    }
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    // std::cin >> t;
    while (t--) Run();
}

F

G

Codeforces
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。