当前位置：网站首页>2021 RoboCom 世界机器人开发者大赛-本科组（复赛）

2021 RoboCom 世界机器人开发者大赛-本科组（复赛）

2022-07-06 04:43:00 【Zqchang】

文章目录

官方题解

官方题解

7-1 冒险者分队

分数 20
7-1 冒险者分队

一个莫名其妙的思维

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
// const int N = 
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int a, b, c, x, y, z;

signed main()
{
    
	fast;
	int t;
	cin >> t;
	while(t --)
	{
    
		cin >> a >> b >> c >> x >> y >> z;

		if(a == x && b == y && c == z)
        {
    
            cout<<0<<endl;
            continue;
        }

		int xx = x - a;
		int yy = y - b;
		int zz = z - c;

		if((xx + yy + zz) || (xx % 20 != 0 || yy % 20 != 0 || zz % 20)) cout << -1 << endl;
		else
		{
    
			int p[3] = {
    xx, yy, zz};
			sort(p, p + 3);
			xx = p[0] / 20, yy = p[1] / 20, zz = p[2] / 20;
			int ans = 0;

			if((xx % 3 + 3) % 3 != (yy % 3 + 3) % 3 || (xx % 3 + 3) % 3 != (zz % 3 + 3) % 3)
	        {
    
	            cout<<-1<<endl;
	            continue;
	        }

			// cout << xx << " " << yy << " " << zz << endl;
			if(yy > 0)
			{
    
				ans += yy;
				xx += 2 * yy;
				zz -= yy;
				yy = 0;

				ans += zz / 3 * 2;

				/* while(yy > 0) { xx += 2; yy -= 1; zz -= 1; ans ++; } while(xx < 0) { xx += 3; zz -= 3; ans += 2; } */
			}
			else if(yy < 0)
			{
    
				ans += abs(yy);
				xx += abs(yy);
				zz -= 2 * abs(yy);
				yy = 0;

				ans += zz / 3 * 2;
				/* while(yy < 0) { xx += 1; yy += 1; zz -= 2; ans ++; } while(xx < 0) { xx += 3; zz -= 3; ans += 2; } */
			}
			else
			{
    
				ans += zz / 3 * 2;
				// while(xx < 0)
				// {
    
				// xx += 3;
				// zz -= 3;
				// ans += 2;
				// }
			}
			cout << ans << endl;
		}
	}
	
	return 0;
}

7-2 拼题A打卡奖励

分数 25
7-2 拼题A打卡奖励

01背包的变形，在面临超时的情况下，明智的选择另一种作为限制

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 1e3 + 10, M = 3e4 + 10;
int n, m;
int w[N], v[N];
int f[M];
signed main()
{
    
	fast;
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> v[i];//时间
	for(int i=1; i<=n; i++) cin >> w[i];//金币
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for(int i=1; i<=n; i++)
		for(int j=30000; j>=w[i]; j--)
		{
    
			f[j] = min(f[j], f[j - w[i]] + v[i]);
		}

	for(int i=30000; i>=0; i--)
	{
    
		if(f[i] <= m) 
		{
    
			cout << i << endl;
			break;
		}
	}
	return 0;
}

7-3 快递装箱

分数 25
7-3 快递装箱

大模拟，没拿到满分，就十六分，不想改了，累了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(p) p&(-p)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 1e4 + 10;
// deque<int> a, b, c, d;
queue<PII> a, b, c;
deque<PII> d1, d;
int n, m, w1, w2, wm;
int f1[N], f2[N];
int res1, res2;

signed main()
{
    
	// fast;
	cin >> n >> wm >> w1 >> w2;
	PII p;
	for(int i=1; i<=n; i++)
	{
    
	    while(d.size() >= 2) 
	    {
    
	        p = d.back();
	        d.pop_back();
	        d1.push_back(p);
	    }
	    
		if(c.size())
		{
    
			p = c.front();
			c.pop();
			if(!d.size()) 
			{
    
				d.push_front(p);
				f1[p.y] = 1;
			}
			else if(d.size())
			{
    
				PII q = d.front();
				d.pop_front();
				if(p.x + q.x <= wm && !f1[p.y]) d.push_front({
    p.x + q.x, q.y});
				else if((p.x + q.x > wm && !f1[p.y]) || f1[p.y])
				{
    
					if(q.x > w2) res2 ++;
					else d.push_back(q);
					d.push_front(p);
					f1[p.y] = 1;
				}
			}	
		}
		// else if(d.size() && i == n)
		// {
    
		// PII q = d.front();
		// d.pop_front();
		// if(q.x > w2) res2 ++;
		// else d1.push_back(q);
		// }

		if(b.size())
		{
    
			p = b.front();
			b.pop();
			if(p.x > w2) res1 ++;
			else c.push(p);
		}

		if(a.size())
		{
    
			p = a.front();
			a.pop();
			if(p.x > w1) f1[p.y] = 1;
			b.push(p);
		}
		
		cin >> m;

		if(d1.size()) 
		{
    
			p = d1.front();
			d1.pop_front();
			if(p.x + m <= wm) 
			{
    
				a.push({
    m + p.x, i});
				f1[i] = 1;
			}
			else
			{
    
				d1.push_front(p);
				a.push({
    m, i});
			}
		}
		else a.push({
    m, i});
		
// cout << "di.size(): " << d1.size() << endl;
	} 
	
	if(d.size())
	{
    
		p = d.front();
		d.pop_front();
		if(p.x > w2) res2 ++;
		else d.push_front(p);
	}
	
	vector<int> v;
	
	while(a.size())
	{
    
	    p = a.front();
	    v.push_back(p.x);
	    a.pop();
	   // cout << "!!!" << endl;
	}
    
    while(b.size())
	{
    
	    p = b.front();
	    v.push_back(p.x);
	    b.pop();
	   // cout << "!!!" << endl;
	}
	while(c.size())
	{
    
	    p = c.front();
	    v.push_back(p.x);
	    c.pop();
	   // cout << "!!!" << endl;
	}
	while(d.size())
	{
    
	    p = d.front();
	    v.push_back(p.x);
	    d.pop_front();
	   // cout << "!!!" << endl;
	}
	while(d1.size())
	{
    
	    p = d1.front();
	    v.push_back(p.x);
	    d1.pop_front();
	   // cout << "!!!" << endl;
	}
	
	sort(v.begin(), v.end());
	
	cout << res1 << " " << res2 << " " << v.size() << endl;
	
	if(v.size() == 0) puts("None");
	else
	{
    
		for(int i=0; i<v.size(); i++)
		{
    
		    cout << v[i];
		    if(i == v.size() - 1) cout << endl;
		    else cout << " ";
		}
	}
	
	return 0;
}

7-4 塔防游戏

分数 30
7-4 塔防游戏

头一次写二位最短路

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define PII pair<int, int>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define PIII pair<int, PII>
#define x first
#define y second
const int N = 110;
int dx[] = {
    -1,1,0,0};
int dy[] = {
    0,0,-1,1};//方向
struct node
{
    
	int x, y, z;
};
int dist[N][N];
int f[110][110];
PII path[N][N];//记录僵尸路径 
bool vis[N][N];
vector<node> v;//记录僵尸 
int cnt[N][N];//记录走过的步数
vector<PII> p[4 * N];//记录每个僵尸的路线 
int num[4 * N];//僵尸人数 
map<PII, int> mp;
int now[N * 4];
int idx = 1;
int n, m, T;

int get(PII xx)
{
    
    if(mp[xx] == 0) mp[xx] = idx++ ;//因为前面判断就是用的等于0，所以下标要从1开始 
    return mp[xx];
}
///*
void dij(PII u)
{
    
	memset(dist, 0x3f, sizeof dist);
	priority_queue<PIII, vector<PIII>, greater<PIII>> q;
	
	dist[u.x][u.y] = 0;
	q.push({
    0, u});
	while(q.size())
	{
    
		auto t = q.top();
		q.pop();
		
		if(vis[t.y.x][t.y.y]) continue;
		
		vis[t.y.x][t.y.y] = 1;
		
		auto tt = t.y;
		for(int i=0; i<4; i++)
		{
    
			int xx = tt.x + dx[i];
			int yy = tt.y + dy[i];
			
			if(xx > n || xx < 1 || yy > m || yy < 1) continue;
			
			if(dist[xx][yy] > dist[tt.x][tt.y] + f[xx][yy])
			{
    
				dist[xx][yy] = dist[tt.x][tt.y] + f[xx][yy];
				cnt[xx][yy] = cnt[tt.x][tt.y] + 1;
				path[xx][yy] = tt;
				q.push({
    dist[xx][yy], {
    xx, yy}});
			}
			else if(dist[xx][yy] == dist[tt.x][tt.y] + f[xx][yy])
			{
    
				if(cnt[xx][yy] > cnt[tt.x][tt.y] + 1)
				{
    
					path[xx][yy] = tt;
					q.push({
    dist[xx][yy], {
    xx, yy}});
				}
			}
		}
	}
	
}
//*/
signed main()
{
    
	fast;
	cin >> n >> m >> T;
	PII start;
	for(int i=0; i<=n+1; i++)
	{
    
		for(int j=0; j<=m+1; j++)
		{
    
			cin >> f[i][j];
			if(i == 0 || j == 0 || i == n + 1 || j == m + 1)
			{
    
				if((i == 0 && j == 0) || (i == 0 && j == m+1) || (i == n+1 && j == 0) || (i == n+1 && j == m+1)) continue;
				else v.push_back({
    i, j, f[i][j]});
			} 
			
			if(f[i][j] < 0) start = {
    i, j};
		}
	}
// /*
	dij(start);
// /*
	for(auto i : v)
	{
    
		int id = get({
    i.x, i.y});
		num[id] = i.z;
		PII kk;
	    for(int j = 0 ; j < 4 ; j++) //由僵尸边上走到地图里面去
            if(i.x + dx[j] >= 1 && i.x + dx[j] <= n && i.y + dy[j] >= 1 && i.y + dy[j] <= m)
			{
    
                kk.x = i.x + dx[j] , kk.y = i.y  + dy[j];
                break ;
			}
			
		while(1)
		{
    
            p[id].push_back(kk);
            if(kk.x == start.x && kk.y == start.y) break;//找到大本营的位置了
            kk = path[kk.x][kk.y];
        }
    }
    
// /*
    for(int t = 1; t <= T; t ++)
    {
    
// memcpy()
    	set<PII> s;
    	for(auto i : v)
    	{
    
    		int id = get({
    i.x, i.y});
    		
    		if(num[id] == 0) continue;
    		
    		int xx = p[id][now[id]].x;
    		int yy = p[id][now[id]].y;
    		
    		if(f[xx][yy] > 0 && (xx != start.x || yy != start.y)) s.insert({
    xx, yy});
    		else if(f[xx][yy] < 0 && (xx == start.x && yy == start.y)) s.insert({
    xx, yy});
		}
		
		for(auto i : v)
		{
    
			int id = get({
    i.x, i.y});
			
			if(num[id] == 0) continue;
			
            int xx = p[id][now[id]].x;
    		int yy = p[id][now[id]].y;
    		
    		if(s.count({
    xx, yy}) == 0) now[id] ++;//set中记录了哪些是炮台，所以不需要滚动数组优化 
    		else
    		{
    
    			if(f[xx][yy] > 0) f[xx][yy] --;//减到0就没了，不减了，根据输出来搞得 
    			else if(f[xx][yy] < 0) f[xx][yy]++;
    			num[id] --;
			}
			
		}
		
		if(f[start.x][start.y] == 0) break;
	}
// */
	 for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
    
        	cout << f[i][j];
            if(j < m) cout << " ";
            else cout << endl;
		}
            
    if(f[start.x][start.y] == 0) cout << "Game Over" << endl;
	return 0;
}
原网站

版权声明
本文为[Zqchang]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51176105/article/details/125630333

边栏推荐

猜你喜欢

随机推荐