算法学习专栏——Codeforces——Codeforces Round 934(Div.2)

CodeforcesRound934

A：Destroying Bridges

Problem - A - Codeforces

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 <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int t;

int main()
{   
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> t;
    while (t--) {
        int n, k, res = 0;
        cin >> n >> k;
        for (int i = n - 1; i >= 1; i--) {
            k -= i;
            if (k >= 0) res ++;
            else break;
        }
        cout << n - res << '\n';if (k >= n - 1) {
            cout << 1 << "\n";
        } else {
            cout << n << '\n';
        }
        
    }

    return 0;
}

B：Equal XOR

Problem - B - Codeforces

思路

​ 思路：这道题目可以这么思考，如果你想让两个区间的数的异或分别相同，是不是意味着两个区间异或之后等于0即可。同时题目还给了要求：每个子集为元素个数为2k，这就意味着两个子集出现数的个数一定是偶数，我们知道偶数个相同数的异或值为0，所以只要两个子集所有出现数的个数为 2 即可。

代码

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
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int> mp1, mp2;
    for (int i = 1, x; i <= n * 2; i ++) {
        cin >> x;
        if (i <= n) mp1[x] ++;
        else mp2[x] ++;
    }
    vector<int> a, b;
    for (auto [x, y] : mp1) {
        if (y == 2) {
            a.push_back(x);
            a.push_back(x);
            if ((int)a.size() == k * 2) break;
        }
    }
    for (auto [x, y] : mp2) {
        if (y == 2) {
            b.push_back(x);
            b.push_back(x);
            if ((int)b.size() == k * 2) break;
        }
    }
    if ((int)a.size() < k * 2) {
        for (auto [x, y] : mp1) {
            if(y == 2) continue;
            a.push_back(x);
            b.push_back(x);
            if ((int)a.size() == k * 2) break;
        }
    }
    for (auto i : a) cout << i << ' ';
    cout << endl;
    for (auto i : b) cout << i << ' ';
    cout << endl;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

C：MEX Game 1

Problem - C - Codeforces

思路

​ Alice第一次一定会拿只出现过一次的最小的数，这样可以保证答案最大，同理，Bob会拿第一次一定会拿只出现过一次的次小的数，这样可以保证答案最小。

代码

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
#include <iostream>
#include <map>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int t;
 
void solve(){
    int n;
    cin >> n;
    int i, j;
    map<int, int> mp; 
 
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
        mp[a[i]]++;
    }
 
    int mx = 0;
    while (mp[mx]) // 找到可能得最大数
        mx++;
 
    if (mx == 0) // =0则直接输出即可
    {
        cout << 0 << endl;
        return;
    }
 
    int t1 = -1, t2 = -1;
 
    for (i = 0; i < mx; i++)
    {
        if (mp[i] == 1 && t1 == -1)
    // 如果当前回合是Alice同时发现其中有一个数只有1个，果断拿走
        {
            t1 = i;
            continue;
        }
        if (mp[i] == 1 && t1 != -1 && t2 == -1)
    // 如果当前回合是Bob同时发现有一个数只有1个，果断删除，如此就确认答案
        {
            t2 = i;
            break;
        }
    }
 
    if (t2 != -1)
    {
        cout << t2 << endl;
    }
    else
    {
        cout << mx << endl;
    }
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> t;
    while (t--) {
        solve();
    }   

    return 0;
}