2021 RoboCom 世界机器人开发者大赛-本科组（决赛）
1.绿地围栏
思路
模拟题目，主要是记住最后要把原点加入到目标点当中，不然最后一个测试点过不了。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
int n, l, now_l, x, y;
vector<pii> v;
void init(){
cin >> n >> l;
for (int i = 1; i <= n; ++i) {
if (i & 1) cin>>y;
else cin>>x;
v.emplace_back(x,y);
}
v.emplace_back(0,0); //这里很重要，因为要走回原点，这里如果不加上的话，最后一个测试点就会错。
}
void solve(){
x = y = 0;now_l = l;
cout<<x<<" "<<y<<"\n";
for (pii &p : v) {
while (x != p.first || y != p.second){
if (x == p.first){ //如果当前是纵向
if (y < p.second) //向上
++y;
else //向下
--y;
}
else{ //如果当前是横向
if (x < p.first) //向右
++x;
else //向左
--x;
}
--now_l;
if (now_l == 0){
if (x != 0 || y != 0)
cout<<x<<" "<<y<<"\n";
now_l = l;
}
}
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
init();
solve();
return 0;
}
2.队列插入
思路×
不太会，每理解大佬的思路，以后有机会补
代码×
3.账户安全预警
输入样例1
24 3 4
daohaole@qq.com 218.109.231.189
1jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 113.18.235.143
jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 218.109.231.189
chenyuelaolao@zju.edu.cn 111.18.235.143
1jiadelaolao@163.com 115.192.203.187
daohaole@qq.com 113.189.58.141
1jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 112.18.58.145
1jiadelaolao@163.com 114.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
daohaole@qq.com 123.89.158.214
chenyuelaolao@zju.edu.cn 112.18.235.143
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 114.192.203.187
youdaohaole@qq.com 113.189.58.141
youdaohaole@qq.com 123.89.158.214
1jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 112.18.58.145
输出样例1
1jiadelaolao@163.com
111.192.203.187 1
112.192.203.187 1
113.192.203.187 1
114.192.203.187 1
115.192.203.187 1
daohaole@qq.com
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1
youdaohaole@qq.com
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1
输入样例2
24 5 8
daohaole@qq.com 218.109.231.189
1jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 113.18.235.143
jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 218.109.231.189
chenyuelaolao@zju.edu.cn 111.18.235.143
1jiadelaolao@163.com 115.192.203.187
daohaole@qq.com 113.189.58.141
1jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 112.18.58.145
1jiadelaolao@163.com 114.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
daohaole@qq.com 123.89.158.214
chenyuelaolao@zju.edu.cn 112.18.235.143
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 114.192.203.187
youdaohaole@qq.com 113.189.58.141
youdaohaole@qq.com 123.89.158.214
1jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 112.18.58.145
输出样例2
1jiadelaolao@163.com
111.192.203.187 1
112.192.203.187 1
113.192.203.187 1
114.192.203.187 1
115.192.203.187 1
思路
嵌套map，用外层map的键表示邮箱，外层map的值也是一个map（内层map），内层map的键表示ip，值表示ip出现的次数，最后遍历一下，按照规定要求排序后输出即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define psi pair<string,int>
int n, Tip, Tlogin;
map<string, map<string, int> > mp;
struct node{
string email; //邮箱
vector<psi> ip; //存ip登录信息
int tip; //ip总数
int tlogin; //登录次数
};
vector<node> v, v1;
bool cmp(const node& a,const node& b){
if (a.tip != b.tip)
return a.tip > b.tip;
return a.email < b.email;
}
bool CMP(psi a, psi b){
if (a.second != b.second)
return a.second > b.second;
return a.first < b.first;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>Tip>>Tlogin;
string s, ip;
for (int i = 0; i < n; ++i) {
cin>>s>>ip;
mp[s][ip] += 1;
}
for (const auto& it : mp) {
node a;
a.tlogin = 0;
a.email = it.first;
a.tip = it.second.size();
for (const auto& x : it.second) {
a.ip.emplace_back(x.first, x.second);
a.tlogin += x.second;
}
v.push_back(a);
}
for (auto & i : v)
if (i.tip > Tip && i.tlogin > Tlogin)
v1.push_back(i);
if (!v1.empty()){
sort(v1.begin(),v1.end(),cmp);
for (node &it : v1) {
sort(it.ip.begin(),it.ip.end(),CMP);
cout<<it.email<<"\n";
for (psi &p : it.ip) {
cout<<p.first<<" "<<p.second<<"\n";
}
}
}
else{
sort(v.begin(),v.end(),cmp);
for (node &it : v) {
if (it.tip != v[0].tip)
break;
cout<<it.email<<"\n";
sort(it.ip.begin(),it.ip.end(),CMP);
for (psi &p : it.ip) {
cout<<p.first<<" "<<p.second<<"\n";
}
}
}
return 0;
}
4.猛犸不上 Ban
输入样例
5 6 1 5
1 2 1
2 3 2
3 4 3
4 1 5
3 5 4
4 5 1
输出样例
11 6
Lose!
思路
去年比赛的时候硬写了个搜索处理s->s的情况。
这个题目看到一些大佬的题解，还是很容易理解的。
s->t就不用说了，裸的迪杰斯特拉。文章来源：https://www.toymoban.com/news/detail-595006.html
s->s的话，这个题目可以拆成s->i + i -> s这两段，但是边不能重复，因此要先将s->i最短路径上面的所有边都标记一下，然后再跑一次s->i（i->s），这次跑的时候就不能用已经被标记过的边了，也是迪杰斯特拉，只不过需要特殊处理判断一下边的使用情况。文章来源地址https://www.toymoban.com/news/detail-595006.html
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int inf;
int n,m,s,t; //如题
int mp[505][505]; //存边
int dis[505]; //表示s到每个点的距离
int dis1[505]; //表示删除第一条路径上的边之后的最短距离
int vis[505]; //标记每个点是否被访问过
int vis1[505][505]; //标记每条边是否被访问过
int pre[505]; //表示每个点的前序最优结点
void init(){
cin>>n>>m>>s>>t;
memset(mp,0x3f,sizeof mp);
memset(dis,0x3f,sizeof dis);dis[s] = 0;
memset(pre,255,sizeof pre);
inf = dis[0];
while (m--){
int from,to,value;cin>>from>>to>>value;
mp[from][to] = mp[to][from] = value;
}
}
void dij(){
while (true){
int mn = inf,k = -1;
for (int i = 1; i <= n; ++i)
if (!vis[i] && dis[i] < mn)
mn = dis[i],k = i;
if (k == -1)
break;
vis[k] = true;
for (int i = 1; i <= n; ++i) {
if (dis[i] > dis[k] + mp[k][i])
dis[i] = dis[k] + mp[k][i],pre[i] = k;
}
}
}
void dij1(){
memset(dis1,0x3f,sizeof dis1);dis1[s] = 0;
memset(vis,0,sizeof vis);
while (true){
int mn = dis1[0],k = -1;
for (int i = 1; i <= n; ++i)
if (!vis[i] && dis1[i] < mn)
mn = dis1[i],k = i;
if (k == -1)
break;
vis[k] = true;
for (int i = 1; i <= n; ++i) {
if (vis1[k][i])
continue;
if (dis1[i] > dis1[k] + mp[k][i])
dis1[i] = dis1[k] + mp[k][i];
}
}
}
int solve(){
//将s->s 拆分成s->i + i->s
int ans = inf;
for (int i = 1; i <= n; ++i) { //遍历每个中间点i
if (i == s)
continue;
for (int from = pre[i], to = i; from != -1 ; to = from, from = pre[from]) {
vis1[from][to] = vis1[to][from] = true;
} //将所有的该路径上的边标记为使用过
dij1();
ans = min(ans,dis[i] + dis1[i]);
for (int from = pre[i], to = i; from != -1 ; to = from, from = pre[from]) {
vis1[from][to] = vis1[to][from] = false;
} //去除标记
}
return ans;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
init(); //输入等初始化操作
dij(); //跑s->t并且存储pre
int ans2 = dis[t];
int ans1 = solve(); //处理s->s
cout<<(ans1 == inf ? -1 : ans1)<<" ";
cout<<(ans2 == inf ? -1 : ans2)<<"\n";
cout<<(ans1 < ans2 ? "Win!" : "Lose!");
return 0;
}
到了这里，关于2021 RoboCom 世界机器人开发者大赛-本科组（决赛）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
