Codeforces Round 934 (Div. 2)

发表于 分类于 ，

Codeforces Round 934 (Div. 2)

Complete problemset

A. Destroying Bridges

题意

有 $n$ 个岛屿，编号为 $1, 2, \ldots, n$ 。最初，每对岛屿都由一座桥连接。因此，一共有 $\frac{n (n - 1)}{2}$ 座桥。

Everule 住在 $1$ 岛上，喜欢利用桥梁访问其他岛屿。Dominater 有能力摧毁最多 $k$ 座桥梁，以尽量减少 Everule 可以使用（可能是多座）桥梁到达的岛屿数量。

如果 Dominater 以最佳方式摧毁桥梁，求 Everule 可以访问的岛屿（包括岛屿 $1$ ）的最少数量。

思路

至少摧毁n-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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n, k;
    cin >> n >> k;
    if (k>=n-1) {
        cout << "1\n";
    } else {
        cout << n << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B. Equal XOR

题意

给你一个长度为 $2n$ 的数组 $a$ ，它由 $1$ 到 $n$ 的每个整数组成，每个整数包含次。

同时给你一个整数 $k$ ( $1 \leq k \leq \lfloor \frac{n}{2} \rfloor $ )。

你需要找出两个长度分别为 $\mathbf{2k}$ 的数组 $l$ 和 $r$ ，使得：

  • $l$ 是 $[a_1, a_2, \ldots a_n]$ 的子集 $^\dagger$ 。
  • $r$ 是 $[a_{n+1}, a_{n+2}, \ldots a_{2n}]$ 的子集
  • $l_1 \oplus l_2 \oplus \ldots \oplus l_{2k} = r_1 \oplus r_2 \oplus \ldots \oplus r_{2k}$，$\oplus $是按位异或。

可以证明，至少有一对 $l$ 和 $r$ 总是存在的。如果有多个解，可以输出其中任意一个。

$^\dagger$ 序列 $x$ 是序列 $y$ 的子集，如果 $x$ 可以通过删除 $y$ 中的几个元素（可能一个元素也没有或全部元素）并按任意顺序重新排列而得到。例如， $[3,1,2,1]$ 、 $[1, 2, 3]$ 、 $[1, 1]$ 和 $[3, 2]$ 是 $[1, 1, 2, 3]$ 的子集，但 $[4]$ 和 $[2, 2]$ 不是 $[1, 1, 2, 3]$ 的子集。

思路

我们优先在左边将出现两次的元素选取至多2k个，然后在右边将出现两次的选取至多2k个。

如果两边元素还不够，就选取两边出现各一次的元素。

代码

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>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n, k;
    cin >> n >> k;
    vector<int> a(2*n);
    for (auto& i:a) cin >> i;
    vector<int> c(n+1);
    for (int i=0; i<n; i++) {
        c[a[i]]++;
    }
    // cout << c << endl;
    int p = 0;
    vector<int> l, r;
    for (int i=1; i<=n; i++) {
        if (l.size() == 2*k) continue;
        if (c[i] == 2) {
            l.push_back(i);
            l.push_back(i);
        }
    }
    for (int i=1; i<=n; i++) {
        if (r.size() == 2*k) continue;
        if (c[i] == 0) {
            r.push_back(i);
            r.push_back(i);
        }
    }
    for (int i=1; i<=n; i++) {
        if (l.size() == 2*k) continue;
        if (c[i] == 1) {
            l.push_back(i);
            r.push_back(i);
        }
    }
    for (int i:l) {
        cout << i << " ";
    } cout << "\n";
    for (int i:r) {
        cout << i << " ";
    } cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C. MEX Game 1

题意

爱丽丝和鲍勃在大小为 $n$ 的数组 $a$ 上进行另一场博弈。爱丽丝从一个空数组 $c$ 开始。双方轮流下棋，爱丽丝先开始。

轮到爱丽丝时，她从 $a$ 中选取一个元素，将该元素追加到 $c$ 中，然后从 $a$ 中删除。

轮到鲍勃时，他从 $a$ 中选取一个元素，然后从 $a$ 中删除。

当数组 $a$ 为空时，游戏结束。游戏的分数定义为 $c$ 的 MEX $^\dagger$ 。爱丽丝希望最大化得分，而鲍勃希望最小化得分。如果双方都以最佳状态进行游戏，求游戏的最终得分。

$^\dagger$ 整数数组的 $\operatorname{MEX}$ （最小不等式）定义为数组中不出现的最小非负整数。例如

  • $[2,2,1]$ 的 MEX 是 $0$ ，因为 $0$ 不属于数组。
  • $[3,1,0,1]$ 的MEX是 $2$ ，因为 $0$ 和 $1$ 属于数组，而 $2$ 不属于数组。
  • $[0,3,1,2]$ 的 MEX 是 $4$ ，因为 $0$ 、 $1$ 、 $2$ 和 $3$ 属于数组，而 $4$ 不属于数组。

思路

如果mex是x那么我们需要将0到x-1都选一遍。

0到x-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
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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n;
    cin >> n;
    vector<int> c(n);
    for(int i=0; i<n; i++) {
        int x;
        cin >> x;
        c[x]++;
    }
    int c1 = 0;
    for (int i=0; i<n; i++) {
        if (c[i] == 0) {
            cout << i << "\n";
            return ;
        }
        if (c[i] == 1) c1++;
        if (c1 == 2) {
            cout << i << "\n";
            return ;
        }
    }
    cout << n << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D. Non-Palindromic Substring

题意

如果至少存在一个长度为 $k$ 的子串不是回文，则称字符串 $t$ 为 $k$ -good。在字符串 $t$ 是 $k$-good的情况下，$f(t)$ 表示所有 $k$ 的值之和。

给你一个长度为 $n$ 的字符串 $s$ 。您需要回答以下问题中的 $q$ 个：

  • 给定 $l$ 和 $r$ ( $l < r$ ), 求 $f(s_ls_{l + 1}\ldots s_r)$ 的值。

思路

如果t是k-good，那么t的所有长度为k的子串至少有一个是非回文。我们可以想一想所有长度为k的子串是回文的情况。

如果k是偶数，那么显然t的所有字符会相等。答案是0。

如果k是奇数，那么t是一个形如”abababa…”的交替串。奇数串的贡献是0，偶数串的贡献通过子串长度可知，假设长度为len，那么有$\lfloor \frac{len}{2} \rfloor$个串，长度分别是$2,4,6,8,…,\lfloor \frac{len}{2} \rfloor$，总贡献是$(\lfloor \frac{len}{2} \rfloor+1)\lfloor \frac{len}{2} \rfloor$

如果不是交替串，所有除了长度为1的不同长度子串都有贡献，$2+3+4+…+len-1$。最后需要判断t本身是否为回文，非回文则贡献len。

判断回文，可双重字符串哈希。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

struct SHash {
    // string s[] index from 0 to n-1
    // B[i] = BASE^i
    // s[i...j] = s[0...j] - s[0...i-1]
    // hash s[0...i-1] = H[i] = s[0]*B[i-1]+s[1]*B[i-2]+...+s[i-1]*B[0]
    // hash s[0...j] = H[j+1] = s[0]*B[j]+s[1]*B[j-1]+...+s[j]*B[0]
    // hash s[i...j] = H[j+1] - H[i]*B[j-i+1]
    // hash s[i...j-1] = H[j] - H[i]*B[j-i]
    vector<ull> H, B;
    ull len, base, mod;
    SHash(string& s, ull base = 173, ull mod = 998244353)
        : H(s.size() + 1, 0),
          B(s.size() + 1, 1),
          len(s.size()),
          base(base),
          mod(mod) {
        for (int i = 1; i <= len; i++) {
            H[i] = (H[i - 1] * base % mod + s[i - 1]) % mod;
            B[i] = B[i - 1] * base % mod;
        }
    }
    ull hash(int l, int r) {  // hash of s[l...r-1]
        return (H[r] - H[l] * B[r - l] % mod + mod) % mod;
    };
};

void sol() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s = '#'+s+'#';
    auto rs = s;
    reverse(rs.begin(), rs.end());
    SHash h1(s), h2(rs); // s[l,r) == rs[n-r+2, n-l+2)
    SHash h3(s, 191, 1e9+7), h4(rs, 191, 1e9+7);
    vector<vector<int>> p1(n+1, vector<int>(26)), p2(n+1, vector<int>(26));
    for (int i=1; i<=n; i++) {
        int c = s[i]-'a';
        p1[i] = p1[i-1];
        p2[i] = p2[i-1];
        if (i%2) p1[i][c]++;
        else p2[i][c]++;
    }
    // cout << p1 << "\n";
    // cout << p2 << endl;
    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        ll len = y-x+1;
        ll cnt1, cnt2;
        int c1 = s[y-1]-'a', c2 = s[y]-'a';
        if (y%2) {
            cnt1 = p1[y][c2]-p1[x-1][c2];
            cnt2 = p2[y-1][c1]-p2[x-1][c1];
        } else {
            cnt1 = p2[y][c2]-p2[x-1][c2];
            cnt2 = p1[y-1][c1]-p1[x-1][c1];
        }
        
        // cout << cnt1 << " " << cnt2 << endl;
        if (cnt1+cnt2 == len) {
            if (s[y] == s[y-1]) cout << "0\n";
            else { // 奇偶交替，不存在奇数长度子串贡献
                ll b = len/2; // 对于2,4,6,8,,,等长度子串 存在非回文
                cout << b*(b+1)/2*2 << "\n";
            }
        } else {
            cout << (len-2)*(2+len-1)/2 + ( h1.hash(x, y+1) == h2.hash(n-y+1, n-x+2) && h3.hash(x, y+1) == h4.hash(n-y+1, n-x+2) ? 0 : len) << "\n";
        }
    }



}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

E. Tree Compass

题意

给你一棵树，树上有 $n$ 个顶点，编号为 $1, 2, \ldots, n$ 。最初，所有顶点都被涂成白色。

您可以执行以下两步操作：

  1. 选择顶点 $v$ ( $1 \leq v \leq n$ ) 和距离 $d$ ( $0 \leq d \leq n-1$ )。
  2. 对于所有顶点 $u$ ( $1 \leq u \leq n$ ) 都与 $\text{dist}^\dagger(u,v)=d$ 一致，将 $u$ 着色为黑色。

构造一个操作序列，用尽可能少的操作次数将树中的所有节点涂成黑色。可以证明，我们总是可以用最多 $n$ 次的操作来实现这一目的。

$^\dagger$ $\text{dist}(x, y)$ 表示树上顶点 $x$ 和 $y$ 之间（唯一的）简单路径上的边的数量。

思路

先找直径d，然后从直径的中心进行操作。

如果是一个中心c，d必然是偶数，在c上操作从0到d/2共d/2+1次即可。

如果是两个中心c1和c2，我们从两个中心操作floor(d/2), floor(d/2)-2, floor(d/2)-4, … 直到非负。一个中心操作距离为x，那么另一个中心就不需要操作x-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
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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n;
    cin >> n;
    vector<vector<int>> g(n+1);
    vector<vector<int>> d(3, vector<int>(n+1));
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int c = 0;
    function<void(int,int,int)> dfs = [&](int u, int fa, int o) {
        for (int v : g[u]) {
            if (v == fa) continue;
            d[o][v] = d[o][u] + 1;
            if (d[o][v] > d[o][c]) c = v;
            dfs(v, u, o);
        }
    };
    dfs(1, 0, 0);
    dfs(c, 0, 1);
    dfs(c, 0, 2);
    // cout << d << endl;
    // d[2][c] 直径
    vector<int> h; // 某条直径上的中心点,直径奇数一个,偶数两个
    for (int i=1; i<=n; i++) {
        if (d[1][i]+d[2][i] == d[2][c] && abs(d[1][i]-d[2][i]) == d[2][c]%2) h.push_back(i);
    }
    if(h.size() == 1) {
        cout << d[2][c]/2+1 << "\n";
        for (int i=0; i<=d[2][c]/2; i++) {
            cout << h[0] << " " << i << "\n";
        }
    } else {
        vector<pair<int,int>> p;
        for (int i=d[2][c]/2; i>=0; i-=2) {
            p.emplace_back(h[0], i);
            p.emplace_back(h[1], i);
        }
        cout << p.size() << "\n";
        for (auto [x, y]:p) {
            cout << x << " " << y << "\n";
        }
    }
    
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

F1. Counting Is Fun (Easy Version)

题意

思路

代码

1
2


F2. Counting Is Fun (Hard Version)

题意

思路

代码

1
2