2021 robocom world robot developer competition - preliminary competition of undergraduate group

2021 RoboCom World robot developer competition - Undergraduate group preliminary

1. Know everything. 【 violence 】

Ideas

Take four numbers , Then directly n Of 4 The power traverses every possibility , Then put it in a set Just in the middle , For each new picture, judge whether each eigenvalue can be in this set Find , If so, output Yes, Otherwise output No.

AC Code

#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)       // Enter the original image 
        cin>>x[i];
    for (int i = 1; i <= n; ++i)  // Traverse each of the four selected numbers 
        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 Processing of a new picture 
        bool f = true;int a,b;
        cin>>a;
        for (int i = 0; i < a; ++i) {
    
            cin>>b;
            if (s.count(b * 4) == 0)    // As long as one value is not s in , It outputs no
                f = false;
        }
        if (f)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}

2. Finnish wood chess 【 thinking 】

Ideas

Sort according to the distance between the stake and the origin , Then deal with it from near to far , For wooden piles in the same direction , If there is a continuous height of 1 Of , Then knock down many wooden stakes at one time , This is under the condition of ensuring the same score , The number of hits is the least ; Otherwise, you can knock down a wooden stake every time .

AC Code

#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];     // Indicates the abscissa of wooden chess 、 Ordinate 、 fraction 
map<pii, int> mp;           //pii Indicates a certain direction ,int Indicates how many consecutive wooden chess scores in this direction are 1
int ans_1,ans_2;            // The most scores 、 The least number of times 
bool cmp(pair<pair<int,int> ,int> a,pair<pair<int,int> ,int> b){
        // Sort according to the distance from the origin 
    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) {
           // Enter the coordinates and scores of the wooden chess 
        cin>>edge[i].first.first>>edge[i].first.second>>edge[i].second;
    }
    sort(edge,edge + n,cmp);        // Sort 
    for (int i = 0; i < n; ++i) {
           // For every wooden chess , Divide the abscissa and ordinate by the greatest common divisor , Used to distinguish each direction 
        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){
       // If 1 Just record it 
            mp[edge[i].first] += 1;
        }
        else{
                           // Otherwise, put the front in this direction 1 All at once , Then we can beat the current wooden chess 
            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) {
          // If there is continuity in one direction 1
        if (it->second > 0){
    
            ans_1 += it->second;
            ans_2 += 1;
        }
    }
    cout<<ans_1<<" "<<ans_2;
    return 0;
}

3. Have to upgrade 【Floyed+Dijkstra】

Ideas

First, use a multi-source shortest path to run out , Then select the starting point （ Find the minimum value of the longest route ）. Then after having a starting point , Run the single source shortest circuit again and record the path .

AC Code

#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;  // Number of points 、 The shortest distance from the starting point to this point 、 The greatest value 
};
struct edge{
    
    int to, w1, w2; // The end of the side 、 distance 、 value 
};
int n,m,k;
vector<int> mubiao; // Target fortress 
int pre[1005];      // Storage precursor node 
int dis[1005][1005], dis1[1005], dis2[1005];    // Respectively used to find out the sending point 、 The distance from the starting point to this point 、 Value from starting point to this point 
vector<edge> M[1005];       // Save edge 
bool vis[1005];         // Judge whether a node has been visited , be used for 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();     // initialization 
    floyed();   //floyed Running multiple shortest paths 
    int from = 0, mn = 0x3f3f3f3f;  // The starting point to choose 
    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;        // Store the precursor node of each point 
    
    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. Epidemic prevention and control 【 Union checking set 】

Ideas

See if the two airports can connect , It depends on whether it is in a set , So we need to use and look up the set , And we have to close an airport every day （ Delete a point ）, But it's not easy to realize , Then we preprocess , Take out all the points to be deleted , After establishing and searching the set , Traverse from the last day , After each day , Then close the airport on this day （ spot ） Join in , Update and search set .

AC Code

#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];       // Save map 
int father[N];          // Stub node 
struct day{
    
    int p,l;
    vector<pii> v;
} day[N];               // Information to be processed every day 
bool note[N];           // Mark whether to delete 
stack<int> sta;         // For output 
int f(int x){
               // Find the root node 
    if (father[x] == x)
        return x;
    return father[x] = f(father[x]);
}
void add(int a,int b){
      // Merge sets 
    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) // Save map 
        cin>>from>>to,M[from].push_back(to),M[to].push_back(from);
    for (int i = 1; i <= n; ++i)
        father[i] = i;          // Initialize root 
    for (int i = 1; i <= d; ++i) {
      // Preprocessing finds all points to delete 
        cin>>day[i].p>>day[i].l;
        note[day[i].p] = true;              // To delete 
        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) {
      // First, set up and search between points that will not be deleted 
        if (note[i])
            continue;
        for (int j : M[i]) {
    
            if (!note[j])
                add(i,j);
        }
    }

    for (int i = d; i >= 1; --i) {
      // Start processing from the last day 
        int sum = 0;
        for (pii t : day[i].v) {
    
            if (f(t.first) != f(t.second))
                sum += 1;
        }
        sta.push(sum);              // Flights affected that day 
        for (int j : M[day[i].p]) {
     // Add the airport to be closed this day and check the collection 
            if (!note[j])
                add(day[i].p,j);
        }
        note[day[i].p] = false;     // The airport was not closed before this day 
    }
    while (!sta.empty()){
    
        cout<<sta.top()<<"\n";sta.pop();
    }
    return 0;
}

          // Flights affected that day 
    for (int j : M[day[i].p]) { // Add the airport to be closed this day and check the collection 
        if (!note[j])
            add(day[i].p,j);
    }
    note[day[i].p] = false;     // The airport was not closed before this day 
}
while (!sta.empty()){
    cout<<sta.top()<<"\n";sta.pop();
}
return 0;

}