Codeforces Round 932 (Div. 2)

Codeforces Round 932 (Div. 2) (A~D)

目录：A B C D

A题：Card Exchange

标签: 贪心策略（greedy）

题目大意

  • 给 n 张牌，每张牌上都写着一个数字，还有一个固定整数 k，可以多次进行下面的运算：
    • 从手牌中任意选择 k 张数字相同的牌
    • 将这些牌换成 k−1张牌，每张牌上数字任意
  • 最少有多少张牌？

思路

  • 分两种情况

    • 如果有 k 张牌相同那么可以将其变为 k - 1张与剩下牌相同的牌，那么被变的牌又有了k张，重复此操作，最终一定会剩下k - 1张牌不会再变化
    • 如果没有 k 张牌相同那么无法操作

  • 以 4 4 4 9 5 5 k = 3 为例

    将 4 4 4 变为 9 9 此时手牌为：9 9 9 5 5

    将 9 9 9 变为 5 5 此时手牌为：5 5 5 5

    将5 5 5 变为 5 5 此时手牌为：5 5 5

    再将5 5 5 变为5 5 此时手牌为：5 5

    无法再发生变化，可以证明这一定为最少手牌

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
#include <bits/stdc++.h>
using namespace std;
const int N = 110; 
int cnt[N];
void solve()
{
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= 100; i++)
		cnt[i] = 0;
	int flag = 0;
	for(int i = 0; i < n; i++)
	{
		int a; cin >> a;
		cnt[a] ++;
		if(cnt[a]>=k) flag = 1;
	}
	if(flag) cout << k -1 << endl;
	else cout << n << endl;
}
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0; 
}

B题：Rectangle Filling

标签: 构造算法（constructive algorithms）

题目大意

  • 有一个由白色和黑色方格组成的 n×m网格。在一次操作中，可以选择任意两个相同颜色的方格，并将它们之间的子方格中的所有方格都染成相同的颜色。

  • 例如如下染色方式：

e125ec62f7e594b2c76ea881028cd1d6c2680a1f

  • 问题：网格中所有方格的颜色是否可能相同？

思路

  • 结论：假设全部染成白色：那么在第一行，第一列，最后一行，最后一列一定都含有白色块

  • 解释：

    • 必须：如果第一列不含白色块，那么第一行全为黑色，如何染色也不可以将第一行全变为白色，最后一行，第一列，最后一行同理
    • 为什么能：第一行和最后一行含有白色，那么可以用这两个点染色，将包括的几列全变为白色（至少有了一列全是白色)

    再使用这一列的白色，和第一列的白色染色，和最后一列的白色染色，之后一定可以全部变为白色。

  • 黑色同理

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
string s[N];
void solve(){
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> s[i];
	bool a[4] = {0}, b[4] = {0};
	// 判断第一行，第一列，最后一行，最后一列是否有白色或黑色 
	for (int i = 0; i < n; i++) if (s[i][0]=='W') a[0] = 1; else b[0] = 1;
	for (int i = 0; i < n; i++) if (s[i][m-1]=='W') a[1] = 1; else b[1] = 1;
	for (int i = 0; i < m; i++) if (s[0][i]=='W') a[2] = 1; else b[2] = 1;
	for (int i = 0; i < m; i++) if (s[n-1][i]=='W') a[3] = 1; else b[3] = 1;
    
	cout << ((a[0]&&a[1]&&a[2]&&a[3]||b[0]&&b[1]&&b[2]&&b[3])?"YES\n":"NO\n");
}
int main(){
	int T; cin >> T;
	while (T--)
		solve();
    return 0;
}

C题：Everything Nim

标签: 博弈论（games）贪心策略（greedy）

题目大意

  • 爱丽丝和鲍勃正在玩一个关于 n 堆石头的游戏。轮到每个玩家时，他们都会选择一个正整数 k，这个正整数最多等于最小的非空堆的大小，然后从每个非空堆中一次性取出 k 个石子。第一个无法下棋的棋手(因为所有棋子都是空的)输。
  • 既然爱丽丝先下，那么如果双方都以最佳方式下棋，谁会赢呢？

思路

  • 由于每次操作剩余所有数都是被减掉相同的值，那么可以将其转换为拿石子问题

  • 转换方式：去重，从小到大排序，找到两两之间的差值。

  • 然后问题就转化为了，从以第一堆到最后一堆的顺序拿石子的问题，注意：与nim经典问题的区别是这题固定了拿石子的顺序 (因为越大的数越后被减完)

  • 例如第六个样例：5 7 2 9 6 3 3 2

    去重排序：2 3 5 6 7 9

    取差值： 2 1 2 1 1 2 （第一个数和0取差值)

    转换为了两人轮流从第一堆到最后一堆按顺序拿一定数量的石子，谁先操作最后一堆谁赢 (直接将最后一堆拿光光第二人无法操作)

  • 从后往前看：谁先操作最后一堆谁赢

    • 倒数第二堆不为1时，谁先操倒数第二堆谁就能决定谁先操作最后一堆（选择拿完或留一个)
    • 倒数第二推为1时，谁先操作倒数第二堆，谁就后操作最后一堆
    • 重复此推断，倒数第三堆，倒数第四堆……，一直到第一堆

  • 剩下看代码 （有注释)

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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int n; cin >> n;
    // set 默认去重，排序
	set<int> st;
	for(int i = 0; i < n; i++)
	{
		int a; cin >> a;
		st.insert(a);
	}	
    // 将计算后的差值存在vector里
	vector<int> v;
	int la = 0;
	for(int a : st)
	{
	    v.push_back(a - la);
	    la = a;
	}
    // 谁先操作最后一堆谁赢，如果只有一堆Alice(先手)赢
	bool flag = true;
	for(int i = v.size() - 2; i >= 0; i--)
		if(v[i] == 1) flag = !flag;	// 如果遇到 1 那么先操作变为后操作下一堆
		else flag = true;			// 如果大于 1 那么可以决定，谁先操作，谁后操作下一堆
		
	cout << (flag? "Alice" : "Bob") << endl;
}
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0; 
}

D题：Missing Subsequence Sum

标签: 构造算法（constructive algorithms）

题目大意

  • 给你两个整数 n 和 k。求一个大小最多为 25 的非负整数序列 a ，使得下列条件成立。
    • 没有和为 k 的 a 的子序列。
    • 对于所有 1 ≤ v ≤ n 中的 v ≠ k 存在一个和为 v 的 a 的子序列。
  • 如果 b 可以从 a 中删除几个(可能是零个或全部)元素，而不改变其余元素的顺序，那么序列 b 就是 a 的子序列。例如 5,2,3 是 1,5,7,8,2,4,3 的子序列。
  • 可以证明，在给定的约束条件下，解总是存在的。

思路

  • 构造题答案肯定不为一，这里数下我的构造方式
  • 以k = 20 为例：
    • 首先构造数组a为 1 2 4 8 5 (1 2 可以构成13的所有数，加上4可以构成17的所有数，再加上8可以构成1~15的所有数…..)最后加5可以构造1 ~ k-1的所有数，这样就构造出了对于所有 1 ≤ v ≤ k-1 存在一个和为 v 的 a 的子序列。
    • 然后加入两个k + 1，加入一个2 * k + 1 然后其余数添加 (2 * k + 1)的2次幂 （同理：1 2 4 8…）
  • 证明没有和为 k 的 a 的子序列：第一步构造的数的组合不了 k ，后面的数都是大于k的，所有最终没有和为 k 的 a 的子序列
  • 证明对于所有 1 ≤ v ≤ n 中的 v ≠ k 存在一个和为 v 的 a 的子序列：不难看出在构造的数组中再加入k，去掉一个k-1，就一定能组成所有数，后续可以证明不存在一个数只能使用新加的 k 去构造
  • 证明不会操作超过25次：2的20次方为1048576 > 1e6

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 10010, mod = 998244353; 
void solve()
{
	int n, k, l = 1;
	vector<int> v; 
	cin >> n >> k;
	while(2 * l - 1 < k)
	{
		v.push_back(l);
		l *= 2;
	} 
	int t = l - 1;
	v.push_back(k - t - 1);
	int la = k + 1;
	v.push_back(la); v.push_back(la);
	la = 2 * k + 1;
	while(v.size() <= 25)
	{
		v.push_back(la);
		la <<= 1;
		if(la > 1e6) break;
	}
	cout << v.size() << endl;
	for(int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;
}
signed main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　⊂⊃〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
          __   _,--="=--,_   __
         /  \."    .-.    "./  \
        /  ,/  _   : :   _  \/` \
        \  `| /o\  :_:  /o\ |\__/
         `-'| :="~` _ `~"=: |
            \`     (_)     `/
     .-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.
 )  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				)
 )                                     (
'---------------------------------------'
*/
算法刷题 > codeforces
#算法竞赛
Codeforces Round 932 (Div. 2)
https://leaf-domain.gitee.io/2024/04/28/cf-div2-941/
作者
叶域
发布于
2024年4月28日
许可协议