Codeforces Round 934 (Div. 2) (A~C)

本文主要是介绍Codeforces Round 934 (Div. 2) (A~C)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codeforces Round 934 (Div. 2) (A~C)

目录：A B C

A题：Destroying Bridges

标签: 数学（math）

题目大意

• n个点，编号1~n，两两相连共$\frac{(n(n-1))}{2}$ 条边。
• 删除 k 个边，使1号点，可以到达的点尽可能少，问最少为多少。

思路

• 删除 1号点与其他点相连的 n - 1边后一号点，就到达不了其他任何点。
• 如果删除的边数 k < n - 1那么无论怎么删，1号点都可以通过与其相连的一条边到达所有点。

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{int n, k;cin >> n >> k;if(k >= n - 1) cout << 1 << endl;else cout << n << endl;
}   
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

B题：Equal XOR

标签: 位掩码（bitmasks）构造算法（constructive algorithms）

题目大意

• 给你一个长度为 2n 的数组 a ，它由 1到 n 的每个整数组成，每个整数包含2次。同时给你一个整数 k ( 1 ≤ k ≤ ⌊$\frac{n}{2}$⌋)
• 找出两个长度分别为 2k 的数组 l 和 r ，使得：
• • l 是 a₁, a₂, … a_n的子集 。
• • r 是 a_n+1, a_n+2, …a_2n的子集
• • l 中元素的异或和等于 r 中元素的异或和
• 答案不为一

思路

• 每个数字包含两次，要么在同一边，要么一边一个。
• 相同两个数异或为0。
• l r现选择两个相同的数都在一边相同的使其异或为0，不够的就加上一边一个相同值。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int a[N<<1], cnt[N], l[N], r[N];
vector<int> b, c, d;
void solve()
{int n, k;cin >> n >> k;for(int i = 1;i <= n; i++) cnt[i] = 0;b.clear(), c.clear(), d.clear();for(int i = 1;i <= (n<<1); i++)cin >> a[i];for(int i = 1;i <= n; i++)cnt[a[i]]++;for(int i = 1;i <= n; i++)if(cnt[i] == 1) d.push_back(i);else if(cnt[i] == 2) b.push_back(i);else if(cnt[i] == 0) c.push_back(i);int num = 1;for(int i = 0;i<b.size()&&num<(k<<1); num += 2, i++){l[num] = l[num+1] = b[i];r[num] = r[num+1] = c[i];}for(int i=0;num<=(k<<1);num++,i++) l[num]=r[num]=d[i];for(int i = 1;i <= (k<<1); i++) cout << l[i] << " ";cout << endl;for(int i = 1;i <= (k<<1); i++) cout << r[i] << " ";cout << endl;
}
int main()
{int T; cin >> T;while(T--)solve(); return 0;
}

C题：MEX Game 1

标签: 构造算法（constructive algorithms）博弈论（games）

题目大意

• 俩个人在长度为 n 的数组 a上进行一场博弈。
• • 第一个人每轮将 a 中的一个数放到 b 中。
• • 第二个人每轮删除 a 中一个数
• 第一个人需要将b的 MEX 值最大化。
• 两个人都是最优方式操作，第一人先操作，问：最大MEX为多少。
• 整数数组的 MEX (最小不等式)定义为数组中不出现的最小非负整数。

思路

• 第一个人先将1~n 中第二个只存在一次的数放入 n 中。例如：5 0 0 1 1 2 3 3 4 中的 4 (第一个是2)
• 如上样例第一个人先手将 2 放入 b 中
• 然后只要第二个人删除 4 前面任何数，第一个人就将存在的另一个数放入b中，所以最终：MEX(b) = 4。
• 不会有更大的情况了，例如如果MEX等于5那么前面必须包含2 和 4，第一个人先手拿2第二个人反手删4反之亦然。

方法一、AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int cnt[N];
void solve()
{int n; cin >> n;for(int i = 0; i <= n; i++)cnt[i] = 0;for(int i = 1; i <= n; i++){int a; cin >> a;cnt[a]++;} int res = 0;for(int i = 0; i <= n; i++){if(cnt[i] == 1) res ++;if(cnt[i] == 0 || res == 2){cout << i << endl;return;		}} 
}   
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

logo

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　⊂⊃〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//

/*__   _,--="=--,_   __/  \."    .-.    "./  \/  ,/  _   : :   _  \/` \\  `| /o\  :_:  /o\ |\__/`-'| :="~` _ `~"=: |\`     (_)     `/.-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.)  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				))                                     (
'---------------------------------------'
*/

这篇关于Codeforces Round 934 (Div. 2) (A~C)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---