2022 RoboCom 世界机器人开发者大赛-本科组(国赛)-Toy模板网

这篇具有很好参考价值的文章主要介绍了2022 RoboCom 世界机器人开发者大赛-本科组(国赛)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

RC-u1 智能红绿灯

题意：为绿灯时，点击按钮后15s后转为红色持续30s，为红灯时再点击按钮则延长15s并只能延长一次，其它操作无效。

题解：模拟题，需要注意的是按下按钮后15s转为红灯后的点亮时间是闭区间，如第1s按下，红灯显示区间为[16, 45]，在这个区间再次点击按钮时才能延长红灯时间。

代码：文章来源地址https://www.toymoban.com/news/detail-638658.html

// 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;
}