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

比赛介绍

• 比赛信息
  比赛官网：https://www.robocom.com.cn/
  报名流程：https://www.robocom.com.cn/content.html?cid=386
  工信部发文：https://www.robocom.com.cn/content.html?cid=367
  中国教育学会清单：https://m.cahe.edu.cn/site/content/14825.html
  编程赛道通知：https://www.robocom.com.cn/content.html?cid=369
  

• 赛制说明：
  CAIA数字创意赛道FAQ
  CAIP编程设计赛道FAQ
  CAIR工程竞技赛道FAQ
  编程技能普及赛是什么赛制？
  严格意义上来说不算ioi赛制，类似天梯赛。因为是个人赛所以不像天梯赛还有团队分。
  题量是多少道题？难度如何？本科组去年4道题，本科组赛题难度类似PAT甲级中文。
  可分为省赛和国赛的奖项，省赛一二等奖晋级国赛；其中省赛获奖比例：20%，30%，40%，10%分别对应一、二、三和优秀奖；国赛获奖比例：10%，30%，60%分别对应一、二和三等奖。
  

• 补题信息：
  PTA教育超市：https://pintia.cn/market
  

7-1 懂的都懂(20分)

众所周知，在互联网上有很多话是不好直接说出来的，不过一些模糊的图片仍然能让网友看懂你在说什么。然而对这种言论依然一定要出重拳，所以请你实现一个简单的匹配算法。

现在我们采集了原图的一些特征数据，由 N 个小于 255 的非负整数组成，假设对于给定的若干张由 M
i
​
个同样小于 255 的非负整数组成的新图的特征数据，每个数据都可以由原图中任意四个不同数据的平均值计算而来，则称新图为原图的相似图片。对于给出的数据，请你判断是不是相似图片。

注意，不同数据指的并非是数据的值不同，而是不能取同一个数据多次。对于两个相同值的数据，如果给出两次，则可以取两次。

输入格式:
输入第一行是两个整数 N,K (1 ≤ N ≤ 50, 1 ≤ K ≤ 200)，表示采集的原图的特征数据个数和新图的张数。

接下来一行为 N 个小于 255 的非负整数，表示原图的特征数据。

最后的 K 行，每行第一个数是 M
i
​
(1 ≤ M
i
​
≤ 200)，表示新图的特征数据个数。然后是 M
i
​
个小于 255 的非负整数，表示新图的特征数据。

输出格式:
对于每一张新图，如果为相似图片，则在一行中输出 Yes，否则输出 No。

输入样例:
5 3
4 8 12 20 40
3 11 16 19
3 12 16 19
10 11 11 11 11 11 11 11 11 11 11
输出样例:
Yes
No
Yes

• 题意：给出一个初始数组，判断后面的n个数组是否每个数都能由第一个数组中的某四个数取平均值得到。
• 思路：直接dfs 4层所有的方案,（4⁵⁰会T，但是50⁴不会T），开个set维护所有可行数字然后判断就行。
  注意坑点，如果不能整除就不要去除，不然只有10分。同时第一个数组的数字也不在set里。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
int n, k, a[maxn], vis[maxn];
set<int>se;
void dfs(int cur, int now){
    if(cur == 4){
        if(now%4==0)se.insert(now/4);//WA
        return ;
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            vis[i] = 1;
            dfs(cur+1, now+a[i]);
            vis[i] = 0;
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i = 1; i <= n; i++){
        cin>>a[i];  //se.insert(a[i]);
    }
    dfs(0, 0);
    while(k--){
        int m;  cin>>m;
        int ok = 1;
        for(int i = 1; i <= m; i++){
            int x;  cin>>x;
            if(!se.count(x))ok = 0;
        }
        if(ok)cout<<"Yes\n";
        else cout<<"No\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
 

7-2 芬兰木棋（25分）

芬兰木棋（Mölkky，又称芬兰木柱）是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版，现在场上一开始有 N 根立起的小木棋（上面分别标有一个非负整数），哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下：

如果仅击倒 1 根木棋，则得木棋上的分数。
如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）
哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (X
i
​
,Y
i
​
)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。

请问哲哲最多能拿多少分，在获得最多分数的情况下最少需要扔出多少次大木棋？

规则与真实规则有较大出入，真实游玩时请以国际莫尔基组织的规则为准

输入格式:
输入第一行是一个正整数 N (1 ≤ N ≤ 10
5
)，表示场上一开始有 N 个木棋。

接下来 N 行，每行 3 个整数 X
i
​
,Y
i
​
,P
i
​
，分别表示木棋放置在 (X
i
​
,Y
i
​
)，木棋上的分数是 P
i
​
。坐标在 32 位整数范围内，分数为小于等于 1000 的正整数。

保证 (0,0) 点没有木棋，也没有木棋重叠放置。

输出格式:
输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。

输入样例:
11
1 2 2
2 4 3
3 6 4
-1 2 2
-2 4 3
-3 6 4
-1 -2 1
-2 -4 1
-3 -6 1
-4 -8 2
2 -1 999
输出样例:
1022 9

• 题意：有n个坐标上都有分数，每次可以拿到一个坐标上的所有分数，或者x个坐标都作为分数1同时被拿掉，拿的时候必须遵守顺序从近到远拿，不能跳着拿，且每次只能拿同一个方向的。
  求最大能拿多少分数，此时的最少次数。
• 不难想到：
  可以无限次拿，所以最大分数肯定是全部加起来。
  然后因为x个一起拿，那么对于>1的就损失了分数，所以>1的肯定要一次，=1的尽量一起拿。
• 没说清楚的：
  每次只能拿同方向的，所以开个map对斜率分类，而且要double。。。
  因为是站在原点，所以更近的同方向，即拿的顺序指的是，-3,-2,-1,0（一起拿√）,1,2,3（按照x,y从小到大排序即可），而不是距离上按照x*x+y*y从小到大排序-1,1,-2,2,-3,3（会WA）

#include<bits/stdc++.h>
using namespace std;
struct node{ int x, y, v; };
bool cmp(node x, node y){ return x.x!=y.x? x.x<y.x : x.y<y.y; }
map<double, vector<node> >mp;
int main(){
    int n;  cin>>n;
    int sum = 0, cnt = 0;
    for(int i = 1; i <= n; i++){
        int x, y, v;  cin>>x>>y>>v;
        sum += v;  //sum肯定全拿
        mp[y*1.0/x].push_back(node{x,y,v});//按斜率（方向）分类
    }
    for(auto x : mp){ //枚举每个方向
        vector<node>vc = x.second; 
        sort(vc.begin(), vc.end(), cmp);//按x,y排序
        for(int i = 0; i < vc.size(); i++){
            if(i==0 || vc[i].v!=1 || vc[i-1].v!=1){
                cnt++;
            }
        }
    }
    cout<<sum<<" "<<cnt<<"\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
 

7-3 打怪升级（25分）

很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。

你的任务有两件：

帮助玩家确定一个最合算的空降位置，即空降到地图中的某个堡垒，使得玩家从这个空降点出发，到攻下最难攻克（即耗费能量最多）的那个堡垒所需要的能量最小；
从这个空降点出发，帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一，则选择沿途缴获武器总价值最高的解，题目保证这种解是唯一的。
输入格式:
输入第一行给出两个正整数 N (≤1000) 和 M，其中 N 是堡垒总数，M 是怪兽总数。为简单起见，我们将堡垒从 1 到 N 编号。随后 M 行，第 i 行给出了第 i 只怪兽的信息，格式如下：

B1 B2 怪兽能量 武器价值
其中 B1 和 B2 是怪兽把守的道路两端的堡垒编号。题目保证每对堡垒之间只有一只怪兽把守，并且 怪兽能量 和 武器价值 都是不超过 100 的正整数。

再后面是一个正整数 K（≤N）和玩家想要攻克的 K 个目标堡垒的编号。

输出格式:
首先在一行中输出玩家空降的堡垒编号 B0。如果有多种可能，则输出编号最小的那个。

随后依次为玩家想要攻克的每个堡垒 B 推荐最省能量的攻克路径，并列出需要耗费的能量值和沿途缴获武器的总价值。注意如果最省力的路径不唯一，则选择沿途缴获武器总价值最高的解。格式为：

B0->途经堡垒1->…->B
总耗费能量 武器总价值
输入样例:
6 12
1 2 10 5
2 3 16 20
3 1 4 2
2 4 20 22
4 5 2 2
5 3 12 6
4 6 8 5
6 5 10 5
6 1 20 25
1 5 8 5
2 5 2 1
2 6 8 5
4
2 3 6 5
输出样例:
5
5->2
2 1
5->1->3
12 7
5->4->6
10 7
5
0 0

• 题意：给出n个点m条边的无向图，每条边有一个代价和一个价值，对于每个点求最大代价的点，记最小的为起点。然后从起点出发到其他所有点的最小代价路径，代价相同时找最大价值，打印路径。
• 思路：
  floyed跑多源最短路，令最长路最短，即为起点RT。
  Dijkstra跑单源最短路（w1最小，w2最大），打印路径即可。
  e数组没初始化WA2改了一个多小时无语死了

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int inf = 1e9+10;
const int maxn = 1010;

int e[maxn][maxn];
struct edge{ int to, w1, w2; };
vector<edge>G[maxn];
struct node{
    int u, w1, w2; 
    bool operator < (const node &b)const{ return w1!=b.w1 ? w1>b.w1 : w2<b.w2; }
};

int dist[maxn], dist2[maxn], vis[maxn], pre[maxn];
void print(int x){
    if(pre[x]==-1)return ;
    print(pre[x]);
    cout<<"->"<<x;
}

int main(){
    memset(e,0x3f,sizeof(e)); //WA2
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int u, v, w1, w2;  cin>>u>>v>>w1>>w2;
        e[u][v] = e[v][u] = w1;
        G[u].push_back({v,w1,w2});
        G[v].push_back({u,w1,w2});
    }
    //1, floyed跑多源，令最长路最短
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                e[i][j] = min(e[i][j], e[i][k]+e[k][j]);
            }
        }
    }
    int rt = -1, mx = inf;
    for(int i = 1; i <= n; i++){
        int tmp = 0;
        for(int j = 1; j <= n; j++)
            tmp = max(tmp, e[i][j]);
        if(tmp < mx){
            mx = tmp;  rt = i;
        }
    }
    //2, Dijkstra跑单源，打印路径
    for(int i = 1; i <= n; i++)dist[i] = inf, pre[i] = -1;
    priority_queue<node>q;
    dist[rt] = 0, dist2[rt] = 0;
    q.push({rt,dist[rt],dist2[rt]});
    while(q.size()){
        int u = q.top().u;  q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(edge nt : G[u]){
            int v = nt.to;
            if(dist[v] > dist[u]+nt.w1){
                dist[v] = dist[u]+nt.w1;
                dist2[v] = dist2[u]+nt.w2;
                pre[v] = u;
                q.push({v,dist[v], dist2[v]});
            }else if(dist[v]==dist[u]+nt.w1 && dist2[nt.to]<dist2[u]+nt.w2){
                dist2[v] = dist2[u]+nt.w2;
                pre[v] = u;
                q.push({v,dist[v], dist2[v]});
            }
        }
    }
    //3, T次打印
    cout<<rt<<"\n";
    int T;  cin>>T;
    while(T--){
        int x;  cin>>x;
        cout<<rt;
        print(x);
        cout<<"\n";
        cout<<dist[x]<<" "<<dist2[x]<<"\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
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
 

7-4 疫情防控（30分）

疫情尚未结束，严防疫情反复。为了做好疫情防控工作，国内设置了地区风险等级，对于中高风险地区的人员采取限制移动、居家隔离等手段。

为了研究疫情防控对于跨地区交通运输的影响，假设现在有 N 个机场，M 条航线，每天都会新增一个防控地区，一个防控地区会导致一个机场无法正常运作，航线也自然无法正常运行，每天会有 Q
i
​
对旅客从 X
i
​
机场前往 Y
i
​
机场，请计算有多少对旅客会受到影响无法完成行程。

旅客只要能直达或通过若干次中转，且乘坐的所有航线的出发和到达机场都正常运作，即视作可完成行程。

输入格式:
输入第一行是三个整数 N,M,D (1≤N≤5×10
4
, 1≤M≤2×10
5
, 1≤D≤10
3
), 表示机场数、航线数以及新增防控地区的天数。

接下来首先有 M 行，每行给出空格分隔的两个数字 A 和 B，表示编号为 A 和 B 的机场之间有一条航线。航线是双向的，机场编号从 1 到 N。

然后是 D 块输入，每块输入内第一行为空格分隔的两个整数 C 和 Q （1≤Q≤10
3
)，表示新增机场编号为 C 所在的城市为防控地区，今天有 Q 段行程。数据保证新增的城市之前一定不是防控地区。

接下来的 Q 行，每行是空格分隔的两个数字 X 和 Y，表示编号为 X 和 Y 的机场的一段行程。行程有可能包括之前就已经成为防控地区的城市。

输出格式:
对于每天的询问，请在一行中输出在新增了一个防控地区后当天的行程有多少不能成行。

输入样例:
5 5 3
1 2
1 3
1 5
2 5
3 4
4 3
1 3
1 4
2 3
5 3
3 4
2 3
3 5
1 3
2 3
2 5
3 4
输出样例:
1
2
3

• 题意：给出n个点，m条边的无向图，接下来d天每天删掉一个点c（累加），然后q次询问每次问删掉c后某两点u,v能否联通。
• 思路：考虑暴力O(每天d*重新建图m*询问q*是否联通n)复杂度直接上天。
  这里的难点在于每次删掉一个点后要重新建图需要大量的时间，因为我们可以离线所有的询问反向建图，这样较难的删点就变成了简单的往图上加点，任意两点的连通性也由需要O(n)暴力变成了可以使用并查集logn维护的。
• 具体来说：记录下第i天删了谁，有哪些询问。从d天开始往前，每天加一个点，然后并查集直接判断一下是否联通即可。注意加点的时候需要考虑当前点连向的点必须是没有被删的，不然会WA。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

vector<int>G[maxn];
vector<pair<int,int> >query[maxn]; //第i天的航班
int dd[maxn], vis[maxn]; //第i天挂了谁，城市i挂了没
int ans[maxn];

int main(){
    int n, m, d;  cin>>n>>m>>d;
    for(int i = 1; i <= m; i++){
        int u, v;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    //离线询问
    for(int i = 1; i <= d; i++){
        int c, q;  cin>>c>>q;
        vis[c] = 1;
        dd[i] = c;
        while(q--){
            int u, v;  cin>>u>>v;
            query[i].push_back(make_pair(u,v));
        }
    }
    init(n+1);
    for(int i = 1; i <= n; i++){//最后没挂的连起来
        if(vis[i]==0){
            for(int j = 0; j < G[i].size(); j++){
                if(vis[G[i][j]]==0)merge(i,G[i][j]);
            }
                
        }
    }
    for(int i = d; i >= 1; i--){
        for(int j = 0 ; j < query[i].size(); j++){
            int x = find(query[i][j].first), y = find(query[i][j].second);
            if(x != y)ans[i]++;
        }
        vis[dd[i]] = 0;  //现在它复活了，加回去
        for(int j = 0; j < G[dd[i]].size(); j++){
            if(vis[G[dd[i]][j]]==0)merge(dd[i], G[dd[i]][j]);
        }
    }
    for(int i = 1; i <= d; i++)
        cout<<ans[i]<<"\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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/124525420