当前位置:网站首页>2021 RoboCom 世界机器人开发者大赛-本科组(决赛)

2021 RoboCom 世界机器人开发者大赛-本科组(决赛)

2022-08-09 18:07:00 Alan_Lowe

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
[email protected] 218.109.231.189
[email protected] 112.192.203.187
[email protected] 112.18.235.143
[email protected] 112.192.203.187
[email protected] 113.18.235.143
[email protected] 111.192.203.187
[email protected] 218.109.231.189
[email protected] 111.18.235.143
[email protected] 115.192.203.187
[email protected] 113.189.58.141
[email protected] 111.192.203.187
[email protected] 112.18.58.145
[email protected] 114.192.203.187
[email protected] 112.18.235.143
[email protected] 123.89.158.214
[email protected] 112.18.235.143
[email protected] 218.109.231.189
[email protected] 113.192.203.187
[email protected] 218.109.231.189
[email protected] 114.192.203.187
[email protected] 113.189.58.141
[email protected] 123.89.158.214
[email protected] 113.192.203.187
[email protected] 112.18.58.145

输出样例1

[email protected]
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
[email protected]
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1
[email protected]
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1

输入样例2

24 5 8
[email protected] 218.109.231.189
[email protected] 112.192.203.187
[email protected] 112.18.235.143
[email protected] 112.192.203.187
[email protected] 113.18.235.143
[email protected] 111.192.203.187
[email protected] 218.109.231.189
[email protected] 111.18.235.143
[email protected] 115.192.203.187
[email protected] 113.189.58.141
[email protected] 111.192.203.187
[email protected] 112.18.58.145
[email protected] 114.192.203.187
[email protected] 112.18.235.143
[email protected] 123.89.158.214
[email protected] 112.18.235.143
[email protected] 218.109.231.189
[email protected] 113.192.203.187
[email protected] 218.109.231.189
[email protected] 114.192.203.187
[email protected] 113.189.58.141
[email protected] 123.89.158.214
[email protected] 113.192.203.187
[email protected] 112.18.58.145

输出样例2

[email protected]
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就不用说了,裸的迪杰斯特拉。

s->s的话,这个题目可以拆成s->i + i -> s这两段,但是边不能重复,因此要先将s->i最短路径上面的所有边都标记一下,然后再跑一次s->i(i->s),这次跑的时候就不能用已经被标记过的边了,也是迪杰斯特拉,只不过需要特殊处理判断一下边的使用情况。

代码

#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;
}
原网站

版权声明
本文为[Alan_Lowe]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_45985728/article/details/126224936