Contest Notes

Codeforces Round 994 (Div. 2)

比赛链接

Problems AC Note
A. MEX Destruction ○
B. pspspsps ○
C. MEX Cycle ○ 构造
D. Shift + Esc ○ DP
E. Broken Queries ⊕ 交互、二分
F. MEX OR Mania ⊕ 启发式合并

A

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
void solve() {
    int n = read();
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    int ans = 2;
    int l = 0;
    while (l + 1 <= n and a[l + 1] == 0) l++;
    int r = n + 1;
    while (r - 1 >= 1 and a[r - 1] == 0) r--;

    bool f = 1;
    for (int i = l + 1; i < r; i++) {
        if (a[i] == 0) {
            f = 0;
            break;
        }
    }

    if (f) ans = 1;
    else ans = 2;

    if (l == n and r == 1) ans = 0;

    cout << ans << '\n';
}

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();
    string s;
    cin >> s;
    bool ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i] == 's' and i != 0 and
                s[j] == 'p' and j != n - 1) {
                ans = 0;
                break;
            }
        }
    }

    cout << (ans ? "YES" : "NO") << '\n';
}

C

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
int getmex(const vector<int>& a) {
    std::unordered_set<int> s(a.begin(), a.end());
    int mex = 0;
    while (s.find(mex) != s.end()) {
        mex++;
    }
    return mex;
}

void solve() {
    int n = read();
    int x = read(), y = read();

    vector<vector<int>> g(n + 1);
    
    for (int i = 1; i <= n; i++) {
        int prev = (i == 1) ? n : i - 1;
        int next = (i == n) ? 1 : i + 1;
        g[i].eb(prev);
        g[i].eb(next);
    }
    
    bool f = false;
    for (auto v : g[x]) {
        if(v == y) {
            f = true;
            break;
        }
    }
    if (!f) g[x].eb(y), g[y].eb(x);
    
    vector<int> a(n + 1);
    
    std::queue<int> q;
    vector<bool> inq(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        q.ep(i);
        inq[i] = true;
    }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        vector<int> t;
        for (auto v : g[u]) {
            t.push_back(a[v]);
        }
        int mex = getmex(t);
        
        if (a[u] != mex) {
            a[u] = mex;
            for (auto v : g[u]) {
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
    
    f = 1;
    for (int i = 1; i <= n; i++) {
        vector<int> t;
        for(auto v : g[i]) {
            t.push_back(a[v]);
        }
        int mex = getmex(t);
        if (a[i] != mex){
            f = 0;
            break;
        }
    }
    
    if (!f) {
        cout << "NO\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    } 
}

D

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

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            a[i][j] = read();
        }
    }
    
    vector dp(m, vector<int>(m, INF));

    for (int s = 0; s < m; s++) {
        dp[0][s] = k * s + a[0][s % m];
    }

    for (int j = 1; j < m; j++) {
        for (int s = 0; s < m; s++) {
            if (dp[j - 1][s] + a[0][(j + s) % m] < dp[j][s]) {
                dp[j][s] = dp[j - 1][s] + a[0][(j + s) % m];
            }
        }
    }

    for (int i = 1; i < n; i++) {

        vector ndp(m, vector<int>(m, INF));
        vector pre(m, INF);

        for (int j = 0; j < m; j++) {
            for (int s = 0; s < m; s++) {
                if (dp[j][s] < pre[j]) {
                    pre[j] = dp[j][s];
                }
            }
        }

        for (int s = 0; s < m; s++) {
            for (int j = 0; j < m; j++) {
                int val = a[i][(j + s) % m];
                if (j == 0) {
                    ndp[j][s] = min(ndp[j][s], pre[j] + k * s + val);
                } else {
                    ndp[j][s] = min({
                        ndp[j][s], 
                        pre[j] + k * s + val, 
                        ndp[j - 1][s] + val
                    });
                }
            }
        }

        dp = std::move(ndp);
    }
        
    int ans = INF;
    for (int s = 0; s < m; s++) {
        ans = min(ans, dp[m - 1][s]);
    }
    cout << ans << '\n';
}

E

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

    auto ask = [&](int l, int r) {
        cout << "? " << l << " " << r << "\n";
        fflush(stdout);
        int res; cin >> res; fflush(stdout);
        return res;
    };

    int ans = 0;

    if (ask(1, n / 4) != ask(n / 4 + 1, n / 2)) {
        // 1 in [1, n / 2]
        // sum[1, n / 2] = 1
        // sum(n / 2, n] = 0
        if (ask(1, n / 2) == 1) {
            // k > n / 2
            for (int l = n / 2 + 1, r = n - 1; l <= r; ) {
                int mid = l + r >> 1;
                if (ask(1, mid) == 0) {
                    ans = mid, r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        } else {
            // k <= n / 2
            for (int l = 2, r = n / 2; l <= r; ) {
                int mid = l + r >> 1;
                if (ask(n / 2 + 1, n / 2 + mid) == 1) {
                    ans = mid, r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
    } else {
        // 1 in (n / 2, n]
        // sum[1, n / 2] = 0
        // sum(n / 2, n] = 1
        if (ask(1, n / 2) == 0) {
            // k > n / 2
            for (int l = n / 2 + 1, r = n - 1; l <= r; ) {
                int mid = l + r >> 1;
                if (ask(n - mid + 1, n) == 0) {
                    ans = mid, r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            
        } else {
            // k <= n / 2
            for (int l = 2, r = n / 2; l <= r; ) {
                int mid = l + r >> 1;
                if (ask(1, mid) == 1) {
                    ans = mid, r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
    }

    cout << "! " << ans << "\n";
    fflush(stdout);
}

F

如果整数序列 $b_1, b_2, \ldots, b_n$ 为 $\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1$ ，则该序列为有效序列。此处， $\operatorname{mex(c)}$ 表示集合 $c$ 的 MEX $^{\text{∗}}$ ，而 $|$ 是 按位或 运算符。

Shohag 有一个整数序列 $a_1, a_2, \ldots, a_n$ 。他将对 $a$ 执行以下 $q$ 更新：

  • $i$ $x$ — 将 $a_i$ 增加 $x$ 。

每次更新后，帮助他找到 $a$ 中最长的好子数组 $^{\text{†}}$ 的长度。

$1 \le n, q \le 10^5$

$0 \le a_i \le n$

$1 \le i, x \le n$

两个性质

$\operatorname{mex}(S) \le \max(S) + 1$

$\max(S) \le \operatorname{or}(S)$

$ \operatorname{mex}(S) = \max(S) + 1 $

$ \max(S) = \operatorname{or}(S) $

可以枚举 $k$，限制转化为 $[0, 2^k)$ 每个数刚好出现一次。

题目的操作是只增不减，那么断点会变得越来越多。启发式分裂好像有点麻烦，直接离线反着操作，变成启发式合并，维护下信息。

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
102
103
struct DSU {
    std::vector<int> f;
    DSU() {}
    DSU(int n) { init(n); }
    void init(int n) { f.resize(n), std::iota(f.begin(), f.end(), 0); }
    int find(int x) { return f[x] != x ? f[x] = find(f[x]) : x; }
};
// mex(S) = or(S) + 1
// mex(S) <= max(S) + 1
// max(S) <= or(S) = mex(S) - 1
// max(S) + 1 <= mex(S)

// mex(S) = max(S) + 1
// max(S) = or(S)
void solve() {
    int n = read();
    int m = read();

    vector<int> a(n);
    vector<std::array<int, 2>> qry(m);
    for (auto &x : a) x = read();
    for (auto &[i, x] : qry) i = read() - 1, x = read();

    // for (auto [i, x] : qry) a[i] += x;

    DSU dsu(n);
    vector<int> L(n), R(n);
    vector<int> ans(m);

    for (int k = 0; k <= 30; k++) {
        int tar = 1LL << k;
        int lim = (1LL << k) - 1;
        
        for (auto [i, x] : qry) a[i] += x;

        dsu.init(n);
        std::iota(L.begin(), L.end(), 0);
        std::iota(R.begin(), R.end(), 0);
        vector<std::map<int, int>> mp(n);
        std::multiset<int> s;
        s.ep(0);

        auto myMerge = [&](int x, int y) -> bool {
            x = dsu.find(x), y = dsu.find(y);
            if (x == y) return false;
            if (mp[x].size() < mp[y].size()) swap(x, y);
            if (mp[x].size() == tar) s.erase(s.find(R[x] - L[x] + 1));
            if (mp[y].size() == tar) s.erase(s.find(R[y] - L[y] + 1));

            dsu.f[y] = x;
            for (auto [num, cnt] : mp[y]) {
                mp[x][num] += cnt;
                // cerr << "!";
            }

            mp[y].clear();

            L[x] = min(L[x], L[y]);
            R[x] = max(R[x], R[y]);

            if (mp[x].size() == tar) s.ep(R[x] - L[x] + 1);
            return true;
        };

        for (int i = 0; i < n; i++) {
            if (a[i] > lim) continue;

            if (!k) s.ep(1);
            mp[i][a[i]] = 1;
            if (i > 0 and a[i - 1] <= lim) myMerge(i - 1, i);
        }

        for (int i = m - 1; i >= 0; i--) {
            ans[i] = max(ans[i], *--s.end());

            auto [p, x] = qry[i];
            auto &val = a[p];
            val -= x;

            if (i == 0 or val > lim) continue;

            int fp = dsu.find(p);

            if (val + x <= lim) {
                if (!--mp[fp][val + x]) {
                    if (mp[fp].size() == tar) {
                        s.erase(s.find(R[fp] - L[fp] + 1));
                    }
                    mp[fp].erase(val + x);
                }
            }
            mp[fp][val]++;
            if (mp[fp].size() == tar and mp[fp][val] == 1) {
                s.ep(R[fp] - L[fp] + 1);
            }
            if (p - 1 >= 0 and a[p - 1] <= lim) myMerge(p - 1, p);
            if (p + 1 < n and a[p + 1] <= lim) myMerge(p + 1, p);
        }
    }

    for (auto x : ans) printf("%d\n", x);
}

Codeforces Round 994 (Div. 2)

https://tosakaucw.github.io/codeforces-round-994-div-2/

Author

TosakaUCW

Posted on

2024-12-21

Updated on

2025-01-04

Licensed under

#

Comments

Catalogue

×