手機(jī)站首頁(yè)散文詩(shī)歌雜文隨筆日記小小說

散文網(wǎng) » 科技 »學(xué)習(xí) » 2021GPLT 團(tuán)體程序設(shè)計(jì)天梯賽個(gè)人題解

2021GPLT 團(tuán)體程序設(shè)計(jì)天梯賽個(gè)人題解

2021-04-26 21:44 作者:俊杰_Charles 0人讀過 | 我要投稿

比賽地址：https://gplt.patest.cn/

題目鏈接：https://pintia.cn/problem-sets/994805046380707840/

難度：L1<L2<L3

由于B站專欄的代碼塊功能有 bug，如果代碼塊不能正常顯示，請(qǐng)通過代碼鏈接查看代碼。

L1-1 人與神

題意：輸出“To iterate is human, to recurse divine.”。

代碼鏈接：https://paste.ubuntu.com/p/JHD5XQcjcw/

L1-2 兩小時(shí)學(xué)完C語(yǔ)言

題意：共? $n$ 個(gè)字，每分鐘看? $m$ 個(gè)字，看了? $k$ 分鐘，還剩多少字沒看。保證 $mk%5Cle%20n$ 。

題解： $n-mk$

代碼鏈接：https://paste.ubuntu.com/p/NtBPBPsrBj/

L1-3 強(qiáng)迫癥

題意：將“年年月月”或“年年年年月月”格式的字符串格式化為“年年年年-月月”。

代碼鏈接：https://paste.ubuntu.com/p/MGB9vWmJF4/

L1-4 降價(jià)提醒機(jī)器人

題意：當(dāng)玩具的當(dāng)前價(jià)格比他設(shè)定的價(jià)格便宜時(shí)發(fā)出提醒。

代碼鏈接：https://paste.ubuntu.com/p/Sy4scJkcdc/

L1-5 大笨鐘的心情

題意：給定大笨鐘在一天? $24$ 小時(shí)中每個(gè)小時(shí)的心情指數(shù)，對(duì)于若干次詢問，每次詢問某一時(shí)間大笨鐘的心情指數(shù)，并判斷是否大于 $50$ 。

代碼鏈接：https://paste.ubuntu.com/p/YBdNgwXvF8/

L1-6 吉老師的回歸

題意：給定? $n$ 個(gè)字符串，輸出第? $m%2B1$ 個(gè)不含 "qiandao" 或 "easy" 子串的字符串，若滿足條件的字符串不超過? $m$ 個(gè)則輸出 "Wo AK le"。

題解：getline 與 find 函數(shù)的運(yùn)用。

代碼鏈接：https://paste.ubuntu.com/p/GWnmrV664n/

L1-7 天梯賽的善良

題意：給定? $n$ 個(gè)數(shù)，求最大的數(shù)及其個(gè)數(shù)，以及最小的數(shù)及其個(gè)數(shù)。

題解：map 容器的運(yùn)用。

代碼鏈接：https://paste.ubuntu.com/p/d5q7XSxsmx/

L1-8 乘法口訣數(shù)列

題意：給定的兩個(gè)? $1$ 位數(shù)字? $a_1$ 和 $a_2$ ，生成一個(gè)數(shù)列 $%5C%7Ba_n%5C%7D$ ，規(guī)則為從 $a_1$ 開始順次進(jìn)行，每次將當(dāng)前數(shù)字與后面一個(gè)數(shù)字相乘，將結(jié)果貼在數(shù)列末尾。如果結(jié)果不是? $1$ 位數(shù)，則其每一位都應(yīng)成為數(shù)列的一項(xiàng)。

代碼鏈接：https://paste.ubuntu.com/p/Y45nMyyDNd/

L2-9 包裝機(jī)

題意：有? $n$ 條軌道，各軌道初始有? $m$ 件物品，還有一個(gè)最大容量為? $s$ 的棧。給定若干操作，若操作號(hào)為 $0$ ，表示從棧頂取出一件物品放在流水線上；否則將對(duì)應(yīng)編號(hào)軌道的首個(gè)物品推入棧中，若棧滿，則先從棧頂取出一件物品放在流水線上，再將軌道上的物品推入棧中。若每次操作對(duì)應(yīng)軌道或棧為空，則忽略該次操作。

代碼鏈接：https://paste.ubuntu.com/p/bh68svWT36/

L2-10 病毒溯源

題意：給定一個(gè)有向無(wú)環(huán)圖，求出圖上最長(zhǎng)鏈。

題解：記憶化搜索。注意沒有說必須從? $0$ 開始。

代碼鏈接：https://paste.ubuntu.com/p/Pby77dVpqm/

L2-11 清點(diǎn)代碼庫(kù)

題意：有? $n$ 個(gè)代碼，每個(gè)代碼的輸出有 $m$ 個(gè)數(shù)。統(tǒng)計(jì)有多少種不同的輸出，以及各種輸出的個(gè)數(shù)。輸出時(shí)按個(gè)數(shù)從大到小排序，若個(gè)數(shù)相同則按字典序。

題解：注意 vector 是可以直接排序的，與 string 一樣都是按字典序，因此直接使用 map 容器統(tǒng)計(jì)個(gè)數(shù)，最后 sort 一下就好了。

代碼鏈接：https://paste.ubuntu.com/p/g5QfCw52jY/

L2-12 哲哲打游戲

題意：給定一張有向圖與若干次操作，操作 0 x 表示走當(dāng)前位置的第? $x$ 條出邊，操作 1 x 表示將當(dāng)前位置存檔在第? $x$ 個(gè)檔位，操作 2 x 表示從第? $x$ 個(gè)檔位讀取位置，求每次存檔時(shí)的位置以及最終位置。

代碼鏈接：https://paste.ubuntu.com/p/Bkm3GFpHBs/

L3-13 森森旅游

題意：給定一張有向圖，每條邊的花費(fèi)為? $c$ 元現(xiàn)金或? $d$ 元旅游金。第? $i$ 個(gè)城市的匯率為 $a_i$ ，表示在第? $i$ 個(gè)城市可以用? $1$ 元現(xiàn)金換取? $a_i$ 元旅游金?，F(xiàn)要從起點(diǎn) $1$ 走到終點(diǎn) $n$ ，要求開始時(shí)都使用現(xiàn)金，然后在某個(gè)城市將所有現(xiàn)金全部換為旅游金，然后剩下的部分都使用旅游金。有? $q$ 次詢問，每次詢問會(huì)將某個(gè)城市的匯率? $a_i$ 改為 $a_i'$ ，對(duì)每次詢問求最少需準(zhǔn)備多少現(xiàn)金。

題解：先跑兩次最短路，分別求出起點(diǎn)到各點(diǎn)最少花費(fèi)多少現(xiàn)金，以及各點(diǎn)到終點(diǎn)最少花費(fèi)多少旅游金。令起點(diǎn)到點(diǎn)? $i$ 最少花費(fèi)? $x$ 元現(xiàn)金，點(diǎn)? $i$ 到終點(diǎn)最少花費(fèi)? $y$ 元旅游金，則在點(diǎn) i 將所有現(xiàn)金全部換為旅游金時(shí)最少準(zhǔn)備現(xiàn)金? $x%2B%5Clceil%5Cfrac%7By%7D%7Ba_i%7D%5Crceil$ 元，對(duì)各點(diǎn)求出結(jié)果取最小值即可。對(duì)于修改操作，由于僅修改 $a_i$ ，不影響最短路，因此每次修改只有對(duì)應(yīng)位置的答案會(huì)發(fā)生變化，用一個(gè) multiset 維護(hù)最小值即可。計(jì)算答案時(shí)要注意判斷該位置是否可達(dá)。

代碼鏈接：https://paste.ubuntu.com/p/GBzwqtNgf8/

L3-14 還原文件

題意：將一個(gè)串拆成若干子串，問如何將這些子串拼回原串，保證解唯一。

題解：將每個(gè)子串在原串中進(jìn)行匹配，每個(gè)匹配用一個(gè)有向邊表示，邊權(quán)為對(duì)應(yīng)子串的編號(hào)以防重復(fù)。最終在得到的有向圖上找到一條從起點(diǎn)到終點(diǎn)所有邊的編號(hào)互不相同的鏈即可。本題數(shù)據(jù)較弱，字符串匹配使用暴力方法即可，最終求答案直接 dfs 搜索。

代碼鏈接：https://paste.ubuntu.com/p/Q6zXZN5NPh/

L3-15 可憐的簡(jiǎn)單題

輸出 1 即可騙到 1 分。

這場(chǎng)比賽我個(gè)人最大的感受是，如果能熟練運(yùn)用 stl 的話，做前兩檔難度的題目速度會(huì)非?？?，可以留更多時(shí)間給第三檔的題目。比賽開始時(shí)服務(wù)器還是出問題了，希望主辦方之后能有所改善。這次的題目質(zhì)量比起上次的來(lái)說確實(shí)有進(jìn)步，希望比賽能越辦越好吧。

算法競(jìng)賽交流群：1043272289

標(biāo)簽：