AcWing 第46场周赛

4396. 取石子

两个小朋友玩取石子游戏。

第一个小朋友面前有 n1 个石子,第二个小朋友面前有 n2 个石子。

两人轮流取自己面前的石子。

第一个小朋友先手,第二个小朋友后手。

第一个小朋友每轮次最多取 k1 个石子,最少取 1 个石子。

第二个小朋友每轮次最多取 k2 个石子,最少取 1 个石子。

率先取完自己面前石子的小朋友,视为失败。

请问,两个小朋友都采取最优策略的情况下,谁会获胜?

输入格式
一行,四个整数 n1,n2,k1,k2。

输出格式
如果第一个小朋友获胜,则输出 First,如果第二个小朋友获胜,则输出 Second。

数据范围
所有测试点满足 1≤n1,n2,k1,k2≤50。

输入样例1:
2 2 1 2
输出样例1:
Second
输入样例2:
2 1 1 1
输出样例2:
First

代码

谁最后取完谁获胜,所以每个人每次都取一个是最优解,等价于判断两个人的石子数量,谁多谁获胜

#include
int main() {
    int n1, n2, k1, k2;
    scanf("%d%d%d%d", &n1, &n2, &k1, &k2);
    if (n1 > n2) printf("First\n");
    else printf("Second\n");

    return 0;
}

4397. 卡牌

有 n 张卡牌,编号 1∼n。

每张卡牌的正面和背面都各有一个数字。

第 i 张卡牌的正面数字为 ai,背面数字为 bi。

初始时,所有卡牌都正面朝上,显示正面的数字。

现在,你可以将其中一些卡牌翻面,使其显示背面的数字,要求:

至少有 k 张卡牌保持正面朝上。
所有卡牌显示的数字之和尽可能小。
输出所有卡牌显示的数字之和的最小可能值。

输入格式
第一行包含两个整数 n,k。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含 n 个整数 b1,b2,…,bn。

输出格式
一个整数,表示所有卡牌显示的数字之和的最小可能值。

数据范围
前 6 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤2×105,0≤k≤n,1≤ai,bi≤104。

输入样例1:
3 1
5 4 6
3 1 5
输出样例1:
10
输入样例2:
5 3
3 4 7 10 3
4 5 5 12 5
输出样例2:
25

代码

贪心
C中存放的是对应位置的b-a的值,即反面的值减去正面的值,如果是负数的话就代表背面比较小,反转之后可以取得更小的值。
升序排序,只取小于零的值,等于0 可取可不取。
因为至少k张正面朝上,所以最多可以反转n-k张牌,遍历c的前n-k,如果大于0直接退出,否则就sum += c[i]

// Author: Changersh
// Problem: 卡牌
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4400/
// When: 2022-04-19 22:36:21
// 
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// 求背面减去正面的差值,排序一下,最多反转n-k个差值为负的
// 因为只有差值为负,才能使结果变得更小

#include 
#include 

using namespace std;
const int N = 200001;

int n, k, a[N], b[N], c[N], sum;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]), sum += a[i];
	for (int i = 0; i < n; i++)
		scanf("%d", &b[i]), c[i] = b[i] - a[i];
	
	sort(c, c + n);
	
	// n张牌,最少k张正面朝上,所以最多反转n-k张
	for (int i = 0; i < n - k; i++) {
		if (c[i] >= 0) break;
		else sum += c[i];
	}
	
	printf("%d", sum);
	return 0;
}

4398. 查询字符串

给定 n 个字符串 f1,f2,…,fn。

这些字符串两两不同。

下面给定 q 个询问。

其中,第 i 次询问给定一个字符串 si,你的任务是:

计算 f1∼fn 这 n 个字符串中,包含 si 作为子串的字符串的数量。
从 f1∼fn 这 n 个字符串中,任选一个包含 si 作为子串的字符串输出。
输入格式
第一行包含整数 n。

接下来 n 行,其中第 i 行包含字符串 fi。

再一行包含整数 q。

接下来 q 行,其中第 i 行包含字符串 si。

所有 fi 和 si 都只包含小写字母、数字以及 .。

输出格式
共 q 行,其中第 i 行输出第 i 个询问的答案。

首先输出 f1∼fn 这 n 个字符串中包含 si 作为子串的字符串的数量。

然后从 f1∼fn 这 n 个字符串中任选一个包含 si 作为子串的字符串输出。

如果这样的字符串不唯一,则输出任意合理字符串均可,如果这样的字符串不存在,则输出 -。

数据范围
前三个测试点满足 1≤n,q≤20。
所有测试点满足 1≤n≤10000,1≤q≤50000,1≤|fi|,|si|≤8。

输入样例:

4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st

输出样例:

1 contests
2 .test
1 test.
1 .test
0 -
4 test.

代码

刚开始使用的是暴力写法,直接遍历,然后不出意外的TLE了。
看了y总的讲解,然后用unordered_map来模拟。
每次输入一个字符串之后,求出这个字符串的所有子串,送入uset里面去重一下,然后再放入umap里面来计数,每个字符串对应的int 加一。
之后用第二个umap存储子串对应的字符串,以便输出结果。

最后输入要判断的字符串,输出其在第一个umap里面对应的int值(如果没有默认是0的)。
然后遍历hash的umap,判断是否包含该字符串,如果包含就输出对应的字符串,不包含就输出‘-’

// Author: Changersh
// Problem: 查询字符串
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4401/
// When: 2022-04-20 18:59:16
// 
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 


#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

// 使用map来进行哈希
int n, q;
unordered_map<string, int> cnt; // 存储最后输出的值
int main() {
	unordered_map<string, string> hash;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		unordered_set<string> S;
		string str;
		cin >> str;
		// 存储所有的子串(uset去重)
		for (int j = 0; j < str.size(); j++) {
			// 每次向后移一位,子串的起始位置也向后移
			string s;
			for (int k = j; k < str.size(); k++) {
				s += str[k];// 每次加一个字母,子串变长
				S.insert(s); // 存入所有的不重复的子串
			}
		}
		// 将子串存入cnt的umap里面,并且数量+1,并且记录一下包含该子串的字符串
		for (auto c : S) {
			cnt[c]++;
			hash[c] = str;
		}	
	}
	
	scanf("%d", &q);
	while (q--) {
		string str;
		cin >> str;
		printf("%d ", cnt[str]);
		if (hash.find(str) != hash.end()) 
			cout << hash[str] << "\n";
		else 
			cout << "-" << "\n";
	}
	
	return 0;
}



// int n, q;
// char s[10001][10], p[10], c[10];
// int main() {
	// scanf("%d", &n);
	// for (int i = 0; i < n; i++) scanf("%s", s[i]);
	// scanf("%d", &q);
	// for (int i = 0; i < q; i++) {
		// memset(p, 0, sizeof(p));
		// memset(c, 0, sizeof(c));
		// c[0] = '-';
		// scanf("%s", p);
		// bool flag = false;
		// int cnt = 0;
		// for (int j = 0; j < n; j++) {
			// if (strstr(s[j], p) != NULL) {
				// if (flag == false) {
					// flag = true;
					// strcpy(c, s[j]);
				// }
				// cnt++;
			// }
		// }
		// printf("%d ", cnt);
		// printf("%s\n", c);
	// }
	// return 0;
// }

你可能感兴趣的