SCNUOJ 2020 軟院天梯賽選拔賽 + 藍橋杯熱身賽 題解

寫在前面

本次比賽面向軟件學院2017、2018铐懊、2019級學生邀桑，賽制為IOI賽制，時長3小時科乎。

最終共有311名同學提交代碼概漱，共有302名同學獲得有效分數(shù)。

最終前18名的同學（除去打星）入圍2020軟件學院團體程序設計天梯賽名單喜喂，其中最高分為183分瓤摧，最低分為105分。

祝賀他們玉吁！

題目限制

ps:一般來說照弥，64MB內(nèi)存足以。

L1-1 建議改成：空 格 體（5）

Problem Description

LXY 在某大型知名同性交友網(wǎng)站上傳了一個視頻进副，但并沒有想到有意思的標題这揣。作為標題黨的 LXY 想讓博學多識的你給他想一個好標題悔常。

結(jié)合 LXY 的視頻內(nèi)容，你自然想到了一個非常好的標題给赞。為了將自己的標題告訴 LXY机打，你需要在評論區(qū)用建議空格體加入標題競標。

建議空格體示例

Input

輸入共一行片迅，一個由大小寫字母及數(shù)字組成的字符串（不超過 個字符）残邀，表示你想出的標題。

Output

輸出一行柑蛇，開頭是"Proposed change to: "芥挣，后面是標題并將標題內(nèi)的每個字符用空格隔開。

Simple Input

114514

Simple Output

Proposed change to: 1 1 4 5 1 4

Source

CGY

思路

讀取字符串耻台，按要求每一個字符前輸出一個空格即可空免。

這道題部分人用JAVA和C語言多次調(diào)用strlen函數(shù)會導致代碼TLE，因為C語言里strlen函數(shù)的時間復雜度為O(n)盆耽，Java的String類比較慢蹋砚，推薦使用StringBuffer來處理。

代碼

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    cout<<"Proposed change to:";
    for(int i = 0;i<str.size();++i) cout<<" "<<str[i];
    return 0;
}

L1-2 多邊形（5）

Problem Description

Veggie最近疲于教小侄子寫紅黑樹摄杂，連多邊形的內(nèi)角和都忘記怎么求了坝咐，想請作為數(shù)學小天才的你幫忙編程解決這個問題。

Input

輸入在一行中給出一個整數(shù)匙姜，表示多邊形的邊數(shù)畅厢。

Output

在一行中對應輸出n邊形內(nèi)角和的值x冯痢，格式為”Answer: x degree”（不含雙引號）氮昧。

Simple Input

4

Simple Output

Answer: 360 degree

Source

LWH

思路

多邊形內(nèi)角和 = (邊數(shù) - 2) * 180

代碼

#include <stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    printf("Answer: %d degree", (n - 2) * 180);
    return 0;
}

L1-3 米斯達與數(shù)字4（10）

Problem Description

Guīdo Misuta是《JOJO的奇妙冒險：黃金之風》里面的人物，他對于數(shù)字4很是在意浦楣，他認為4是十分不吉利的數(shù)字⌒浞剩現(xiàn)在有一串數(shù)字，請問這串數(shù)字迫害米斯達的次數(shù)是多少振劳？

迫害次數(shù)=數(shù)字4出現(xiàn)的次數(shù)+數(shù)字長度內(nèi)4出現(xiàn)的次數(shù)椎组。

//性感手槍警告

Input

輸入一串數(shù)字，長度不超過200位

Output

數(shù)字4出現(xiàn)的次數(shù)和數(shù)字長度中4的次數(shù)的總和

Simple Input

1234

Simple Output

2

Hint

數(shù)字中出現(xiàn)4的次數(shù)為1历恐，同時數(shù)字長度為4寸癌，因此總和為1+1=2

Source

LXY

思路

這道題分為兩個部分來求解，一個是求這串數(shù)字中4的個數(shù)弱贼，另一個是這串數(shù)字位數(shù)（長度）中4的個數(shù)蒸苇。
在這里，我們可以采用string字符串來讀入吮旅，借助string.size()函數(shù)來快速得到這串數(shù)字的位數(shù)溪烤，然后將位數(shù)不斷模10整除10來獲得每一位的數(shù)字并統(tǒng)計其中4的個數(shù)。最后遍歷這個字符串，判斷字符為'4'的個數(shù)檬嘀，兩部分累加即為答案槽驶。

代碼

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int n = str.size();
    int cnt = 0;
    while(n){
        if(n%10 == 4) cnt++;
        n/=10;
    }
    for(int i = 0;i<str.size();++i){
        if(str[i]=='4') cnt++;
    }
    cout<<cnt;
    return 0;
}

L1-4 打印（10）

Problem Description

真的是道簡單打印題哈——給定一個整數(shù)數(shù)組鸳兽，請打印其中位數(shù)為偶數(shù)且數(shù)值也為偶數(shù)的數(shù)字掂铐。

Input

第一行為一個整數(shù)，代表數(shù)組有N個整數(shù)贸铜。

接下來有N行堡纬，每行有一個整數(shù)

Output

若輸入的的位數(shù)為偶數(shù)且數(shù)值也為偶數(shù)，則打印該行蒿秦。

Simple Input1

3
12
2
13

Simple Output1

12

Simple Input2

2
-1
-12

Simple Output2

-12

Source

SLF

思路

方法一：用字符串處理烤镐，判斷字符串位數(shù)是否為偶數(shù)（負號不算入內(nèi)），再判斷最后一個字符是否為偶數(shù)即可棍鳖。

方法二：直接讀入整數(shù)處理炮叶。

代碼（方法一）

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    int n;
    cin>>n;
    while(n--){
        cin>>str;
        int num_len = str.size();
        if(str[0]=='-'){
            num_len--;
        }
        if(str[str.size()-1]%2==0 && num_len%2==0){
            cout<<str<<endl;
        }
    }
    return 0;
}

L1-5 尋找連座（15）

Problem Description

image.png

軟件學院的LXY和CGY要去一起坐火車外出比賽《纱Γ火車上有許多節(jié)車廂镜悉，每節(jié)車廂的每一排都有4個座位，且這4個座位被過道分成了兩半医瘫。不幸的是侣肄，當LXY和CGY到了車上時，一些位子已經(jīng)有人了醇份。

但LXY和CGY是好基友稼锅，于是他們想要找一對連在一起的座位，以便于更好地打游戲(手動劃掉)學習僚纷。一對連在一起的座位指得是矩距，這兩個座位在同一排且不被過道分割開。已知火車上每節(jié)車廂上的座位情況怖竭，請問能否找得到這樣的一對連座锥债？

Input

第一行為一個整數(shù)，代表火車總長度痊臭。

緊接著輸入行哮肚，每行由五個字符組成，代表一排座位或者車廂分割線广匙。

若是一排座位允趟，第1、2艇潭、4拼窥、5個字符分別代表一排中的4個座位情況戏蔑，字符'O'表示空座位，字符'X'表示座位上已經(jīng)有人鲁纠，即被占用总棵。第3個字符為'|'，代表過道。

若是車廂分割線，則五個字符均為'-'砰苍。

數(shù)據(jù)保證每節(jié)車廂至少有一排座位课竣。

Output

如果能夠找到這樣一組連座室埋，請先輸出一行字符串"Yes"（不輸出引號），接下來一行，輸出一個整數(shù)k，代表這組連座在第k車廂（車廂編號由1開始专酗，從前往后編號遞增）。

接下來輸出火車的座位情況盗扇，將LXY和CGY坐的連座用"+"來表示祷肯。

若不能找到這樣的連座，則輸出一行字符串"No"（不輸出引號）疗隶。

有多組座位符合要求時佑笋，將LXY和CGY安排在靠前的車廂，靠前的排斑鼻，如果同一排還有兩組可行解蒋纬，選擇將LXY和CGY排在左邊。例如：

OO|OO                ++|OO

-----        ->      -----

OO|XX                OO|XX

Simple Input1

6
OO|OX
XO|XX
OX|OO
XX|OX
-----
OO|XX

Simple Output1

Yes
1
++|OX
XO|XX
OX|OO
XX|OX
-----
OO|XX

Simple Input2

6
XO|OX
XO|XX
OX|XO
XX|OX
-----
OX|XX

Simple Output2

No

Source

SLF

思路

字符串處理題坚弱。

遍歷字符串數(shù)組蜀备，判斷出LXY和CGY連座的位置，記錄下來即可史汗。

需要注意得是琼掠，車廂分割線代表著前一節(jié)車廂和后一節(jié)車廂的分割拒垃，可以聯(lián)想火車/高鐵的平面示意圖停撞。有些同學沒有注意到這一點，導致Wrong Answer悼瓮。

代碼

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

string str[110];

int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;++i){
        cin>>str[i];
    }
    int cnt = 1;
    int ansi,ansj;
    int flag = false;
    for(int i = 0;i<n;++i){
        for(int j = 0;j<4;++j){
            if(str[i][j]=='-'){
                ++cnt;//統(tǒng)計當前車廂為第幾車廂
                break;
            }
            if(str[i][j]=='O' && str[i][j+1]=='O'){
                flag = true;
                ansi = i,ansj = j;
                break;
            }
        }
        if(flag) break;
    }
    if(flag){
        cout<<"Yes"<<endl;
        cout<<cnt<<endl;
        for(int i = 0;i<n;++i){
            for(int j = 0;j<5;++j){
                if(i==ansi&&j==ansj){
                    cout<<"++";
                    ++j;
                    continue;
                }
                cout<<str[i][j];
            }
            cout<<endl;
        }
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

L1-6 Heroes never die（15）

Problem Description

image.png

OverWatch里的三個英雄有著上圖的克制關(guān)系戈毒。

現(xiàn)在，我們需要寫一個程序來自動選擇英雄横堡，以對抗對方選擇的英雄埋市。

選擇規(guī)則如下：

1、當回合數(shù)是K的倍數(shù)時命贴，選擇一個相同的英雄道宅。

2食听、當回合數(shù)是N的倍數(shù)時，選擇一個”天使”英雄污茵，并在接下來一行輸出” Heroes never die”樱报。

3、當回合數(shù)是K和N的倍數(shù)時泞当，選擇一個相同的英雄迹蛤。

4、其他回合襟士，選擇一個克制對方英雄的英雄盗飒。

Ps：回合數(shù)從1開始

Input

首先第一行給出兩個整數(shù)K、N（1≤K,N≤10）陋桂，由空格隔開逆趣。隨后每行給出一個對方選擇的英雄：”Mccree”代表”麥克雷”，”Hanzo”代表”半藏”嗜历，”Genji”代表源氏汗贫。End代表輸入結(jié)束，這一行不要做任何處理秸脱。

數(shù)據(jù)保證：回合數(shù)最多不超過

Output

參照題意的規(guī)則落包，每次選擇一個英雄，單獨輸出一行摊唇。其中”Mercy”代表”天使”咐蝇，選擇”天使”時，接下來一行要接著輸出”Heroes never die”巷查。（所有輸出均不帶雙引號）

Simple Input1

2 3
Mccree
Hanzo
Genji
Genji
Hanzo
Mccree
End

Simple Output1

Genji
Hanzo
Mercy
Heroes never die
Genji
Mccree
Mccree

Source

SLF

思路

判斷每一回合是否為K或者N的倍數(shù)有序，然后按照題意要求輸出即可。

代碼

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

int main(){
    string Mccree = "Mccree",Hanzo = "Hanzo",Genji = "Genji";
    int n,k,cnt = 0;
    cin>>k>>n;
    while(true){
        cnt++;
        string str;
        cin>>str;
        if(str == "End") break;
        if(cnt%k==0){
            cout<<str;
        }else if(cnt%n==0){
            cout<<"Mercy"<<endl;
            cout<<"Heroes never die";
        }else{
            if(str == Mccree) cout<<Genji;
            else if(str == Hanzo) cout<<Mccree;
            else              cout<<Hanzo;
        }
        cout<<endl;
    }
    return 0;
}

L1-7 LXY的小機器人（20）

Problem Description

LXY上大三了岛请，他選修了機器人技術(shù)這門課旭寿。期末的大作業(yè)是要寫一段機器人的控制程序，完成某些功能崇败。LXY可以對機器人發(fā)布WSAD四個指令盅称，在二維平面上，指令分別表示：

W：機器人向上走一步（X,Y+1）

S：機器人向下走一步（X,Y-1）

A：機器人向左走一步（X-1,Y）

D：機器人向右走一步（X+1,Y）

LXY的程序會從頭到尾循環(huán)的運行后室，LXY設定的每個指令會在1s內(nèi)完成缩膝，現(xiàn)在LXY想知道經(jīng)過一段時間后，機器人所處在的二維平面上的位置是多少岸霹。（LXY開始時已經(jīng)將機器人放在(0,0)點）

Input

第一行輸入一串由‘W’,‘S’疾层，‘A’，‘D’組成的字符串贡避，表示指令（指令長度不超過2000）
第二行輸入一個數(shù)字N痛黎，表示LXY想知道經(jīng)過N秒后機器人的位置（N<=2000000000）

Output

輸出包括兩個數(shù)字予弧，表示經(jīng)過N秒后機器人的坐標位置，分別為橫坐標和縱坐標

Simple Input1

WSDDWSDAADW
12

Simple Output1

2 2

Source

LXY

思路

模擬題湖饱，但要注意數(shù)據(jù)范圍桌肴，數(shù)據(jù)。

所以若直接暴力模擬琉历，時間復雜度為O(N)坠七，在一秒內(nèi)無法完成。這里有許多同學沒有注意到這一點旗笔，導致無法通過最后兩個測試點彪置。

然后我們可以分析可得，完成一次指令周期機器人相對位置變化是固定的蝇恶，而指令周期len最長只有2000拳魁，時間復雜度O(len)是可以接受的。

于是我們可以先算出一個指令周期的相對位置撮弧，然后乘以（N/len）次潘懊，最后我們再模擬一次（N/len）的余數(shù)部分即可。

代碼

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int x = 0,y = 0;
    for(int i = 0;i<str.size();++i){
        if(str[i]=='W') ++y;
        if(str[i]=='S') --y;
        if(str[i]=='A') --x;
        if(str[i]=='D') ++x;
    }
    int len;
    cin>>len;
    x *= (len/str.size());y *= (len/str.size());
    for(int i = 0;i<(len%str.size());++i){
        if(str[i]=='W') ++y;
        if(str[i]=='S') --y;
        if(str[i]=='A') --x;
        if(str[i]=='D') ++x;
    }
    cout<<x<<" "<<y;
    return 0;
}

L1-8 LXY的圓和矩形（20））

Problem Description

LXY上初中了贿衍，數(shù)學老師有一天留下了一個作業(yè)授舟。已知圓上有N個點，給出每個點之間的弧長（為方便）輸入贸辈，給出的弧長已經(jīng)除了π释树，請問這些點一共能構(gòu)成多少個不重復的矩形。

Input

輸入第一行整數(shù)N（N<=100）擎淤，第二行輸入N個整數(shù)奢啥，表示相鄰每兩個點之間的弧長。

Output

輸出N個點所構(gòu)成的不重復的矩形個數(shù)

Simple Input1

8
1 2 2 3 1 1 3 3

Simple Output1

3

Hint

image.png

據(jù)說嘴拢，直徑所對的弦為半圓桩盲；

而且，直徑所對的圓周角為直角席吴；

那么問題來了赌结，矩形有幾個直角呢？

Source

LXY

思路

圓內(nèi)一條直徑對應的兩個圓周角均為直角抢腐，一個矩形有四個直角姑曙，所以兩條直徑確定一個矩形襟交。

我們計算出圓內(nèi)的點能連成多少條直徑迈倍，然后兩兩直徑算一次即可得出矩形數(shù)量。

如果兩個點連接的直線對應的弧長正好為總弧長的一半捣域，則該直線為圓的直徑啼染。

ps:只要兩個矩形四點任意一點不同就視為不同的矩形宴合。這里有一些同學可能考慮復雜了。

代碼

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
    int n,sum = 0,m = 0;
    cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
        sum += a[i];
    }
    for(int i = 1;i<=n;++i){
        int t = a[i];
        for(int j = i+1;j<=n-1;++j){
            t += a[j];
            if(t*2 == sum){
                ++m;
                break;
            }
        }
    }
    int res = 0;
    for(int i = 1;i<=m;++i){
        res+=(i-1);
    }
    cout<<res;
    return 0;
}

L2-1 竊取密碼（25）

Problem Description

LWH想要竊取ACM-ICPC系統(tǒng)的管理員密碼迹鹅，以提前查看今年World Final的題目卦洽。為此，他偷偷溜進管理員辦公室斜棚，偷了一張紙阀蒂，上面有一張清單，清單上有著個密碼弟蚀，密碼均由小寫的英文字母組成蚤霞。管理員密碼就在其中。
LWH回家后义钉，開始準備對系統(tǒng)進行黑客攻擊昧绣。為了破解系統(tǒng)，他不得不輸入一個個密碼進行嘗試捶闸。不過幸運得是夜畴，他發(fā)現(xiàn)了這些密碼具有等效性。

• 如果清單上兩個密碼a和b都包含同一個字母删壮，則密碼a等效于b

• 如果清單上兩個密碼a和b都等效于c贪绘，則a也等效于b

如果管理員密碼與某個密碼等效，則用戶也可以使用等效的密碼來登錄系統(tǒng)央碟。

例如兔簇，如果清單列表包含密碼”a”, ”b”, ”ab”, ”d”，則”a”, ”b”, ”ab”彼此等效硬耍，但密碼”d”不與清單列表中任何的密碼等效垄琐。所以：

• 如果管理員的密碼為”b”，那么您可以使用以下任何密碼訪問系統(tǒng)：”a”, ”b”, ”ab”经柴。

• 如果管理員的密碼為”d”,那么您只能使用”d”來訪問系統(tǒng)狸窘。

清單列表中只有一個密碼是測試系統(tǒng)的管理員密碼。請幫助LWH計算能正確進入系統(tǒng)所需的最小密碼數(shù)坯认。請記住翻擒，LWH不知道清單列表中哪個密碼是管理員的密碼。

Input

第一行包含一個整數(shù)牛哺，代表列表清單中的密碼數(shù)陋气。

接下來n行，每行一個非空字符串代表密碼引润，長度不超過50個字符巩趁。某些密碼可能一樣。

數(shù)據(jù)保證所有字符串總長度不超過淳附，所有密碼都由小寫英文字母組成议慰。

Output

輸出一個整數(shù)蠢古，代表需要測試密碼的最小數(shù)量，其中這些密碼能夠確保LWH進入系統(tǒng)别凹。

Simple Input1

4
a
b
ab
d

Simple Output1

2

Hint

第一個樣例LWH只需要測試兩個密碼即可草讶，一個密碼為”a”、”b”炉菲、”ab”中的任意一個堕战，因為它們相互具有等效性，另一個密碼為”d”拍霜，所以輸出2践啄。

Source

SLF

思路

題意要求算可以將給出的密碼列表分成多少類，同一類內(nèi)的密碼相互等效沉御。

我們可以用并查集來解決這個問題屿讽。

1、設置一個長度為26的整數(shù)數(shù)組吠裆，分別代表26個英文字母指向哪一個字符串伐谈。

2、遍歷每一個字符串的每一個字符试疙。

3诵棵、若該字符的數(shù)組尚未指向，這將該字符指向這個字符串祝旷。

4履澳、若該字符的數(shù)組已指向，這將該字符串用并查集指向該字符已指向的字符串怀跛。

5距贷、最后統(tǒng)計有多少個字符串指向自己即可。（在并查集中吻谋，每個字符串一開始均指向自己）

ps：如果寫得并查集常數(shù)較大或者沒有進行路徑壓縮忠蝗，只能拿到60%的分數(shù)。暴力查找求解也可以通過部分的測試點漓拾，但是代碼容易寫錯且分數(shù)不高阁最。

代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int f[MAXN];
int find_father(int x){return f[x]==x?x:f[x]=find_father(f[x]);}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int flag[110];
    memset(flag,0,sizeof(flag));
    int n;
    cin>>n;
    for(int i = 1;i<=n;++i){
        f[i] = i;
        string str;
        cin>>str;
        for(int j = 0;j<str.size();++j){
            int t = str[j]-'a';
            if(!flag[t]){
                flag[t] = i;
            }
            else{
                int tx = find_father(flag[t]);
                int ty = find_father(i);
                if(tx!=ty){
                    f[tx] = ty;
                }
            }
        }
    }
    int res = 0;
    for(int i = 1;i<=n;++i){
        if(i==find_father(i))
            res++;
    }
    cout<<res;
    return 0;
}

L2-2 愧疚往事（25）

Problem Description

Veggie想起高中注冊時幫了初中語文老師插隊交學費，至今內(nèi)心都因為那次插隊感到無比愧疚骇两。為了能夠讓這件愧疚往事成為教訓速种，Veggie決定通過建立插隊模型來體會那些被插隊者的心情。在模型中低千，每個人都屬于且僅屬于一個朋友圈配阵，圈內(nèi)的人相互之間都是朋友。他們在排隊時，會在隊伍從后往前找熟人闸餐，如果找到了自己的朋友饱亮，就排在朋友后面矾芙，否則才會選擇排到隊伍最后舍沙。Veggie正在為找實習而忙碌，于是請你幫忙編程實現(xiàn)這個模型剔宪。

Input

輸入第一行中給出兩個整數(shù)N拂铡、M，其中朋友圈個數(shù)葱绒，是指令條數(shù)感帅。

隨后N行中，每行給出一個朋友圈的信息地淀。首先是整數(shù)失球，表示這個朋友圈中的人數(shù)，接著是K個人員的編號(00000~99999)帮毁，中間用空格分開实苞。

隨后M行中，每一行給出一條模擬指令烈疚，指令有以下兩種形式：

"IN x": 表示編號為x的人員進入隊伍黔牵。

"OUT": 表示在隊首的人離開隊伍，此時我們需要輸出該人員的編號爷肝。
（注意：指令不含雙引號）

Output

按順序輸出離開隊伍的人員編號猾浦，每個人的編號占一行。如果對空的隊伍使用“OUT”指令灯抛，則輸出”EMPTY”（不含雙引號）金赦。

Simple Input1

3 16
3 00001 00002 00003
3 11111 22222 33333
5 05030 05116 05103 05139 05044
IN 00001
IN 11111
IN 05030
IN 00002
IN 22222
OUT
OUT
OUT
OUT
OUT
IN 00003
IN 05103
IN 05139
IN 00001
OUT
OUT

Simple Output1

00001
00002
11111
22222
05030
00003
00001

Source

LWH

思路

隊列模擬題。

為了處理方便对嚼，我們將每一個朋友圈編號素邪，然后用Map<string,int>來映射每一個人對應的朋友圈編號。（不用Map猪半，也可以用數(shù)組代替相應功能）

然后我們設置一個編號隊列T兔朦，用來存放正在排隊的朋友圈編號。

最后我們給每一個朋友圈都再單獨設置一個隊列Q磨确。

然后開始模擬：

當一個人x想入隊時沽甥，我們先判斷x所在的朋友圈隊列Q是否為空。

• 若為空證明總隊列中沒有x的朋友乏奥，所以將x入隊到Q中摆舟，同時將x所對應的朋友圈編號i入隊到編號隊列T中。

• 若不為空證明總隊列中有x的朋友，所以將x入隊到Q中即可恨诱。

當遇到出隊命令時,我們先判斷編號隊列T的隊首元素i,然后將i對應的隊列Q的隊首出隊.然后判斷Q是否為空,是則將隊列T隊首元素i進行出隊處理.

要注意處理遇到出隊命令時媳瞪，需要判斷隊列是否為空，否則會造成Runtime Error照宝。

所有入隊/出隊操作的時間復雜度都是O(lg(K*N))蛇受。

有許多同學直接暴力模擬題意，而沒有考慮到數(shù)據(jù)范圍和算法的時間復雜度厕鹃，造成Time Limit兢仰。

這道題對Java選手不太友好，因為Java讀入和自帶的數(shù)據(jù)結(jié)構(gòu)庫比較慢剂碴，算法正確的前提下可能會導致后面幾個點TLE把将。

代碼

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
using namespace std;
const int maxn = 1e5+10;
queue<int> q_id;
queue<int> q_member[1005];
int mapping[maxn], isInQueue[1005];
int n, m, k, t;
string str;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &t);
            mapping[t] = i;
        }
    }

    while (m--) {
        cin >> str;
        if (str == "IN") {
            scanf("%d", &t);
            if (!isInQueue[mapping[t]]) {
                isInQueue[mapping[t]] = 1;
                q_id.push(mapping[t]);
            }
            q_member[mapping[t]].push(t);
        } else {
            if (q_id.empty()) {
                printf("EMPTY\n");
                continue ;
            }
            int id = q_id.front();
            printf("%05d\n", q_member[id].front());
            q_member[id].pop();
            if (q_member[id].empty()) {
                q_id.pop();
                isInQueue[id] = 0;
            }
        }
    }
    return 0;
}

L2-3 關(guān)心員工（25）

Problem Description

SLF是G市某集團的總裁，他認為能一起打拼的員工都是好兄弟忆矛，因此他十分關(guān)心公司各個層次員工的生活水平察蹲。在公司中，每位員工都有且只有一名直屬上司（SLF除外）催训，而上司有可能有多個下屬員工洽议，于是各級員工之間就有了層次之分。為了更好地給員工補貼瞳腌，SLF會定期統(tǒng)計各層次員工的平均收入绞铃。由于SLF忙于處理集團事務，于是想請你幫忙編程解決這個問題嫂侍。

Input

輸入第一行中給出一個整數(shù)儿捧，即整個公司的總?cè)藬?shù)，每個員工從1到N編號挑宠，總裁SLF的編號為1菲盾。隨后N行，第i行給出編號為i的員工的相關(guān)信息各淀，格式如下：

其中K是一個整數(shù)懒鉴，表示該員工直接下屬員工的個數(shù)，是直接下屬員工的編號碎浇，Salary是一個正數(shù)临谱，表示該員工的收入。

Output

在一行中對應輸出公司的層次數(shù)m奴璃，隨后m行中輸出各層次員工的平均工資悉默，格式為”Level i: ”（不含雙引號）,其中表示第i層員工的平均工資，需要保留兩位小數(shù)苟穆。

Simple Input1

7
2 2 3 100
3 4 5 6 2
1 7 3
0 4
0 5
0 6
0 7

Simple Output1

3
Level 1: 100.00
Level 2: 2.50
Level 3: 5.50

Source

LWH

思路

對多叉樹進行層序遍歷抄课，計算每一層員工的平均和有多少層唱星，最后輸出即可。

這里有個注意的點是：題目中的工資Salary是正數(shù)跟磨，而不是整數(shù)间聊，所以輸入的變量要設置為浮點數(shù)。

這個點許多同學沒有注意到從而造成Wrong Answer抵拘，真是令人可惜哎榴。這也表明了同學們讀題能力稍顯薄弱，有待加強啊仑濒。

//你要問題意為什么這么坑叹话？沒辦法偷遗，天梯賽的真題就有這樣坑人的墩瞳。(手動滑稽)

代碼

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 1e5 + 10;
vector<int> tree[maxn];
double num[maxn], salary;
int n, m, root, t;

void bfs(int root) {
    //pre_level表示當前層數(shù)，node_num表示本層的節(jié)點數(shù)
    int pre_level = 1, node_num = 0;
    //本層的平均值
    double avg = 0;
    vector<double> ans;
    queue<pair<int, int> > q;
    q.push(make_pair(root, 1));
    while (!q.empty()) {
        int node = q.front().first;
        int level = q.front().second;
        q.pop();
        //當去到新的一層就統(tǒng)計上一層的數(shù)據(jù)
        if (level != pre_level) {
            ans.push_back(avg / node_num);
            node_num = 0;
            avg = 0;
            pre_level = level;
        }
        //數(shù)量和工資的累計
        node_num++;
        avg += num[node];
        //將所有的子節(jié)點放入隊列中
        for (int i = 0; i < tree[node].size(); i++) {
            q.push(make_pair(tree[node][i], level + 1));

        }
    }
    //由于最后一層無法再到達新的一層氏豌，所以要單獨計算
    ans.push_back(avg / node_num);

    //輸出結(jié)果
    printf("%d\n", pre_level);
    for (int i = 0; i < ans.size(); i++) {
        printf("Level %d: %.2f\n", i + 1, ans[i]);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> t;
            tree[i].push_back(t);
        }
        cin >> salary;
        num[i] = salary;
    }
    bfs(1);
    return 0;
}

L2-4 奇怪的需求增加了.jpg（25）

Problem Description

自從復工以來喉酌，CGY 一直在接一些奇怪的需求，需求多到做都做不完（他急了泵喘，他急了）泪电。由于 CGY 是單核單線程處理器（Intel 賽揚 B720），所以他每次只能同時做一個需求〖推蹋現(xiàn)在 CGY 手上堆了 個需求相速，每個需求都需要一段時間完成，如果他在一定時間內(nèi)沒有完成某個需求鲜锚，那么這個需求就會被他的師兄憶兔之心拿過去做突诬，這樣憶兔之心就有可能抓到 CGY 把之前趕需求的時間都用來打雀魂（而且還上不了雀圣）的把柄。為了防止被發(fā)現(xiàn)芜繁，CGY 需要完成盡可能多的需求旺隙，那你能幫幫他嗎？

9c551c53ca.png

Input

第一行是一個整數(shù) 骏令。

接下來 行每行兩個整數(shù) 和 蔬捷，描述了一個需求：完成這個需求需要 小時，如果在 小時之內(nèi)還沒有完成（如果剛好在 時刻完成也算完成榔袋，踩點不算遲到嘛）周拐，這個需求就被撈走了。（數(shù)據(jù)保證 ）

Output

輸出一個整數(shù) 凰兑，表示最多可以完成 個需求妥粟。

Simple Input1

4
100 200
200 1300
1000 1250
2000 3200

Simple Output1

3

Source

CGY

思路

堆+貪心。

我們可以先按照進行升序排序聪黎，然后遍歷這些需求罕容。遍歷的同時維護一個nowtime（代表現(xiàn)在的時刻）备恤，如果當前需求能夠被滿足，就將這個需求加入到優(yōu)先隊列PQ（其中PQ是的大根堆）锦秒。如果當前需求不能被滿足露泊，則判斷當前需求能否替換掉PQ頂端的需求，可以的話就替換旅择，另外需要注意替換后nowtime可能會發(fā)生變化惭笑。這樣替換并不會造成錯誤，因為我們已經(jīng)對需求進行排序生真，所以替換對PQ中的其他需求不會產(chǎn)生沖突沉噩。

代碼

#include <bits/stdc++.h>

using namespace std;

int n;
pair<long long, long long> needs[150010];
priority_queue<long long> pq;
int ans;
long long last;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> needs[i].second >> needs[i].first;
    }
    sort(needs, needs + n);
    for (int i = 0; i < n; ++i) {
        if (last + needs[i].second <= needs[i].first) {
            ++ans;
            last += needs[i].second;
            pq.push(needs[i].second);
        } else if (!pq.empty() && needs[i].second < pq.top()) {
            last += needs[i].second - pq.top();
            pq.pop();
            pq.push(needs[i].second);
        }
    }
    cout << ans << endl;

    return 0;
}

L3-1 《還債啦！動物森友會》（30）

Problem Description

Dr.Su 每天辛苦工作柱蟀，缺乏休息時間川蒙，只能深夜在夢里玩動物之森聊以慰藉。在夢里长已，帶資本家貍吉還是那個貍吉畜眨，西施惠還是那個西施惠，該還的貸款還是要還术瓮。于是康聂，Dr.Su 給夢里的這個版本起名叫《還債啦！動物森友會》胞四。

在《還債啦恬汁！動物森友會》里，賺錢的唯一方法是——從地上收集樹枝賣錢（這才是真正的里數(shù)挑戰(zhàn)）辜伟。這次的無人島是一個 的長方形島嶼（難道哪一次不是嗎氓侧？），第 行 列的格子內(nèi)可以收集到 個樹枝游昼。Dr.Su 只會向上下左右四個方向走甘苍，并且不能離開這座無人島（離開了貍吉會把你綁回來繼續(xù)打工的），每當他走到一個格子烘豌，就會花費一個單位的時間將格子內(nèi)的樹枝全部收集完载庭。眾所周知，這是一個神（keng）奇（die）的島嶼廊佩，所以當 Dr.Su 收集完并離開某一格子后囚聚，該格子會重新刷新出原來所有的樹枝。

Dr.Su 建的房子（房子所在的格子沒有樹枝）在第 行 列标锄，他從這里出發(fā)顽铸，花費 單位的時間收集樹枝，且 單位時間過后他恰好回到自己的房子料皇，請問他最多能采集多少樹枝谓松？

（什么星压？你問 Dr.Su 這么聰明為什么不自己算？有動森玩誰還做題肮砥Ｄ缺臁）

微信圖片_20200328141305.jpg

Input

第一行共五個正整數(shù)，分別是行數(shù) 优质、列數(shù) 竣贪、房子位置 、 和時間 巩螃，保證 是偶數(shù)演怎。

接下來 行每行 個非負整數(shù) ，表示對應位置樹枝的數(shù)量避乏。且保證 爷耀。

Output

一個整數(shù)，表示 Dr.Su 能采集到的最多的樹枝數(shù)淑际。

Simple Input1

2 2 1 1 2
0 1
2 1

Simple Output1

2

Simple Input2

2 2 1 1 4
0 5
5 10

Simple Output2

20

Simple Input3

3 3 2 2 6
5 1 0
1 0 3
1 3 3

Simple Output3

15

Source

CGY

思路

登頂題畏纲。

首先扇住，Dr.Su的路徑可以視作原路返回春缕。因為路徑采摘樹枝數(shù)sum = 去時采摘的樹枝數(shù)x + 回時采摘的樹枝數(shù)y，如果x是最優(yōu)的x艘蹋，那么想要sum最大锄贼，那么y必定 = x。所以我們可以將時間K/2女阀，只需要算x宅荤，最后答案 = x*2。

所以我們可以進行搜索處理浸策，但由于時間K最大有1e9，所以會超時。

其次春瞬，我們分析可得山上，如果K/2 ＞ n*m，那么Dr.Su會在最后一定會轉(zhuǎn)圈圈蚯舱，而且圈的周長等于2改化，也就說Dr

.Su會在兩個格子之間反復橫跳。因為我們可以假設如果圈的周長 = n枉昏，那么這n個格子里面一定可以選出兩個格子使得這兩個格子的樹枝數(shù)/2 ＞= n個格子的樹枝數(shù)/n陈肛。

所以如果K/2 ＞ n*m，那么我們只用對全部格子記憶化搜索n*m次即可兄裂。

代碼一

#include <bits/stdc++.h>

using namespace std;

#define INF 0x7f7f7f7f

long long n;
long long m;
long long a;
long long b;
long long k;
long long c[110][110];
long long dp[110][110][2];
long long ans;
long long dx[4] = {-1, 0, 1, 0};
long long dy[4] = {0, 1, 0, -1};
long long step;
int tag = 0;

bool check(int x, int y) {
    return !(x < 1 || y < 1 || x > n || y > m);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> a >> b >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c[i][j];
            dp[i][j][0] = dp[i][j][1] = -INF;
        }
    }
    k /= 2;
    step = min(k, n * m);
    dp[a][b][0] = 0;
    for (int i = 1; i <= step; ++i) {
        tag ^= 1;
        for (int row = 1; row <= n; ++row) {
            for (int col = 1; col <= m; ++col) {
                long long maxp = -INF;
                long long maxc = -INF;
                for (int dir = 0; dir < 4; ++dir) {
                    int newx = row + dx[dir];
                    int newy = col + dy[dir];
                    if (check(newx, newy)) {
                        maxp = max(maxp, dp[newx][newy][1 ^ tag]);
                        maxc = max(maxc, c[newx][newy]);
                    }
                }
                if (maxp != -INF) {
                    dp[row][col][tag] = maxp + c[row][col];
                    ans = max(ans, dp[row][col][tag] * 2 - c[row][col] + (maxc + c[row][col]) * (k - i));
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

代碼二（ZLM大師37ms的代碼orz）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

const int dir_x[] = {0, 0, -1, 1};
const int dir_y[] = {-1, 1, 0, 0};
const int MAXN = 101;

long long dp[MAXN][MAXN], ss[MAXN][MAXN];
int s[MAXN][MAXN], step[MAXN][MAXN];

int main() {
    int n, m, a, b, k;
    memset(dp, 0xFF, sizeof(dp));
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &k);
    k >>= 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", s[i] + j);
    memset(ss, 0, sizeof(ss));
    for (int x = 1; x <= n; ++x)
        for (int y = 1; y <= m; ++y) {
            for (int i = 0; i < 4; ++i) {
                int xx = x + dir_x[i];
                int yy = y + dir_y[i];
                if (!xx || xx > n || !yy || yy > m) continue;
                ss[x][y] = std::max(ss[x][y], (long long)s[x][y] + s[xx][yy]);
            }
        }
    long long ans = 0;
    std::queue< std::pair< int, int > > q;
    q.push(std::make_pair(a, b));
    dp[a][b] = 0;
    step[a][b] = 0;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (step[x][y] > k) break;
        long long left = k - step[x][y];
        left *= ss[x][y];
        ans = std::max(ans, (dp[x][y] << 1) + left - s[x][y]);
        for (int i = 0; i < 4; ++i) {
            int xx = x + dir_x[i];
            int yy = y + dir_y[i];
            if (!xx || xx > n || !yy || yy > m) continue;
            long long tmp = dp[x][y] + s[xx][yy];
            if (dp[xx][yy] == -1 || dp[xx][yy] + ((step[x][y] + 1 - step[xx][yy]) >> 1) * ss[xx][yy] < tmp) {
                dp[xx][yy] = tmp;
                step[xx][yy] = step[x][y] + 1;
                q.push(std::make_pair(xx, yy));
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

總結(jié)

這次比賽的前10名榜單每隔幾分鐘就會發(fā)生變化句旱，競爭非常激烈阳藻。

這套題目的Lv1難度相對較低，所以主要拉開差距的題目在于Lv2數(shù)據(jù)結(jié)構(gòu)方面的題目谈撒，這也和天梯賽現(xiàn)場賽題目的難度分布相同稚配。如果同學們感覺做Lv2數(shù)據(jù)結(jié)構(gòu)的題目稍顯吃力，表明數(shù)據(jù)結(jié)構(gòu)這方面有待加強港华。

無論結(jié)果如何道川，盡了自己最大的努力便是成功。沒有入圍隊伍名單的同學不用氣餒立宜，好好準備接下來的藍橋杯等賽事吧~