比賽介紹

• 比賽信息
  比賽官網(wǎng)：https://www.robocom.com.cn/
  報(bào)名流程：https://www.robocom.com.cn/content.html?cid=386
  工信部發(fā)文：https://www.robocom.com.cn/content.html?cid=367
  中國教育學(xué)會清單：https://m.cahe.edu.cn/site/content/14825.html
  編程賽道通知：https://www.robocom.com.cn/content.html?cid=369
  

• 賽制說明：
  CAIA數(shù)字創(chuàng)意賽道FAQ
  CAIP編程設(shè)計(jì)賽道FAQ
  CAIR工程競技賽道FAQ
  編程技能普及賽是什么賽制？
  嚴(yán)格意義上來說不算ioi賽制，類似天梯賽。因?yàn)槭莻€人賽所以不像天梯賽還有團(tuán)隊(duì)分。
  題量是多少道題？難度如何？本科組去年4道題，本科組賽題難度類似PAT甲級中文。
  可分為省賽和國賽的獎項(xiàng)，省賽一二等獎晉級國賽；其中省賽獲獎比例：20%，30%，40%，10%分別對應(yīng)一、二、三和優(yōu)秀獎；國賽獲獎比例：10%，30%，60%分別對應(yīng)一、二和三等獎。
  

• 補(bǔ)題信息：
  PTA教育超市：https://pintia.cn/market
  

7-1 懂的都懂(20分)

眾所周知，在互聯(lián)網(wǎng)上有很多話是不好直接說出來的，不過一些模糊的圖片仍然能讓網(wǎng)友看懂你在說什么。然而對這種言論依然一定要出重拳，所以請你實(shí)現(xiàn)一個簡單的匹配算法。

現(xiàn)在我們采集了原圖的一些特征數(shù)據(jù)，由 N 個小于 255 的非負(fù)整數(shù)組成，假設(shè)對于給定的若干張由 M
i
?
個同樣小于 255 的非負(fù)整數(shù)組成的新圖的特征數(shù)據(jù)，每個數(shù)據(jù)都可以由原圖中任意四個不同數(shù)據(jù)的平均值計(jì)算而來，則稱新圖為原圖的相似圖片。對于給出的數(shù)據(jù)，請你判斷是不是相似圖片。

注意，不同數(shù)據(jù)指的并非是數(shù)據(jù)的值不同，而是不能取同一個數(shù)據(jù)多次。對于兩個相同值的數(shù)據(jù)，如果給出兩次，則可以取兩次。

輸入格式:
輸入第一行是兩個整數(shù) N,K (1 ≤ N ≤ 50, 1 ≤ K ≤ 200)，表示采集的原圖的特征數(shù)據(jù)個數(shù)和新圖的張數(shù)。

接下來一行為 N 個小于 255 的非負(fù)整數(shù)，表示原圖的特征數(shù)據(jù)。

最后的 K 行，每行第一個數(shù)是 M
i
?
(1 ≤ M
i
?
≤ 200)，表示新圖的特征數(shù)據(jù)個數(shù)。然后是 M
i
?
個小于 255 的非負(fù)整數(shù)，表示新圖的特征數(shù)據(jù)。

輸出格式:
對于每一張新圖，如果為相似圖片，則在一行中輸出 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

• 題意：給出一個初始數(shù)組，判斷后面的n個數(shù)組是否每個數(shù)都能由第一個數(shù)組中的某四個數(shù)取平均值得到。
• 思路：直接dfs 4層所有的方案,（4⁵⁰會T，但是50⁴不會T），開個set維護(hù)所有可行數(shù)字然后判斷就行。
  注意坑點(diǎn)，如果不能整除就不要去除，不然只有10分。同時第一個數(shù)組的數(shù)字也不在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;
}

7-2 芬蘭木棋（25分）

芬蘭木棋（M?lkky，又稱芬蘭木柱）是源自芬蘭的一項(xiàng)運(yùn)動。哲哲將這個運(yùn)動改造成了賽博朋克單人版，現(xiàn)在場上一開始有 N 根立起的小木棋（上面分別標(biāo)有一個非負(fù)整數(shù)），哲哲投擲一根大木棋去擊倒這些小木棋以獲得分?jǐn)?shù)。分?jǐn)?shù)規(guī)則如下：

如果僅擊倒 1 根木棋，則得木棋上的分?jǐn)?shù)。
如果擊倒 2 根或以上的木棋，則只得擊倒根數(shù)的分?jǐn)?shù)。（例如擊倒 5 根，則得 5 分。）
哲哲固定站在 (0,0) 點(diǎn)上，四周放著若干個小木棋 (X
i
?
,Y
i
?
)，坐標(biāo)均為整數(shù)。每次哲哲可以朝一個方向扔出大木棋，大木棋會打倒這個方向上離哲哲最近的 k 個小木棋。哲哲游戲水平很高超，所以這個 k 可以自由控制。

請問哲哲最多能拿多少分，在獲得最多分?jǐn)?shù)的情況下最少需要扔出多少次大木棋？

規(guī)則與真實(shí)規(guī)則有較大出入，真實(shí)游玩時請以國際莫爾基組織的規(guī)則為準(zhǔn)

輸入格式:
輸入第一行是一個正整數(shù) N (1 ≤ N ≤ 10
5
)，表示場上一開始有 N 個木棋。

接下來 N 行，每行 3 個整數(shù) X
i
?
,Y
i
?
,P
i
?
，分別表示木棋放置在 (X
i
?
,Y
i
?
)，木棋上的分?jǐn)?shù)是 P
i
?
。坐標(biāo)在 32 位整數(shù)范圍內(nèi)，分?jǐn)?shù)為小于等于 1000 的正整數(shù)。

保證 (0,0) 點(diǎn)沒有木棋，也沒有木棋重疊放置。

輸出格式:
輸出一行兩個數(shù)，表示最多分?jǐn)?shù)以及獲得最多分?jǐn)?shù)最少需要投擲大木棋多少次。

輸入樣例:
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個坐標(biāo)上都有分?jǐn)?shù)，每次可以拿到一個坐標(biāo)上的所有分?jǐn)?shù)，或者x個坐標(biāo)都作為分?jǐn)?shù)1同時被拿掉，拿的時候必須遵守順序從近到遠(yuǎn)拿，不能跳著拿，且每次只能拿同一個方向的。
  求最大能拿多少分?jǐn)?shù)，此時的最少次數(shù)。
• 不難想到：
  可以無限次拿，所以最大分?jǐn)?shù)肯定是全部加起來。
  然后因?yàn)閤個一起拿，那么對于>1的就損失了分?jǐn)?shù)，所以>1的肯定要一次，=1的盡量一起拿。
• 沒說清楚的：
  每次只能拿同方向的，所以開個map對斜率分類，而且要double。。。
  因?yàn)槭钦驹谠c(diǎn)，所以更近的同方向，即拿的順序指的是，-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;
}

7-3 打怪升級（25分）

很多游戲都有打怪升級的環(huán)節(jié)，玩家需要打敗一系列怪獸去贏取成就和徽章。這里我們考慮一種簡單的打怪升級游戲，游戲規(guī)則是，給定有 N 個堡壘的地圖，堡壘之間有道路相連，每條道路上有一只怪獸把守。怪獸本身有能量，手里的武器有價(jià)值。打敗怪獸需要的能量等于怪獸本身的能量，而怪獸一旦被打敗，武器就歸玩家所有 —— 當(dāng)然繳獲的武器價(jià)值越高，玩家就越開心。

你的任務(wù)有兩件：

幫助玩家確定一個最合算的空降位置，即空降到地圖中的某個堡壘，使得玩家從這個空降點(diǎn)出發(fā)，到攻下最難攻克（即耗費(fèi)能量最多）的那個堡壘所需要的能量最?。?br> 從這個空降點(diǎn)出發(fā)，幫助玩家找到攻克任意一個其想要攻克的堡壘的最省能量的路徑。如果這種路徑不唯一，則選擇沿途繳獲武器總價(jià)值最高的解，題目保證這種解是唯一的。
輸入格式:
輸入第一行給出兩個正整數(shù) N (≤1000) 和 M，其中 N 是堡壘總數(shù)，M 是怪獸總數(shù)。為簡單起見，我們將堡壘從 1 到 N 編號。隨后 M 行，第 i 行給出了第 i 只怪獸的信息，格式如下：

B1 B2 怪獸能量 武器價(jià)值
其中 B1 和 B2 是怪獸把守的道路兩端的堡壘編號。題目保證每對堡壘之間只有一只怪獸把守，并且 怪獸能量 和 武器價(jià)值 都是不超過 100 的正整數(shù)。

再后面是一個正整數(shù) K（≤N）和玩家想要攻克的 K 個目標(biāo)堡壘的編號。

輸出格式:
首先在一行中輸出玩家空降的堡壘編號 B0。如果有多種可能，則輸出編號最小的那個。

隨后依次為玩家想要攻克的每個堡壘 B 推薦最省能量的攻克路徑，并列出需要耗費(fèi)的能量值和沿途繳獲武器的總價(jià)值。注意如果最省力的路徑不唯一，則選擇沿途繳獲武器總價(jià)值最高的解。格式為：

B0->途經(jīng)堡壘1->…->B
總耗費(fèi)能量 武器總價(jià)值
輸入樣例:
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個點(diǎn)m條邊的無向圖，每條邊有一個代價(jià)和一個價(jià)值，對于每個點(diǎn)求最大代價(jià)的點(diǎn)，記最小的為起點(diǎn)。然后從起點(diǎn)出發(fā)到其他所有點(diǎn)的最小代價(jià)路徑，代價(jià)相同時找最大價(jià)值，打印路徑。
• 思路：
  floyed跑多源最短路，令最長路最短，即為起點(diǎn)RT。
  Dijkstra跑單源最短路（w1最小，w2最大），打印路徑即可。
  e數(shù)組沒初始化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;
}

7-4 疫情防控（30分）

疫情尚未結(jié)束，嚴(yán)防疫情反復(fù)。為了做好疫情防控工作，國內(nèi)設(shè)置了地區(qū)風(fēng)險(xiǎn)等級，對于中高風(fēng)險(xiǎn)地區(qū)的人員采取限制移動、居家隔離等手段。

為了研究疫情防控對于跨地區(qū)交通運(yùn)輸?shù)挠绊?，假設(shè)現(xiàn)在有 N 個機(jī)場，M 條航線，每天都會新增一個防控地區(qū)，一個防控地區(qū)會導(dǎo)致一個機(jī)場無法正常運(yùn)作，航線也自然無法正常運(yùn)行，每天會有 Q
i
?
對旅客從 X
i
?
機(jī)場前往 Y
i
?
機(jī)場，請計(jì)算有多少對旅客會受到影響無法完成行程。

旅客只要能直達(dá)或通過若干次中轉(zhuǎn)，且乘坐的所有航線的出發(fā)和到達(dá)機(jī)場都正常運(yùn)作，即視作可完成行程。

輸入格式:
輸入第一行是三個整數(shù) N,M,D (1≤N≤5×10
4
, 1≤M≤2×10
5
, 1≤D≤10
3
), 表示機(jī)場數(shù)、航線數(shù)以及新增防控地區(qū)的天數(shù)。

接下來首先有 M 行，每行給出空格分隔的兩個數(shù)字 A 和 B，表示編號為 A 和 B 的機(jī)場之間有一條航線。航線是雙向的，機(jī)場編號從 1 到 N。

然后是 D 塊輸入，每塊輸入內(nèi)第一行為空格分隔的兩個整數(shù) C 和 Q （1≤Q≤10
3
)，表示新增機(jī)場編號為 C 所在的城市為防控地區(qū)，今天有 Q 段行程。數(shù)據(jù)保證新增的城市之前一定不是防控地區(qū)。

接下來的 Q 行，每行是空格分隔的兩個數(shù)字 X 和 Y，表示編號為 X 和 Y 的機(jī)場的一段行程。行程有可能包括之前就已經(jīng)成為防控地區(qū)的城市。

輸出格式:
對于每天的詢問，請?jiān)谝恍兄休敵鲈谛略隽艘粋€防控地區(qū)后當(dāng)天的行程有多少不能成行。

輸入樣例:
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文章來源地址http://www.zghlxwxcb.cn/news/detail-565597.html

• 題意：給出n個點(diǎn)，m條邊的無向圖，接下來d天每天刪掉一個點(diǎn)c（累加），然后q次詢問每次問刪掉c后某兩點(diǎn)u,v能否聯(lián)通。
• 思路：考慮暴力O(每天d*重新建圖m*詢問q*是否聯(lián)通n)復(fù)雜度直接上天。
  這里的難點(diǎn)在于每次刪掉一個點(diǎn)后要重新建圖需要大量的時間，因?yàn)槲覀兛梢?strong>離線所有的詢問反向建圖，這樣較難的刪點(diǎn)就變成了簡單的往圖上加點(diǎn)，任意兩點(diǎn)的連通性也由需要O(n)暴力變成了可以使用并查集logn維護(hù)的。
• 具體來說：記錄下第i天刪了誰，有哪些詢問。從d天開始往前，每天加一個點(diǎn)，然后并查集直接判斷一下是否聯(lián)通即可。注意加點(diǎn)的時候需要考慮當(dāng)前點(diǎn)連向的點(diǎn)必須是沒有被刪的，不然會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;  //現(xiàn)在它復(fù)活了，加回去
        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;
}

到了這里，關(guān)于2021 RoboCom 世界機(jī)器人開發(fā)者大賽-本科組（初賽）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！