2023 RoboCom 世界机器人开发者大赛-本科组（国赛) CAIP 完整版题解
RC-u1 睿抗，启动！
分数 15
你被委托开发一个用于睿抗机器人开发者大赛CAIP-编程技能赛的管理系统，这个管理系统需要一些账号名和密码，你需要按照规则根据账号生成对应的密码，具体规则是：
- 将当前操作的字符串初始化为提供的账号名。
- 每次生成会规定一个生成轮次 N。
- 对于每一轮次，按顺序执行以下操作：
- 对于当前操作的字符串，将所有大写字母替换为后一个字母；如将 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();
}
}
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
12
0- 0
已为社区贡献2条内容
所有评论(0)