2024睿抗机器人开发者大赛CAIP编程赛个人题解_睿抗题解

T1：热?热?热?

题目描述：

热?热?热?……最近热得打的字都出汗了！

幸好某连锁餐厅开启了气温大于等于 35 度即可获得一杯免费雪碧的活动。但不知为何，在每个星期四的时候，这个活动会暂停一天……

现在给定连续的若干天的气温情况以及给定的第一天是星期几，请你算出有多少天你可以喝到免费的雪碧，又有多少天是因为星期四而导致你喝不到雪碧的。

输入格式:
输入第一行是两个正整数 N, W (1≤N≤50,1≤W≤7)，表示给定连续的 N 天，下面给定的第一天是星期 W（7 等于星期天）。

接下来的一行给出 N 个用一个空格隔开的、小于 60 的整数，第 i 个数表示第 i 天的温度。保证温度大于等于 -273 度。

输出格式:
输出两个数，第一个是你能喝到免费雪碧的天数，第二个是你本来能喝到免费雪碧、但因为是星期四而无法喝到的天数。

输入样例:
15 3
33 35 34 36 37 40 32 31 30 29 28 29 33 38 40

输出样例:
5 1

思路：直接模拟就好

代码：

#include<bits/stdc++.h>
 
using namespace std;
 
int n, w;
 
int main()
{
	cin >> n >> w;
	
	int a1 = 0, a2 = 0;
	int x;
	for (int i = 0; i < n; ++ i)
	{
		cin >> x;
		
		if(x >= 35)
		{
			if(w == 4) a2 ++;
			else a1 ++;
		}
		w ++;
		if(w > 7) w = 1;
	}
	
	cout << a1 << ' ' << a2;
	
	return 0;
}

T2：

题目描述：

Xepa Legends 是一个第一人称射击类大逃杀（“吃鸡”）游戏，每轮游戏共有 20 支 3 人小队参加，最后获胜的队伍被称为“捍卫者”。

最近 Xepa Legends 举行了亚太地区南赛区的线上比赛，争夺 7 个前往德国曼海姆参加线下赛的资格，国内共有 14 支队伍参与到了其中。因为比赛十分激烈，直到最后谁进了线下仍有巨大的疑问。小 K 喜欢的国内知名战队 DreamTear 因其队内选手杀马特表现不佳，正好卡在出线分数前后，请你赶紧帮帮小 K，计算一下最后的分数情况，看看他喜欢的战队出线了没有吧！

Xepa Legends 的比赛共进行 N 场游戏，在每场游戏中，每支队伍在游戏中会获得一个排名和一个杀敌数（击败其他队伍玩家的数量），一支队伍在一场游戏的得分为杀敌数+排名分，排名分由队伍当场的排名根据以下表格求得：

排名    分数
第一名    12 分
第二名    9 分
第三名    7 分
第四名    5 分
第五名    4 分
第六名至第七名    3 分
第八名至第十名    2 分
第十一名至第十五名    1 分
第十六名至第二十名    0 分
例如，

DreamTear 战队在第三场比赛获得了第三名、有 6 个杀敌数，那么他们将获得 7 + 6 = 13 分；
KV 战队在第二场比赛获得了第 19 名、有 1 个杀敌数，那么他们将获得 0 + 1 = 1 分；
SRN 战队在第四场比赛获得了第 1 名、有 9 个杀敌数，那么他们将获得 12 + 9 = 21 分。
注：本题与实际情况无关，所有比赛规则、队伍、队员名称均为虚构。

输入格式:
输入第一行是一个正整数 N (≤20)，表示有 N 场比赛。

接下来有 N 部分输入，每部分是一场比赛的情况。对每一场比赛，信息共分 20 行，第 i 行（i=1,?,20）给出的两个非负整数 p 和 k 表示第 i 支队伍在这场比赛里获得了第 p 名、杀敌数为 k。

数据保证所有给定的情况中，排名永远大于等于 1 且小于等于 20，杀敌数小于等于 57。

输出格式:
输出 20 行，按编号从小到大依次输出队伍的编号及该队全部游戏结束时的总分。

输入样例:
3
6 2
7 3
11 5
10 1
2 9
5 8
14 3
4 3
1 6
18 1
12 1
20 0
13 0
3 2
16 4
8 1
19 0
9 4
17 1
15 0
8 2
19 1
12 2
1 9
10 1
7 5
18 0
14 0
5 2
4 4
2 5
6 2
16 3
13 1
20 0
3 7
9 3
15 0
17 5
11 3
18 0
5 2
2 9
9 4
4 7
10 3
16 0
1 6
20 0
15 1
6 0
3 6
14 3
7 4
19 0
17 0
8 9
11 0
13 5
12 0

输出样例:
1 9
2 13
3 27
4 30
5 33
6 25
7 4
8 27
9 24
10 12
11 19
12 18
13 8
14 18
15 4
16 17
17 16
18 8
19 12
20 6

思路：预处理出一个数组，就很可以很快捷地进行处理了。

代码：

#include<bits/stdc++.h>
 
using namespace std;
 
int a[25], n;
int t[21] = {0, 12, 9, 7, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0};
 
int main()
{
	int p = 0, k = 0;
	cin >> n; 
	
	for (int op = 0; op < n; ++ op)
	{
		for (int i = 1; i <= 20; ++ i)
		{
			cin >> p >> k;
			a[i] += k + t[p];
		}
	}
	
	for (int i = 1; i <= 20; ++ i)
	{
		cout << i << ' ' << a[i];
		if(i != 20) cout << endl;
	}
	
	return 0;
}

T3：卡皮巴拉

题目描述：

在一个 N×M 的矩阵中有若干水豚以及暖炉，暖炉可以辐射以它自身为中心的 3×3 范围里的水豚，使其变得暖呼呼的。谜题里存在一只冷的要命的水豚，你需要移动其中的一个暖炉，使所有水豚都变得暖呼呼的。

在往下读题前，如果你有兴趣的话，不妨思考一下如何解答这个谜题。（思考结果与题目无关，可跳过。）

这个谜题的关键在于，单纯从图中能看到的暖炉来说是无解的，但如果注意到，第 3 行第 6 列的水豚明明周围没有暖炉，却也处于暖呼呼的状态，就能推测出来图中的那个对话框挡住了一个暖炉，只要移动这个暖炉就可以完成题目的要求。

现在我们将谜题一般化，对于给定的一个 N×M 的矩阵、对应的所有水豚状态、以及能看到的暖炉摆放情况，已知最多只有一只水豚的状态不太对劲（周围没有暖炉却暖呼呼的），你需要推测有哪些格子可能藏了暖炉。一个空格可能藏了暖炉可以理解为：当前空格设置暖炉后整个矩阵的状态会从不合法变为合法。

输入格式:
输入第一行是两个正整数 N, M (1≤N,M≤1000)，表示矩阵的大小。

接下来的 N 行，每行有 M 个字符，第 i 行的第 j 个字符表示矩阵中对应位置的状态，其中：

. 表示空格（或者说，看上去是空格的格子）；
c 表示很冷的水豚；
w 表示暖呼呼的水豚；
m 表示暖炉。
输出格式:
输出若干行，每行两个正整数 r 和 c，表示第 r 行第 c 列有可能藏了一个暖炉，有多个可能时，先按 r 从小到大输出，r 相同时再按 c 从小到大输出。如果没有一个格子可能藏了暖炉， 则在一行中输出Too cold!。
行与列均从 1 开始编号。

输入样例:
6 8
wm....mw
.w..ww..
..wm.wwm
w.w....w
.m.c.m..
w.....w.

输出样例:
2 7
3 5
4 6
4 7

思路：

对于C来说，我们要将它周围的位置记录一下，因为冻的卡皮巴拉肯定是正确的元素，所以它方圆9x9的矩阵中不能有炉子。然后对于方圆9x9的矩阵中没有炉子的暖和卡皮巴拉，那他肯定有隐藏的炉子，对应去掉由C排除的即可。

注意一个坑点，题目中提到只有最多一个异常的卡皮巴拉（跟前9X9矩阵没有炉子但不冷的），但实际如果不按照多个处理，就有一组数据过不去。

代码：

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 1010, M = 1e6 + 10;
 
int n, m;
char a[N][N];
vector<int> vc1, vc2;
vector<int> ans1, ans2;
vector<int> qq, ww;
 
struct res
{
	int r1, r2;
} rs[N];
 
bool cmp(res rr1, res rr2)
{
	if(rr1.r1 != rr2.r1) return rr1.r1 < rr2.r1;
	else return rr1.r2 < rr2.r2;
}
 
int main()
{
	string s;
	
	cin >> n >> m;
	
	for (int op = 1; op <= n; ++ op)
	{
		cin >> s;
		for (int i = 1; i <= m; ++ i)
		{
			a[op][i] = s[i - 1];
		}
	}
	
	int q = 0, w = 0;
	bool isw = false, isc = false;
	
	for (int i = 1; i <= n; ++ i)
	{
		for (int j = 1; j <= m; ++ j)
		{
			bool is = false;
			if(a[i][j] == 'w' && !isw)
			{
				int lmi = max(1, i - 1);
				int lmj = max(1, j - 1);
				int rmi = min(n, i + 1);
				int rmj = min(m, j + 1);
				
				for (int ii = lmi; ii <= rmi; ++ ii)
					for (int jj = lmj; jj <= rmj; ++ jj)
					{
						if(a[ii][jj] == 'm') 
						{
							is = true;
							break;
						}
					}
				
				if(!is) 
				{
					q = i, w = j;
					qq.push_back(q), ww.push_back(w);
				}
			}
			
			if(a[i][j] == 'c')
			{
				int lmi = max(1, i - 1);
				int lmj = max(1, j - 1);
				int rmi = min(n, i + 1);
				int rmj = min(m, j + 1);
				
				for (int ii = lmi; ii <= rmi; ++ ii)
					for (int jj = lmj; jj <= rmj; ++ jj)
					{
						if(a[ii][jj] == '.') 
						{
							vc1.push_back(ii);
							vc2.push_back(jj);
						}
					}
			}
		}
	}
	
	int tnow = 0;
	
	for (int i = 0; i < qq.size(); ++ i)
	{
		q = qq[i], w = ww[i];
		int lmi = max(1, q - 1);
		int lmj = max(1, w - 1);
		int rmi = min(n, q + 1);
		int rmj = min(m, w + 1);
		for (int i = lmi; i <= rmi; ++ i)
		{
			for (int j = lmj; j <= rmj; ++ j)
			{
				if(a[i][j] == '.')
				{
					bool jud = false;
					
					for (int t = 0; t < vc1.size(); ++ t)
					{
						int tmp1 = vc1[t];
						int tmp2 = vc2[t];
						if(i == tmp1 && j == tmp2) 
						{
							jud = true;
							break;
						}
					}
					if(!jud) 
					{
						rs[tnow].r1 = i, rs[tnow ++].r2 = j;
					}
				}
			}
		}
	}
	
	
	if(tnow == 0) cout << "Too cold!";
	else 
	{
		for (int i = 0; i < tnow; ++ i)
		{
			cout << rs[i].r1 << ' ' << rs[i].r2;
			if(i != tnow - 1) cout << endl;
		}
	}
	
	return 0;
}

T5：酬劳判断

题目描述：

这个题目没记录，大概意思是给你T组数据，每组中有N个工作，每个工作给你工时 t ，截止时间 d ，还有可获得的报酬 p，问能获得的最多的报酬是多少。

思路：

没来得及写最优解，使用了 DFS + 结构体暴力拿到了18分。

代码：

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 5050, M = 1e6 + 10;
 
int n, t, d, p;
int ans, sum;
bool st[N];
 
struct str
{
	int a, b, c;
} r[N];
 
bool cmp(str r1, str r2)
{
	if(r1.b != r2.b) return r1.b < r2.b;
	else if(r1.a != r2.a) return r1.a < r2.a;
	else return r1.c > r2.c;
}
 
void dfs(int u, int nt, int mxd, int len)
{
	if(u == mxd)
	{
		ans = max(sum, ans);
		return;
	}
	
	for (int i = nt; i < len; ++ i) 
	{
		if(!st[i])
		{
			if(u + r[i].a <= r[i].b)
			{
				st[i] = true;
				u += r[i].a;
				sum += r[i].c;
				dfs(u, i, mxd, len);
				st[i] = false;
				u -= r[i].a;
				sum -= r[i].c;
			}
		}
	}
	ans = max(sum, ans);
}
 
void solve()
{
	int len = 0, mxd = 0;
	memset(st, false, sizeof st);
	ans = 0, sum = 0;
	
	cin >> n;
	
	for (int i = 0; i < n; ++ i)
	{
		cin >> t >> d >> p;
		
		if(t <= d)
		{
			r[len].a = t, r[len].b = d, r[len++].c = p;
			mxd = max(mxd, d);
		}
	}
	
	sort(r, r + len, cmp);
	
	dfs(0, 0, mxd, len);
	
	cout << ans;
}
 
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		solve();
		if(T != 0) cout << endl;
	}
	
	return 0;
}