2021 robocom world robot developer competition - undergraduate group (Preliminary) problem solution

7-1 Know everything. (20 branch )

violence

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define x first
#define y second
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

int a[N];
bool st[N];

inline void solve(){
    
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
    
        for(int j=i+1;j<=n;j++){
    
            for(int k=j+1;k<=n;k++){
    
                for(int p=k+1;p<=n;p++){
    
                    st[a[i]+a[j]+a[k]+a[p]]=1;
                }
            }
        }
    }
    while(k--){
    
        bool tag=0;
        int q;
        cin>>q;
        while(q--){
    
            int x;
            cin>>x;
            if(!st[x*4]) tag=1;
        }
        if(tag) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

7-2 Finnish wood chess (25 branch )

Save them together according to the slope , Sort by coordinates , If more than one 1 Together, the maximum score plus the number , Otherwise, step by step

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

struct node{
    
    int x,y, p;
}dp[N];
vector<int>idx[N];
map<double,int>mp;

bool cmp(int x,int y){
    
    if(dp[x].x<dp[y].x) return 1;
    else if(dp[x].x==dp[y].x&&dp[x].y<dp[y].y) return 1;
    return 0;
}

inline void solve(){
    
    int n;
    cin>>n;
    int x,y,p;
    int tot=0;
    int id;
    for(int i=1;i<=n;i++){
    
        cin>>x>>y>>p;
        dp[i]={
    x,y,p};
        double k=x*1.0/y;
        if((x<0&&y<0)||(x>0&&y<0)) k*=1000.1;
        if(mp.count(k)) id=mp[k];
        else id=++tot,mp[k]=tot;
        idx[id].eb(i);
        //cout<<k<<" "<<tot<<endl;
    } 
    int sum=0;
    int cnt=0;
    for(int i=1;i<=tot;i++){
    
        sort(idx[i].begin(),idx[i].end(),cmp);
        for(int j=0;j<idx[i].size();j++){
    
            int num=0;
            while(dp[idx[i][j]].p==1&&j<idx[i].size()){
    
                num++;
                j++;
            }
            if(num>1) sum+=num,j--;
            else if(num==1) sum++,j--;
            else sum+=dp[idx[i][j]].p;
            cnt++;
        }
    }
    cout<<sum<<" "<<cnt<<endl;
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

7-3 Have to upgrade (25 branch )

Floyd The algorithm finds the starting point , Reuse Dijkstra Find the shortest path

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define x first
#define y second
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

int n,m;
int g[M][M],gg[M][M];
int p[M][M],pp[M][M];
int ask[N];
int dist[N];
int cost[N];
int pre[N];
bool st[N];

void Floyd(){
    
    for(int k=1;k<=n;k++){
    
        for(int i=1;i<=n;i++){
    
            for(int j=1;j<=n;j++){
    
                if(g[i][j]>g[i][k]+g[k][j]){
    
                    g[i][j]=g[i][k]+g[k][j];
                    p[i][j]=p[i][k]+p[k][j];
                }else if(g[i][j]==g[i][k]+g[k][j]){
    
                    if(p[i][j]<p[i][k]+p[k][j]){
    
                        p[i][j]=p[i][k]+p[k][j];
                    }
                }
            }
        }
    }
}


void show_road(int s,int e){
    
    vector<int>vp;
    vp.eb(e);
    while(pre[e]!=s) vp.eb(pre[e]),e=pre[e];
    cout<<s;
    for(int i=vp.size()-1;i>=0;i--) cout<<"->"<<vp[i];
    cout<<endl;
}

void Dijkstra(int s){
    
    mem(dist,0x3f);
    mem(cost,0);
    dist[s]=0;
    for(int i=1;i<n;i++){
    
        int t=-1;
        for(int j=1;j<=n;j++){
    
            if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
        }
        for(int j=1;j<=n;j++){
    
            if(dist[j]>dist[t]+gg[t][j]){
    
                dist[j]=dist[t]+gg[t][j];
                cost[j]=cost[t]+pp[t][j];
                pre[j]=t;
            }else if(dist[j]==dist[t]+gg[t][j]){
    
                if(cost[j]<cost[t]+pp[t][j]){
    
                    cost[j]=cost[t]+pp[t][j];
                    pre[j]=t;
                }
            }
        }
        st[t]=1;
    }
}

inline void solve(){
    
    cin>>n>>m;
    int u,v,W,P;
    mem(g,inf);
    mem(p,0);
    mem(gg,inf);
    mem(pp,0);
    while(m--){
    
        cin>>u>>v>>W>>P;
        g[u][v]=g[v][u]=W;
        gg[u][v]=gg[v][u]=W;
        p[u][v]=p[v][u]=P;
        pp[u][v]=pp[v][u]=P;
    }
    int x;
    cin>>x;
    for(int i=1;i<=x;i++) cin>>ask[i];
    Floyd();
    int pos=inf;
    int minn=inf;
    for(int i=1;i<=n;i++){
    
        int sum=0;
        for(int j=1;j<=n;j++){
    
            //if(i!=j) 
            sum=max(sum,g[i][j]);
        }
        if(sum<minn){
    
            minn=sum;
            pos=i;
        }else if(sum==minn) pos=min(pos,i);
    }
    cout<<pos<<endl;
    Dijkstra(pos);
    for(int i=1;i<=x;i++){
    
        if(ask[i]==pos) cout<<pos<<endl<<"0 0"<<endl;
        else{
    
            show_road(pos,ask[i]);
            cout<<dist[ask[i]]<<" "<<cost[ask[i]]<<endl;
        }
    }
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

7-4 Epidemic prevention and control (30 branch )

Flashback and search set

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define x first
#define y second
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb push_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 3e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

PII edge[N];
int n,m,d;
struct  node{
    
    vector<PII>add;
    vector<PII>ask;
}dp[N];

int w[N];
int vis[N];
int ans[N];

int Find(int x){
    
    if(x!=vis[x]) vis[x]=Find(vis[x]);
    return vis[x];
}

void Merge(int x,int y){
    
    int xx=Find(x);
    int yy=Find(y);
    if(xx!=yy) vis[xx]=yy;
}

inline void solve(){
    
    cin>>n>>m>>d;
    int u,v;
    mem(w,0x3f);
    for(int i=1;i<=m;i++){
    
        cin>>u>>v;
        edge[i]={
    u,v};
    }
    for(int i=0;i<=n;i++) vis[i]=i;
    for(int i=1;i<=d;i++){
    
        int p,k;
        cin>>p>>k;
        w[p]=i;
        while(k--){
    
            cin>>u>>v;
            dp[i].ask.eb(PII{
    u,v});
        }
    }
    for(int i=1;i<=m;i++){
    
        int minn=min(w[edge[i].x],w[edge[i].y]);
        if(minn==inf) Merge(edge[i].x,edge[i].y);
        else dp[minn].add.eb(edge[i]);
    }
    for(int i=d;i>=1;i--){
    
        int tot=0;
        for(auto it:dp[i].ask){
    
            if(Find(it.x)!=Find(it.y)) tot++;
        }
        ans[i]=tot;
        for(auto it:dp[i].add) Merge(it.x,it.y);
    }
    for(int i=1;i<=d;i++) cout<<ans[i]<<endl;
}

int main() {
    
    ios::sync_with_stdio(0);
    solve();
    return 0;
}