当前位置:网站首页>2021RoboCom机器人开发者大赛(初赛)
2021RoboCom机器人开发者大赛(初赛)
2022-07-06 04:43:00 【Zqchang】
题目
题解
7-1 懂的都懂
分数 20
直接暴力
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 55, K = 260;
int f[N][K];//选i个数,平均值是j
int vis[K];
int v[N];
int n, kk;
signed main()
{
cin >> n >> kk;
for(int i=1; i<=n; i++) cin >> v[i];
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
for(int k=j+1; k<=n; k++)
for(int p=k+1; p<=n; p++)
{
int t = v[i] + v[j] + v[k] + v[p];
if(t % 4) continue;
else t /= 4;
// cout << t << endl;
vis[t] = 1;
}
while(kk --)
{
int m, x; cin >> m;
bool flag = 0;
for(int i=1; i<=m; i++)
{
cin >> x;
if(!vis[x]) flag = 1;
}
if(!flag) puts("Yes");
else puts("No");
}
return 0;
}
7-2 芬兰木棋
这个题一开始读了假题,因为距离原点的距离不同,所以你要对她进行排序,然后不能存斜率,不能存斜率!!坑惨了,因为是四个象限,所以只能存gcd之后的数,而且gcd要加绝对值,要不然就会改变象限,注意它可以扔无限多次,也就是分数肯定都能拿到
分数 25
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e5 + 10;
#define PII pair<int, int>
#define INF 0x3f3f3f3f
#define x first
#define y second
map<PII, vector<PII> > v;
set<PII> s;
int n;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
signed main()
{
cin >> n;
int a, b, c;
for(int i=1; i<=n; i++)
{
cin >> a >> b >> c;
int p = gcd(a, b);
p = abs(p);
v[{
a / p, b / p}].push_back({
a * a + b * b, c});
s.insert({
a / p, b / p});
}
int ans = 0;
int res = 0;
for(auto i : s)
{
int len = 0;
sort(v[i].begin(), v[i].end());
for(auto j : v[i])
{
if(j.y > 1)
{
ans++;
res += j.y;
if(len)
{
ans ++;
len = 0;
}
}
else
{
len ++;
res ++;
}
}
if(len) ans ++;
}
cout << res << " " << ans << endl;
return 0;
}
7-3 打怪升级
分数 25
这个emm,debug发现是一个小错,绝了,就是flody先找出发点,注意是每个最短路里面的最大值进行比较,从最大值里面选最小值!!
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
#define INF 0x3f3f3f3f
const int N = 1010;
int dist[N];
int val[N];
int mu[N];
int n, m;
int st[N];
int g[N][N], gg[N][N];
int v[N][N];
int pre[N];
void dij(int root)
{
memset(dist, 0x3f, sizeof dist);
memset(st,0,sizeof st);
dist[root] = 0;
val[root] = 0;
for(int i=0; i<n; i++)
{
int t = -1;
for(int j=1; j<=n; j++)
if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
st[t] = 1;
for(int j=1; j<=n; j++)
{
if(dist[j] > dist[t] + g[t][j])
{
dist[j] = dist[t] + g[t][j];
val[j] = val[t] + v[t][j];
pre[j] = t;
}
else if(dist[j] == dist[t] + g[t][j])
{
if(val[j] < val[t] + v[t][j])
{
val[j] = val[t] + v[t][j];
pre[j] = t;
}
}
}
}
}
signed main()
{
memset(g, 0x3f, sizeof g);
cin >> n >> m;
for(int i=1; i<=n; i++) g[i][i] = 0;
int a, b, c, d;
for(int i=1; i<=m; i++)
{
cin >> a >> b >> c >> d;
v[a][b] = v[b][a] = d;
g[a][b] = g[b][a] = c;
}
memcpy(gg, g, sizeof g);
for(int kk=1; kk<=n; kk++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
gg[i][j] = min(gg[i][j], gg[i][kk] + gg[kk][j]);
int root = -1, maxn = INF;
for(int i=1; i<=n; i++)
{
int tmp = 0;
for(int j=1; j<=n; j++)
tmp = max(tmp, gg[i][j]);
if(tmp < maxn)
{
maxn = tmp;
root = i;
}
}
cout << root << endl;
dij(root);
int k;
cin >> k;
for(int i=1; i<=k; i++) cin >> mu[i];
vector<int> l;
for(int i=1; i<=k; i++)
{
int rt = mu[i];
l.clear();
while(rt != root)
{
l.push_back(rt);
rt = pre[rt];
}
reverse(l.begin(), l.end());
cout << rt;
for(auto i : l)
{
cout << "->" << i;
}
cout << endl;
cout << dist[mu[i]] << " " << val[mu[i]] << endl;
}
return 0;
}
7-4 疫情防控
分数 30
这个思路很重要,因为删除点是从前往后进行删除,删到后面的时候,前面的已经被删了,所以可以反过来,从最后一个开始往前加点,因为这样,从最后一个慢慢加到第一个的时候,当到第一个的时候,后面的肯定没删,然后发现这种做法也都加上了,就很巧妙!
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
//#define int long long
#define PII pair<int, int>
#define x first
#define y second
const int N = 5e4 + 10, M = 2e5 + 10, D = 1e3 + 10;
int n, m, c, q, d;
vector<int> v[N];
vector<PII> query[D];
int p[N];
bool vis[N];
int id[N];
int ans[N];
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b)
{
a = find(a);
b = find(b);
if(a != b) p[a] = b;
}
signed main()
{
cin >> n >> m >> d;
int a, b;
for(int i=1; i<=n; i++) p[i] = i;
for(int i=1; i<=m; i++)
{
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=1; i<=d; i++)
{
cin >> c >> q;
id[i] = c;
vis[c] = 1;
for(int j=1; j<=q; j++)
{
cin >> a >> b;
query[i].push_back({
a, b});
}
}
for(int i=1; i<=n; i++)
if(!vis[i])
for(auto j : v[i])
if(!vis[j]) merge(i, j);
for(int i=d; i>=1; i--)
{
for(auto j : query[i])
{
a = find(j.x);
b = find(j.y);
if(a != b) ans[i] ++;
}
vis[id[i]] = 0;
for(auto j : v[id[i]])
if(!vis[j]) merge(id[i], j);
}
for(int i=1; i<=d; i++) cout << ans[i] << endl;
return 0;
}
边栏推荐
- 饼干(考试版)
- Orm-f & Q object
- P3500 [poi2010]tes intelligence test (two points & offline)
- P2022 interesting numbers (binary & digit DP)
- View workflow
- ORM aggregate query and native database operation
- 内核判断i2c地址上是否挂载外设
- [mathematical modeling] differential equation -- sustainable development of fishing industry
- win10电脑系统里的视频不显示缩略图
- cdc 能全量拉去oracle 表嘛
猜你喜欢
The most detailed and comprehensive update content and all functions of guitar pro 8.0
RTP GB28181 文件测试工具
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (柔性对接 AutoDock)
8. Static file
CADD course learning (8) -- virtual screening of Compound Library
Basic knowledge and examples of binary tree
IPv6 comprehensive experiment
Redis - redis in action - redis actual combat - actual combat Chapter 1 - SMS login function based on redis - redis + token shared session application - with code
ue5 小知识点 开启lumen的设置
Certbot failed to update certificate solution
随机推荐
Ue5 small knowledge points to enable the setting of lumen
The value of two date types is subtracted and converted to seconds
行业专网对比公网,优势在哪儿?能满足什么特定要求?
也算是学习中的小总结
Lagrange polynomial
On the solution of es8316's audio burst
[数学建模] 微分方程--捕鱼业的持续发展
NPM command -- install dependent packages -- Usage / explanation
拉格朗日插值法
项目经理,你会画原型嘛?项目经理需要做产品设计了?
Dry goods collection | Vulkan game engine video tutorial
力扣(LeetCode)186. 翻转字符串里的单词 II(2022.07.05)
How to realize automatic playback of H5 video
Basic explanation of turtle module - draw curve
Tengine kernel parameters
[network] channel attention network and spatial attention network
web工程导入了mysql驱动jar包却无法加载到驱动的问题
Visio draws Tai Chi
ORM aggregate query and native database operation
P2102 floor tile laying (DFS & greed)