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

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

1.懂的都懂【暴力】

思路

取四个数，那就直接n的4次方遍历每种可能，然后放到一个set当中就行，对于每一张新的图片都判断是否每个特征值都能在这个set中找到，如果是的话输出Yes，否则输出No。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define int long long

int n, k;
int x[55];
set<int> s;
signed main(){
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i = 1;i <= n;++i)       //输入原始图片
        cin>>x[i];
    for (int i = 1; i <= n; ++i)  //遍历出选四个数的每种情况
        for (int j = i + 1; j <= n; ++j)
            for (int l = j + 1; l <= n; ++l)
                for (int m = l + 1; m <= n; ++m)
                    s.insert((x[i] + x[j] + x[l] + x[m]));
    while(k--){
                         //k张新的图片的处理
        bool f = true;int a,b;
        cin>>a;
        for (int i = 0; i < a; ++i) {
    
            cin>>b;
            if (s.count(b * 4) == 0)    //只要有一个值不在s中，就输出no
                f = false;
        }
        if (f)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}

2.芬兰木棋【思维】

思路

按照木桩与原点的距离来排序，然后从近到远去处理，对于相同方向的木桩，如果有连续高度为1的，那么就一次打倒多跟木桩，这是在保证分数相同的情况下，打的次数最少；否则每次打倒一根木桩即可。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
const int N = 1e5 + 5;
int gcd(int a,int b){
    return b ? gcd(b,a % b) : a;}
int n,v;
pair<pii, int> edge[N];     //表示木棋的横坐标、纵坐标、分数
map<pii, int> mp;           //pii表示某个方向，int表示该方向上目前有多少个连续的木棋分数为1
int ans_1,ans_2;            //最多的分数、最少的次数
bool cmp(pair<pair<int,int> ,int> a,pair<pair<int,int> ,int> b){
        //按照和原点的距离排序
    return a.first.first * a.first.first + a.first.second * a.first.second <
            b.first.first * b.first.first + b.first.second * b.first.second;
}
signed main(){
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 0; i < n; ++i) {
           //输入木棋的坐标和分数
        cin>>edge[i].first.first>>edge[i].first.second>>edge[i].second;
    }
    sort(edge,edge + n,cmp);        //排序
    for (int i = 0; i < n; ++i) {
           //对于每一个木棋，都将横纵坐标除以最大公约数，用来区分每个方向
        int g = gcd(abs(edge[i].first.first), abs(edge[i].first.second));
        edge[i].first.first /= g;edge[i].first.second /= g;
    }
    for (int i = 0; i < n; ++i) {
    
        if (edge[i].second == 1){
       //如果为1就记录下来
            mp[edge[i].first] += 1;
        }
        else{
                           //否则把该方向上前面的1一次全部打掉，然后再打掉现在这个木棋
            if(mp[edge[i].first] > 0){
    
                ans_1 += mp[edge[i].first];
                mp[edge[i].first] = 0;
                ans_2 += 1;
            }
            ans_1 += edge[i].second;
            ans_2 += 1;
        }
    }
    for (auto it = mp.begin();it!=mp.end();++it) {
          //如果还有某个方向上有连续的1
        if (it->second > 0){
    
            ans_1 += it->second;
            ans_2 += 1;
        }
    }
    cout<<ans_1<<" "<<ans_2;
    return 0;
}

3.打怪升级【Floyed+Dijkstra】

思路

首先用一个多源最短路跑出来，然后选择起点（找最长路线的最小值）。然后有了起点过后，再跑一次单源最短路并且记录路径。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define psi pair<string,int>
const int N = 5e5 + 5,inf = 0x3f3f3f3f,INF = 1e18,MOD = 1e9 + 7;
struct node{
    
    int p, w1, w2;  //点的编号、起点到该点的最短距离、最大价值
};
struct edge{
    
    int to, w1, w2; //边的终点、距离、价值
};
int n,m,k;
vector<int> mubiao; //目标堡垒
int pre[1005];      //存储前驱结点
int dis[1005][1005], dis1[1005], dis2[1005];    //分别用来找出发点、出发点到该点的距离、出发点到该点的价值
vector<edge> M[1005];       //存边
bool vis[1005];         //判断一个结点是否已经访问过，用于dij

struct cmp{
    
    bool operator()(node a,node b){
    
        if (a.w1 == b.w1)
            return a.w2 < b.w2;
        return a.w1 > b.w1;
    }
};
void init(){
    
    cin>>n>>m;
    memset(dis,0x3f,sizeof dis);
    memset(dis1,0x3f,sizeof dis1);
    for(int i = 1;i <= n;++i)
        dis[i][i] = 0;
    int a,b,c,d;
    while(m--){
    
        cin>>a>>b>>c>>d;
        dis[a][b] = dis[b][a]  = c;
        M[a].push_back(edge{
    b,c,d});
        M[b].push_back(edge{
    a,c,d});
    }
    cin>>k;
    while (k--)
        cin>>a,mubiao.push_back(a);
}
void floyed(){
    
    for (int k = 1; k <= n; ++k) {
    
        for (int i = 1; i <= n; ++i) {
    
            for (int j = 1; j <= n; ++j) {
    
                dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
            }
        }
    }
}
void print(int x){
    
    if (pre[x] == -1)
        return;
    print(pre[x]);
    cout<<"->"<<x;
}
signed main(){
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    init();     //初始化
    floyed();   //floyed跑多元最短路
    int from = 0, mn = 0x3f3f3f3f;  //要选择的出发点
    for (int i = 1; i <= n; ++i) {
    
        int sum = 0;
        for(int j = 1;j <= n;++j)
            if (sum < dis[i][j])
                sum = dis[i][j];
        if (sum < mn)
            mn = sum, from = i;
    }
    cout<<from<<"\n";

    for (int i = 1; i <= n; ++i)
        pre[i] = -1;        //存储每个点的前驱结点
    
    dis1[from] = 0;
    priority_queue<node,vector<node>,cmp> q;q.push(node{
    from, 0, 0});
    while (!q.empty()){
    
        int p = q.top().p; q.pop();
        if (vis[p])
            continue;
        vis[p] = true;
        for (edge now : M[p]) {
    
            if (dis1[p] + now.w1 < dis1[now.to]){
    
                dis1[now.to] = dis1[p] + now.w1;
                dis2[now.to] = dis2[p] + now.w2;
                pre[now.to] = p;
                q.push(node{
    now.to, dis1[now.to], dis2[now.to]});
            }
            else if(dis1[p] + now.w1 == dis1[now.to] && dis2[p] + now.w2 > dis2[now.to]){
    
                dis2[now.to] = dis2[p] + now.w2;
                pre[now.to] = p;
                q.push(node{
    now.to, dis1[now.to], dis2[now.to]});
            }
        }
    }
    for (int i : mubiao) {
    
        cout<<from;
        print(i);
        cout<<"\n";
        cout<<dis1[i]<<" "<<dis2[i]<<"\n";
    }
    return 0;
}

4.疫情防控【并查集】

思路

看两个机场之间是否能互通，那就看是否在一个集合当中就行，所以要用到并查集，而我们每天要封闭一个机场（删除一个点），但是又不好实现，那么我们预处理，把要删除的点全部拿出来，建立并查集之后，从最后一天往前遍历，每次处理完这天之后，再把这天封闭的机场（点）加入其中，更新并查集。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
const int N = 5e4 + 5;
int n,m,d;
vector<int> M[N];       //存图
int father[N];          //存根节点
struct day{
    
    int p,l;
    vector<pii> v;
} day[N];               //要处理的每一天的信息
bool note[N];           //标记是否要删除
stack<int> sta;         //用于输出
int f(int x){
               //找根节点
    if (father[x] == x)
        return x;
    return father[x] = f(father[x]);
}
void add(int a,int b){
      //合并集合
    int x = f(a), y = f(b);
    father[x] = y;
}
signed main(){
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>d;
    int from, to;
    for (int i = 0; i < m; ++i) //存图
        cin>>from>>to,M[from].push_back(to),M[to].push_back(from);
    for (int i = 1; i <= n; ++i)
        father[i] = i;          //初始化根节点
    for (int i = 1; i <= d; ++i) {
      //预处理找出所有要删除的点
        cin>>day[i].p>>day[i].l;
        note[day[i].p] = true;              //要删除
        for (int j = 0; j < day[i].l; ++j) {
    
            int a, b;cin>>a>>b;
            day[i].v.push_back(pii(a,b));
        }
    }

    for (int i = 1; i <= n; ++i) {
      //先将不会被删除的点之间建立并查集
        if (note[i])
            continue;
        for (int j : M[i]) {
    
            if (!note[j])
                add(i,j);
        }
    }

    for (int i = d; i >= 1; --i) {
      //从最后一天开始处理
        int sum = 0;
        for (pii t : day[i].v) {
    
            if (f(t.first) != f(t.second))
                sum += 1;
        }
        sta.push(sum);              //当天被影响的航班
        for (int j : M[day[i].p]) {
     //把这天要封闭的机场加入并查集
            if (!note[j])
                add(day[i].p,j);
        }
        note[day[i].p] = false;     //这天之前该机场未被封闭
    }
    while (!sta.empty()){
    
        cout<<sta.top()<<"\n";sta.pop();
    }
    return 0;
}

          //当天被影响的航班
    for (int j : M[day[i].p]) { //把这天要封闭的机场加入并查集
        if (!note[j])
            add(day[i].p,j);
    }
    note[day[i].p] = false;     //这天之前该机场未被封闭
}
while (!sta.empty()){
    cout<<sta.top()<<"\n";sta.pop();
}
return 0;

}