目录：A B C
标签: 数学（math）
题目大意
思路
- 删除 1号点与其他点相连的 n - 1边后一号点，就到达不了其他任何点。
- 如果删除的边数 k < n - 1那么无论怎么删，1号点都可以通过与其相连的一条边到达所有点。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #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;
}
|
标签: 位掩码（bitmasks）构造算法（constructive algorithms）
题目大意
- 给你一个长度为 2n 的数组 a ，它由 1到 n 的每个整数组成，每个整数包含2次。同时给你一个整数 k ( 1 ≤ k ≤ ⌊$\frac{(n}{2}$⌋)
- 找出两个长度分别为 2k 的数组 l 和 r ，使得：
-
-
-
- 答案不为一
思路
- 每个数字包含两次，要么在同一边，要么一边一个。
- 相同两个数异或为0。
- l r现选择两个相同的数都在一边相同的使其异或为0，不够的就加上一边一个相同值。
AC代码
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
| #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;
}
|
标签: 构造算法（constructive algorithms）博弈论（games）
题目大意
- 俩个人在长度为 n 的数组 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代码
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
| #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