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

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

1.绿地围栏

思路

模拟题目，主要是记住最后要把原点加入到目标点当中，不然最后一个测试点过不了。

代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

输出样例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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入样例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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

输出样例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
1
2
3
4
5
6

思路

嵌套map，用外层map的键表示邮箱，外层map的值也是一个map（内层map），内层map的键表示ip，值表示ip出现的次数，最后遍历一下，按照规定要求排序后输出即可。

代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

4.猛犸不上 Ban

输入样例

5 6 1 5
1 2 1
2 3 2
3 4 3
4 1 5
3 5 4
4 5 1
1
2
3
4
5
6
7

输出样例

11 6
Lose!
1
2

思路

去年比赛的时候硬写了个搜索处理s->s的情况。

这个题目看到一些大佬的题解，还是很容易理解的。

s->t就不用说了，裸的迪杰斯特拉。

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

代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87