2022 RoboCom 世界机器人开发者大赛-本科组(国赛)
·
RC-u1 智能红绿灯
题意：为绿灯时，点击按钮后15s后转为红色持续30s，为红灯时再点击按钮则延长15s并只能延长一次，其它操作无效。
题解：模拟题，需要注意的是按下按钮后15s转为红灯后的点亮时间是闭区间，如第1s按下，红灯显示区间为[16, 45]，在这个区间再次点击按钮时才能延长红灯时间。
代码：
// AC
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
const int N = 1e4+10;
int a[N];
int n;
int flag, l, r, color;
vector<PII> v;
int main()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
cin >> a[i];
int x = a[i];
if(i && a[i] == a[i-1]) continue;
// 绿转红
if(!color) {
l = x + 15;
r = l + 29;
flag = 0;
color = 1;
}
// 再次点击 注意红灯区间
else if(color && !flag && r >= x && l <= x) {
r = r + 15;
flag = 1;
}
// 红转绿
else if(color && r < x) {
color = 0;
if(!v.size() || v.back() != make_pair(l, r)) v.push_back(make_pair(l, r));
// 绿转红
l = x + 15;
r = l + 29;
flag = 0;
color = 1;
}
}
if(!v.size() || v.back() != make_pair(l, r)) v.push_back(make_pair(l, r));
for(int i = 0;i < v.size();i ++)
{
cout << v[i].first << ' ' << v[i].second << endl;
}
return 0;
}
RC-u2 女王的大敕令
题意：在5*5方格中给定终点，上下左右四个方向的怪物，在初始位置时，左右怪物顺时针移动相应行数后进行整行的激光覆盖，在移动一次位置后，上下怪物顺时针移动相应列数后进行整列的激光覆盖，您需要保证确定初始位置和移动一次后的位置，并且这两个位置不会被怪物的激光覆盖，然后可以通过指定步数到达终点。
题解：模拟题，需要注意的是初始位置时是左右两侧怪物移动，上下怪物位置保持不变，而第一次移动位置后是上下两侧怪物移动，左右怪物位置保持不变。我们可以推断出初始和第一次移动后的安全位置，然后4重循环枚举这两个位置，通过移动距离相等来判断是否满足条件，最后排序输出。
代码：
//AC
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int mp[6][6], mp2[6][6];
int c1, c2, r1, r2;
int n[5];
int r, c, d1, d2;
int idx;
struct node
{
int x, y, x2, y2;
}no[N];
bool cmp(node x, node y)
{
if(x.x == y.x && x.y == y.y && x.x2 == y.x2) return x.y2 < y.y2;
else if(x.x == y.x && x.y == y.y) return x.x2 < y.x2;
else if(x.x == y.x) return x.y < y.y;
else return x.x < y.x;
}
int main()
{
cin >> c1 >> c2 >> r1 >> r2;
for(int i = 1;i <= 4;i ++) cin >> n[i];
cin >> r >> c >> d1 >> d2;
// 左右两侧怪物移动后的激光覆盖情况
for(int i = 1;i <= 5;i ++)
{
mp[i][c1] = 1;
mp[i][c2] = 1;
mp[r1-n[3]][i] = 1;
mp[r2+n[4]][i] = 1;
}
// 上下两侧怪物移动后的激光覆盖情况
for(int i = 1;i <= 5;i ++)
{
mp2[i][c1+n[1]] = 1;
mp2[i][c2-n[2]] = 1;
mp2[r1-n[3]][i] = 1;
mp2[r2+n[4]][i] = 1;
}
// 枚举两个位置
for(int i = 1;i <= 5;i ++)
{
for(int j = 1;j <= 5;j ++)
{
if(!mp[i][j])
{
for(int i1 = 1;i1 <= 5;i1 ++)
{
for(int j1 = 1;j1 <= 5;j1 ++)
{
if(!mp2[i1][j1])
{
// 判断曼哈顿距离
int dd2 = abs(r-i1) + abs(c-j1);
int dd1 = abs(i1-i) + abs(j1-j);
if(dd2 == d2 && dd1 == d1)
{
no[idx].x = i;
no[idx].y = j;
no[idx].x2 = i1;
no[idx].y2 = j1;
idx ++;
}
}
}
}
}
}
}
// 排序输出
sort(no, no+idx, cmp);
for(int i = 0;i < idx;i ++)
{
cout << no[i].x << ' ' << no[i].y << ' ';
cout << no[i].x2 << ' ' << no[i].y2 << endl;
}
return 0;
}
RC-u3 战利品分配
题意：给定边权为1的无向图，从起点到终点距离最短并且指定距离点权和最大。
题解：bfs，当到达终点后统计最大点权和，需要注意的是起点到终点距离最短，超过这个距离后的答案无效，终止。
代码：
// AC
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
unordered_map<int, int> mp;
vector<int> v[N];
int w[N], vis[N];
int n, m, k, p;
int s, t;
int res, minn = 0x3f3f3f3f;
struct node
{
// 节点 步数 答案
int no, st, ww;
};
void add(int x, int y)
{
// 判断是否出现过该边 可以省略
if(mp.count(x) && mp[x] == y) return;
mp[x] = y;
v[x].push_back(y);
}
void bfs()
{
queue<node> q;
int ww = 0;
// 注意p=1情况
if(p == 1) ww = w[s];
// 步数为0方便计算
q.push({s, 0, ww});
while(q.size())
{
node tt = q.front();
q.pop();
vis[tt.no] = 1;
// 超过最短距离直接终止
if(tt.st > minn) break;
// 更新答案和最短距离
if(tt.no == t)
{
minn = tt.st;
res = max(res, tt.ww);
continue;
}
for(int i = 0;i < v[tt.no].size();i ++)
{
int u = v[tt.no][i];
// 注意终点可以多次访问
if(!vis[u] || u == t)
{
vis[u] = 1;
int no = u;
int st = tt.st + 1;
int ww = tt.ww;
if(st%k + 1 == p) ww += w[u];
q.push({no, st, ww});
}
}
}
}
int main()
{
cin >> n >> m >> k >> p;
for(int i = 1;i <= n;i ++) cin >> w[i];
for(int i = 0;i < m;i ++)
{
int x, y;
cin >> x >> y;
if(x != y)
{
add(x, y);
add(y, x);
}
}
cin >> s >> t;
bfs();
cout << res << endl;
return 0;
}
RC-u4 变牛的最快方法
题意：最短编辑距离+记录路径
题解：动规找出所需要的最少操作数，并记录路径
代码：
// AC
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
const int N = 1010;
vector<int> ans;
int f[N][N], op[N][N];
PII pre[N][N];
vector<int> s1, s2;
int n, m, x, y;
void init()
{
// 边界值初始化
for(int i = 0;i <= n;i ++) f[i][0] = i, op[i][0] = 0, pre[i][0] = {i-1, 0};
for(int i = 0;i <= m;i ++) f[0][i] = i, op[0][i] = 3, pre[0][i] = {0, i-1};
}
int main()
{
s1.push_back(0);
cin >> x;
while(x != -1)
{
s1.push_back(x);
cin >> x;
}
s2.push_back(0);
cin >> y;
while(y != -1)
{
s2.push_back(y);
cin >> y;
}
n = s1.size()-1;
m = s2.size()-1;
init();
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
// 是否需要修改
int flag = 1;
if(s1[i] == s2[j]) flag = 0;
int del = f[i-1][j] + 1;
int add = f[i][j-1] + 1;
int upd = f[i-1][j-1] + flag;
f[i][j] = min(del, min(add, upd));
// 记录操作类型和位置
if(f[i][j] == del)
{
op[i][j] = 0;
pre[i][j] = {i-1, j};
}
else if(f[i][j] == add)
{
op[i][j] = 3;
pre[i][j] = {i, j-1};
}
else
{
// 更新
if(flag) op[i][j] = 1;
else op[i][j] = 2;
pre[i][j] = {i-1, j-1};
}
}
}
cout << f[n][m] << endl;
ans.push_back(op[n][m]);
PII t = pre[n][m];
while(t.first || t.second)
{
int i = t.first, j = t.second;
ans.push_back(op[i][j]);
t = pre[i][j];
}
reverse(ans.begin(), ans.end());
for(int x : ans) cout << x;
return 0;
}
RC-u5 养老社区
题意：给定一棵树，每个节点有一个类型，需要找出本质不同的三元组个数，即3个节点的类型各不相同，并且两两之间的最短距离相同。
题解：n次bfs找出每两节点之间的最短距离，3重循环判断每3个节点是否满足要求。
代码：
// AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
vector<int> G[maxn];
int n, t[maxn];
int vis[maxn], e[maxn][maxn];
void bfs(int x){
queue<int> q;
q.push(x);
vis[x] = 1;
while(q.size()){
int u = q.front();
q.pop();
for(int to : G[u]){
if(vis[to])continue;
vis[to] = 1;
e[x][to] = e[x][u]+1;
q.push(to);
}
}
}
int main(){
cin >> n;
for(int i = 1; i < n; i++){
int u ,v ;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1; i <= n; i++) cin >> t[i];
// bfs求任意2节点距离
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) vis[j] = 0;
bfs(i);
}
// 枚举3个节点
int cnt = 0;
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
for(int k = j+1; k <= n; k++){
// 判断距离 注意由于数据量 这里的条件不能交换
if(e[i][j]==e[j][k] && e[i][j]==e[i][k]){
// 判断类型
if(t[i]!=t[j] && t[i]!=t[k] && t[j]!=t[k]){
cnt++;
}
}
}
}
}
cout << cnt << endl;
return 0;
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)