2023 RoboCom 世界机器人开发者大赛-本科组（国赛) CAIP 完整版题解_cjm.png给定一个由带编号的积木搭成的长方体。其中每块积木的厚度都一样,由若干个

RC-u1 睿抗，启动！

分数 15

你被委托开发一个用于睿抗机器人开发者大赛CAIP-编程技能赛的管理系统，这个管理系统需要一些账号名和密码，你需要按照规则根据账号生成对应的密码，具体规则是：

1. 将当前操作的字符串初始化为提供的账号名。
2. 每次生成会规定一个生成轮次 N。
3. 对于每一轮次，按顺序执行以下操作：

• 对于当前操作的字符串，将所有大写字母替换为后一个字母；如将 A 替换为 B，B 替换为 C，以此类推。特别地，将 Z 替换为 A。对于所有小写字母，将其替换为前一个字母，如将 z 替换为 y，以此类推。特别地，将 a 替换为 z。
• 对于完成上一步后的字符串，如果连续出现了至少三个大写字母（不一定要相同），则将这些连续的大写字母全部改为小写字母；对于连续出现了至少三个小写字母（不一定要相同），则将这些连续的小写字母全部改为大写字母。注意修改不在原地进行，即修改结果不影响本次步骤中对于连续的判定。

现在给定账号名以及轮次，请你生成对应的密码。

输入格式:

输入第一行是一个正整数 N (1≤N≤10)，表示生成的轮次数；

输入第二行是一个字符串 S (1≤∣S∣≤100)，表示需要操作的账号名。账号名只包含大小写及数字。

注意：如果 S 为 yourname，请将 S 改为你的名字的拼音拼写，全小写，不包含空格。如你的名字为张三，则你操作的字符串应为 zhangsan。请务必写真实姓名，写错误的名字可能会导致成绩被取消。

输出格式:

输出两行，第一行为账号名，第二行为根据规则生成的密码。

输入样例:

1
DOGcat1234XZxzABabFFXIV
 

输出样例:

DOGcat1234XZxzABabFFXIV
ephBZS1234YAwyBCzaggyjw

输入样例:

2
DOGcat1234XZxzABabFFXIV
 

输出样例:

DOGcat1234XZxzABabFFXIV
DOGcat1234ZBvxCDYZFFXIV

题解:

模拟题, 按照题目要求进行模拟, 注意题目特殊要求和可能有其他字符的存在 

参考代码:

#include<bits/stdc++.h>
using namespace std;
string Password;
void solve(string s) {
	int n = s.size();
	for(int i = 0; i < n; ++ i) {
		
		if(s[i] >= 'A' && s[i] <= 'Z') {
			if(s[i] == 'Z')	s[i] = 'A';
			else	++ s[i];
		}
		else if(s[i] >= 'a' && s[i] <= 'z'){
			if(s[i] == 'a')	s[i] = 'z';
			else	-- s[i];
		}
	}
	
	for(int i = 0; i < n; ++ i) {
		if(s[i] >= 'a' && s[i] <= 'z') {
			int j = i;
			while(j + 1 < n && s[j + 1] >= 'a' && s[j + 1] <= 'z')	++ j;
			if(j - i + 1 >= 3) {
				for(int k = i; k <= j; ++ k)	s[k] =  s[k] - ('a' - 'A');
			}
			i = j;
		}
		else if(s[i] >= 'A' && s[i] <= 'Z'){
			int j = i;
			while(j + 1 < n && s[j + 1] >= 'A' && s[j + 1] <= 'Z')	++ j;
			if(j - i + 1 >= 3) {
				for(int k = i; k <= j; ++ k)	s[k] =  s[k] + ('a' - 'A');
			}
			i = j;
		}
	}
	Password = s;
}
int main() {
	int t;
	string name; 
	cin >> t >> name;
	if(Password == "yourname")	name = "xxx"; 
    Password = name;
	while(t --) 	solve(Password);
	cout << name << "\n" << Password;
	return 0;
}

RC-u2 桌游猜谜

分数 20

小 C 和他的朋友一起玩一个桌游。游戏开始的时候，一共有 6 种不同颜色的卡牌，每种颜色有 8 张卡牌，其中一面写着 1 到 8 的数字，每种颜色的每个数字的卡牌只有一张。每位玩家需要从每种颜色的卡牌中抽取一张，并将卡牌摆放在自己的面前，卡牌上的数字朝外，所有玩家坐成一圈，这样所有玩家能看见其他玩家卡牌上的颜色及数字，也能看见自己的卡牌的颜色，但看不到自己的卡牌的数字。

游戏会进行若干轮，每次轮到某位玩家的时候，玩家可以选择三种不同的颜色，再选择一个范围 [L,R]，询问一次其他玩家，自己对应的三种颜色的卡牌的数字之和是不是在范围内。其他玩家可以如实地回答“是”或“不是”。在游戏最后玩家需要猜测出自己卡牌上的数字是什么。

为了提高自己的游戏水平，小 C 决定考虑一个简化的问题：现在游戏刚刚开始，小 C 第一个进行询问。不难发现，进行询问后，小 C 可以根据回答排除一些自己卡牌上的数字的不可能的情况。例如选择红色、黄色、蓝色三种颜色的卡牌，询问三种颜色卡牌上的数字和的范围是否为 [5,8]，假设回答是“是”，那么显然不可能出现红色卡牌数字为 2、黄色卡牌数字为3、蓝色卡牌数字为 4 的情况。

进一步地，对于一个询问，假设其他玩家给出的回答为“是”的时候可以排除的自己卡牌数字的可能方案数为 K1​，给出的回答为“不是”的时候可以排除的可能方案数为 K2​。小 C 自然希望自己的询问能够在不同的情况下尽可能排除更多的情况，因此小 C 希望自己的询问能够最大化 Min(K1​,K2​) 的值。

请你求出在询问达到以上要求的情况下，小 C 卡牌数字剩余的可能方案数为多少。

输入格式:

输入第一行是一个正整数 T (1≤T≤5)，表示数据组数。

接下来的 T 组数据，每组数据第一行是一个正整数 N (1≤N≤7)，表示其他玩家的数量。

紧接着的 N 行，每行是六个数字，表示看到的其他玩家的数字是什么。

为方便起见，对于所有玩家来说，输入里的第 i 个数字固定对应着第 i 种颜色的牌面数字。

保证给定的输入数据合法。

输出格式:

对于每组数据，输出一行一个数，表示在最大化 Min(K1​,K2​)时，小 C 的卡牌数字剩余的可能方案数是多少。

输入样例:

2
1
1 1 1 1 1 1
3
1 4 2 8 5 7
2 3 1 4 6 6
4 5 3 2 8 1
 

输出样例:

59339
7875

题解 :

暴力枚举, 枚举选择哪三种颜色和询问的范围, 同时还要明白计算公式, 否则就0分了(我也是, 当时还怀疑dfs写错了). 题目要求最大化 min(K1, K2) 的同时输出剩余最多种情况的方案数,  计算公式可以为 max(K1, K2) *  pow(8 - n, 3),    其中pow(8 - n, 3)为其他三种颜色的所有卡牌组合方案数 .

参考代码:

#include<bits/stdc++.h>
using namespace std;
pair<int,int> ans;
int arr[10][10];
int n;
bool st[10][10];
pair<int,int> temp;
void dfs(int &x1, int &x2, int &x3, int cnt, int &l, int &r, int sum) {
	if(cnt == 4)	{
		if(sum >= l && sum <= r)	++temp.first;
		else	++ temp.second;
		return;
	}
	int t = -1;
	if(cnt == 1)	t = x1;
	else if(cnt == 2)	t = x2;
	else	t = x3;
	
	for(int i = 1; i <= 8; ++ i) {
		if(!st[t][i]) {
			st[t][i] = true;
			dfs(x1, x2, x3, cnt + 1, l, r, sum + i);
			st[t][i] = false; 
		}
	}
}
 
void check(int x1, int x2, int x3, int l, int r) {
	temp = {0, 0};
	dfs(x1, x2, x3, 1, l, r, 0);
	if(min(temp.first, temp.second) > min(ans.first, ans.second)) {
		ans = temp;
	}
	else if(min(temp.first, temp.second) == min(ans.first, ans.second) && abs(temp.first - temp.second) < abs(ans.first - ans.second)) {
		ans = temp;
	}
}
 
 
void solve() {
	ans = {-1, -1};
	memset(st, false, sizeof st); 
	cin >> n;
	for(int i = 1; i <= n; ++ i) {	//其他玩家 
		for(int j = 1; j <= 6; ++ j) {
			cin >> arr[i][j];
			st[j][arr[i][j]] = true;
		}
	}
 
	for(int i = 1; i <= 6; ++ i) {
		for(int j = i + 1; j <= 6; ++ j) {
			for(int k = j + 1; k <= 6; ++ k) {
				for(int l = 3; l <= 24; ++ l) {
					for(int r = l; r <= 24; ++ r) {
						check(i, j, k, l, r);
					}
				}
			}
		}
	}
 
	int sum = pow(8 - n, 3), t = max(ans.first, ans.second);
	cout <<  sum * t << '\n';
}
int main() {
	int t;
	cin >> t;
	while(t --) {
		solve();
	}
	return 0;
}

RC-u3 兰州拉面派餐系统

分数 25

兰州拉面是著名美食，其煮面很有讲究，不同种类的面需要煮不同的时长。拉面馆的煮面师傅的规则很简单，只要手头有煮面篮子是空闲的，就把下一份客单指定的面放到空闲篮子里煮；如果空闲的篮子不止一个，那么先放到其中编号最小的篮子里煮；如果没有篮子是空闲的，就等待。一个篮子里的面煮够了时间，师傅要准时捞出来放到该客单对应的碗里，招呼服务员端给客人；如果有多个篮子里的面同时到了捞取时间，师傅会同时捞起，但要本着先到先得的原则，按下单顺序招呼送餐。

在生意火爆的拉面馆里，煮面师傅需要很强的记忆力和计时能力，才能面对源源不断的客单，同时照顾一大堆煮面篮子而不出错。如果面的品种不太多，篮子也不太多，那一位拉面师傅的大脑还是能应对的。但如果我们有上千种面、上万只煮面篮、数十万客单呢…… 这就需要请你帮忙，写个派餐系统来完成这个任务了。

输入格式：

输入在第一行中给出 3 个正整数：N（≤103）为面的种类数；M（≤104）为煮面篮子的个数；L（≤105）为客单总数。于是我们假设面的种类从 1 到 N 编号、篮子从 1 到 M 编号、客单从 1 到 L 编号。

第二行给出 N 个不超过 10 的正整数，第 i 个数字对应第 i 种面需要煮的时间长度（分钟）。

第三行给出 L 个正整数，第 i 个数字对应第 i 份客单所点的面种 —— 这里我们将情况简化为一份客单只要一种面，并且只要一碗，所以只要给出面的种类即可。

一行中数字间以空格分隔。

因为面馆的生意太火爆，我们可以认为所有的客单都是在开门前就预约好的，并且是按预约的顺序递增编号的。此外，与煮面的时长相比，下面、捞面和送餐的时长是可以忽略不计的。

输出格式：

首先按照送单顺序在一行中输出所有客单的编号和送餐时间（即开门后第几分钟），格式为 编号:时间。

随后在下一行按照编号递增序输出每只篮子煮了多少碗面。

一行的输出之间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

3 5 10
3 5 8
2 1 3 3 1 1 2 1 3 2
 

输出样例：

2:3 5:3 1:5 6:6 3:8 4:8 7:8 8:8 10:13 9:14
3 3 1 1 2

题解:

分别开两个优先队列, 其中一个优先队列为煮面篮子的编号(从小到大), 另一个则为完成时间和所用篮子的编号(因为要还篮子). 最后记录答案排序后输出

参考代码:

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e3 + 10, M = 1e5 + 10;
int val[M], arr[M];
int ct[M];
 
struct info{
	int x, y, id;
	bool operator < (const info &X) const {
		return x > X.x;
	}
};
 
bool cmp(pair<int,int> &x, pair<int,int> &y) {
	if(x.first != y.first)	return x.first < y.first;
	return x.second < y.second; 
}
 
void solve() {
	int n, m, L, cnt = 1;
	cin >> n >> m >> L;
	for(int i = 1; i <= n; ++ i)	cin >> val[i];
	for(int i = 1; i <= L; ++ i)	cin >> arr[i];
	priority_queue<int> rot;
	for(int i = 1; i <= m; ++ i)	rot.push(-i);
	
	priority_queue<info>q;
	vector<pair<int,int> > ans;
	int times = 0;
	while(cnt <= L || !q.empty()) {
 
		while(!q.empty() && q.top().x <= times) {
			ans.push_back({q.top().x, q.top().y});
			rot.push(q.top().id); 
			q.pop();
		}
		
		while(!rot.empty() && cnt <= L) {
			q.push({val[arr[cnt]] + times, cnt ++, rot.top()});
			ct[-rot.top()] ++;
			rot.pop();
		}
		++ times; 
	}
	
	sort(ans.begin(), ans.end(), cmp);
	
    for(int i = 0; i < ans.size(); ++ i) {
    	cout << ans[i].second << ":" << ans[i].first; 
    	if(i != ans.size() - 1)	cout  << " ";
	}	
    cout << '\n';
    for(int i = 1; i <= m; ++ i){
    	cout << ct[i];
    	if(i != m)	cout << " ";
	}
    
    
}
int main() {
	solve();
	return 0;
}

RC-u4 拆积木

分数 30

给定一个由带编号的积木搭成的长方体。其中每块积木的厚度都一样，由若干个单位边长的相邻方块组成（相邻是指两个方块有一面重合）。现在要求将这个长方体中的积木一块一块拆掉。每块积木只能从顶端取出，并且取出时不能移动还在长方体中的其它积木。请你给出一个拆积木的顺序。当然这种顺序可能是不唯一的，我们规定当有多种选择时，总是取出编号最小的那个。

输入格式:

输入第一行给出两个正整数 N 和 M（1≤N,M≤1000），分别为长方体的高度和宽度。随后 N 行，每行给出 M 个整数，为对应位置上积木的编号。编号为不超过 106 的正整数，数字间以空格分隔。题目保证不同积木的编号是不同的。

输出格式:

在一行中输出按照题目限定可以拆卸积木的顺序。数字间以 1 个空格分隔，行首尾不得有多余空格。如果拆卸到某一步发现无法继续了，则在对应位置上输出 Impossible，然后结束。

输入样例 1（示意如上图）:

5 5
4 4 4 11 11
9 9 4 2 1
9 5 4 4 4
7 3 3 6 10
8 8 8 10 10

输出样例 1:

11 1 2 4 6 9 5 3 7 8 10

输入样例 2:

4 3
8 9 7
4 4 4
5 6 4
1 4 4

输出样例 2:

7 8 9 Impossible

题解 :

拓扑排序, 将该积木抽象为图, 则可以将方块看作点, 不同点之间若有直接上下接触则连一条从上方点到下方点的边, 只有入度为0的点可以出队(拆出该方块积木) . 注意空间限制

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 2, M = 1e6;
int h[M], e[M], ne[M], idx;
short int inp[M];
int val[M], mp[M + 1];
 
struct info {
	short int x;    int y;
	bool operator < (const info &X) const {
		if(x != X.x)	return x > X.x;
		return val[y] > val[X.y];
	}	
}; 
 
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
 
void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int> > g(2, vector<int> (m));
	int id = 0;
	memset(h, -1, sizeof h);
	memset(mp, -1, sizeof mp);
	for(int i = 0; i < n; ++ i) {
		for(int j = 0; j < m; ++ j) {
			cin >> g[i & 1][j];
			if(mp[g[i & 1][j]] == -1) {
				mp[g[i & 1][j]] = id ++;
			}
			
			int t = i & 1;
			if(i != 0 && g[t][j] != g[!t][j]) {
				++ inp[mp[g[t][j]]];
				add(mp[g[!t][j]], mp[g[t][j]]);
			}
		}
	}
	
	priority_queue<info> q;
	for(int i = 1; i <= 1e6; ++ i)	{
		if(mp[i] == -1)	continue;
		val[mp[i]] = i;
		q.push({inp[mp[i]], mp[i]});
	}
    
	int cnt = 0, nums = id;
	while(cnt < nums) {
		if(q.top().x != 0) {
			cout << "Impossible";
			return;
		}
		else {
			auto t = q.top();
			q.pop();
			cout << val[t.y];
			++ cnt;
			if(cnt != nums)	cout << " ";
			for(int i = h[t.y]; ~i; i = ne[i]) {
				int j = e[i];	
				-- inp[j];
				q.push({inp[j], j});
			}
		}
	}
}
int main() {
	solve();
	return 0;
}

RC-u5 栈与数组

分数 30

现在有两个大小分别为 C1​ 和 C2​ 的栈，以及一个固定长度的数组，数组的每个位置一开始都是空的。只要数组仍然有空间，每次你可以从任意一个栈顶取出一个数字放置在数组的任意空位，然后判断数组里是否有 K 个相同的数字，如果有的话，那么你可以从数组里删除这 K 个数字，删除后的空间可以继续用于放置其他数字。

请问如果要将两个栈全部清空，数组的长度至少是多少？

输入格式:

输入第一行是一个正整数 T (1≤T≤3)，表示数据组数。

接下来的 T 组数据，每组数据的第一行是三个数 C1​,C2​,K (1≤C1​,C2​≤1000,2≤K≤100)，表示两个栈的大小以及相同 K 个数字可以删除。

接下来的两行，第一行是 C1​ 个数字，第二行是 C2​ 个数字，用一个空格隔开，表示栈顶到栈底的数字分别是多少。所有数字均为小于等于 2000 的非负整数。

输出格式:

对于每组数据输出一行一个数，表示数组的长度至少为多少。

输入样例:

3
6 7 3
1 1 4 5 1 4
1 9 1 9 8 1 0
5 5 2
1 2 3 4 5
6 7 8 9 10
5 5 2
1 1 1 1 1
1 1 1 1 1
 

输出样例:

8
10
2

提示:

第一组样例中，一种可行的方法是：

先弹出第一个栈两次，再弹出第一个栈一次，此时两个栈变为以下情况：

4 5 1 4
9 1 9 8 1 0

然后再依次弹出第一个栈 3 次，第二个栈 5 次（此时花费空间最多），两个栈变为以下情况：

4
0

数组里还剩下的数字（不论顺序）为：

4 5 9 9 8

最后弹出并放置剩余元素即可。数组最多需要 8 的空间。

题解:
 

------2024.3.26 更新---------------

动态规划. 先考虑只有一个数组的时候, 此时弹出顺序固定, 按照题意模拟, 第 i 个位置向下一个位置进行转移时, 我们需要知道两个信息: 在 i 点的当前长度, 在 i 点 及之前 的最大长度. 最后的末位置上的最大长度则是答案

同理, 此时有两个数组, 弹出的顺序并不固定(当k固定时, 其实我们不在乎实际的弹出顺序, 只需要知道弹出的数字是哪些就行, 因为我们总会以最优的方式去弹出数字{且看dp状态定义}),  我们可以定义pair<int,int> dp[C1][C2], 其中dp[i][j].first 为弹出C1数组前 i 个数字和C2数组前 j 个数字 此时的栈内最大容量,   dp[i][j].second 弹出C1数组前 i 个数字和C2数组前 j 个数字 此时的栈内已使用的容量.  显然， dp[i][j] 可以由 dp[i-1][j], dp[i][j-1] 转移而来.  

若dp[i][j]由dp[i-1][j]转移而来，分为两种情况处理：
1. dp[i-1][j].first == dp[i-1][j].second, 即当前的最大容量已经被占满, 此时新放进一个数进去， 最大容量+=1， 至于现在已用容量的更新 也只用讨论新加进下数是否满足删除的条件 

2.  dp[i-1][j].first != dp[i-1][j].second, 即当前的最大容量未被占满, 此时新放进一个数进去， 不会变化， 已用容量的更新 同上

由dp[i][j-1]转移而来 情况处理同上 

细节可以看代码

参考代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define pre(i,x,y) for(int i=x; i>=y; --i)
const int N = 1e3 + 10, INF = N << 1;
int stk1[N], stk2[N];
int pre_cnt[2010];
void solve() {
    int c1, c2, k;
    cin >> c1 >> c2 >> k;
    memset(pre_cnt, 0, sizeof(pre_cnt));
    rep(i, 1, c1)   cin >> stk1[i];
    rep(i, 1, c2)   cin >> stk2[i];
    if(k == 1) {
        cout << 1 << '\n';
        return;
    }
    vector<vector<pair<int,int>> > f(c1 + 1, vector<pair<int,int>>(c2 + 1, {INF, INF}));
    f[1][0] = f[0][1] = {1, 1};
 
    rep(i, 1, c1) {
        pre_cnt[stk1[i]] += 1;
        unordered_map<int,int> mp;
        rep(j, 1, c2) {
            mp[stk2[j]] += 1;
            // f[i-1][j] --> f[i][j]
            pair<int,int> t1 = {INF, INF}, t2 = {INF, INF};
            auto &x = f[i-1][j];
            if(x.first == x.second)     t1.first = x.first + 1;
            else t1.first = x.first;
            t1.second = ((mp[stk1[i]] + pre_cnt[stk1[i]]) % k == 0) ? x.second + 1 - k : x.second + 1;
 
 
            //f[i][j-1] --> f[i][j]
            x = f[i][j-1];
            if(x.first == x.second)     t2.first = x.first + 1;
            else t2.first = x.first;
            t2.second = ((mp[stk2[j]] + pre_cnt[stk2[j]]) % k == 0) ? x.second + 1 - k : x.second + 1;
            f[i][j] = min(t1, t2);
        }
    }
    cout << f[c1][c2].first << '\n';
}
 
signed main() {
#ifndef ONLINE_JUDGE
    freopen("E:\\CLionProjects\\data.in","r",stdin);
    freopen("E:\\CLionProjects\\data.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t --) {
        solve();
    }
}