2021 RoboCom 世界機器人開發者大賽-本科組(復賽)
文章目錄
7-1 冒險者分隊 20
7-2 拼題A打卡獎勵 25
7-3 快遞裝箱 25
7-4 塔防游戲 30
7-1 冒險者分隊 20
由于完成任務有能力的要求,因此我們需要對 NPC 進行一定的訓練。NPC 組成的小隊會有三個屬性:體能、心智,以及戰術,玩家可以選擇以下的兩種訓練課程之一對小隊進行訓練:
提升其中一個屬性 40,降低其他兩個屬性各 20;
提升其中兩個屬性 20,降低剩下一個屬性 40。
如果在選擇的訓練課程后有任意一個屬性小于 0,那么訓練會失敗,屬性不會發生變化。
為了完成特定任務,現在給定小隊的初始屬性和目標屬性,請回答是否有可能通過一定的訓練,使得小隊的屬性正好達到目標屬性的值,如果可以的話,最少的次數是多少?
輸入格式:
輸入第一行是一個正整數 T (≤10
5
),表示有多少組詢問。
接下來的 T 組詢問,每組詢問有兩行,每行三個非負整數,第一行為小隊初始的屬性,第二行為需要達成的目標屬性。
所有屬性值均大于等于 0,小于等于 2×10
9
。
輸出格式:
如果目標屬性無法通過訓練達到,輸出一行 ?1,否則輸出一個整數,表示達到目標屬性的最少訓練次數。
輸入樣例:
4
25 30 35
65 10 15
100 200 300
200 180 220
100 100 100
0 0 0
777 888 999
777 888 999
輸出樣例:
1
3
-1
0
題意:給出初始數組和目標數組,長都為3。每次可以給兩個數+20,一個-40,或者兩個-20,一個加40,求最少多少次能變成目標數組。
思路:
首先,初始數組和目標數組之間只能通過20來變換,所以對應位置的值作差%20,有余數肯定直接-1。然后把三個差值/20,簡化問題。
然后,考慮非法的情況,不管是-1,-1,+ 2還是 -2,+1,+1,這三個數%3的值都是1,因為最后要讓差值從(a,b,c)變成(0,0,0),所以原本的這三個差值必須%3相等,否則-1。
最后,考慮構造最優解。 設a < b < 0 < c,我們以1,1,-2作用于三者,那么b會首先變成0。再然后,再以兩個操作2,-1,-1和1,1,-2組合成3,0,-3作用于a和c,就可以構造出(0,0,0)。(如果a或c不能被3整除怎么辦?事實是不會的,因為上面已經判過三者對3同余了,所以三者%3都等于0,必定是能整除的)
#include 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 7-2 拼題A打卡獎勵 25 輸入格式: 輸入首先在第一行中給出兩個正整數 N(≤10 3 ) 和 M(≤365×24×60),分別對應打卡卷的數量和以“分鐘”為單位的活動總時長(不超過一年)。隨后一行給出 N 張打卡卷要花費的時間 m i (≤600),最后一行給出 N 張打卡卷對應的獎勵金幣數量 c i (≤30)。上述均為正整數,一行內的數字以空格分隔。 輸出格式: 在一行中輸出最多可以贏得的金幣數量。 輸入樣例: 5 110 70 10 20 50 60 28 1 6 18 22 輸出樣例: 40 樣例解釋: 選擇最后兩張卷子,可以在 50+60=110 分鐘內獲得 18+22=40 枚金幣。 題意:n個物品,有價值和體積,每個可以選一次,背包容量m,求最大價值。 思路: 01背包板子題???果然TLE(15分)。 n < 1e3, m < 5e5,所以O(nm)1e8肯定會超時。 發現金幣數量ci < 30 成為一個突破口,此時所有物品總價值不超過1000?30,因此可以轉換原本的求 “最小容量(5e5)下的最大價值” 為 “最大價值(3e4)下的最小容量”,系數都是n,3e7勉強可以通過。 //15分 #include 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 //25分 #include 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 7-3 快遞裝箱 25 有一條快遞裝箱的流水線是這樣設計的(見下圖): fig.png 快遞件從 A 口進入流水線轉盤;到達 B 時進行稱重,如果重量大于 W 1 就開一個新的箱子把它裝進去,否則直接讓它通過;到達C時檢查箱子的重量,如果超過了 W 2 (>W 1 ),就直接裝車 —— 這條線有 1 號攝像頭拍攝裝車的箱子編號并記錄;重量不達標的箱子或快遞件繼續行進到 D,在這里進行裝箱處理。這里分幾種情況: 如果 D 當前是空的,那么新開一箱給到達的快遞件,或者如果到達的是一只箱子,那么等待下一個快遞件到達; 如果 D 當前不是空的,那么肯定是有一只箱子。這時考察下一個物體 —— 如果下一個是快遞件并且能裝入這個箱子(即總重量不超過箱子的最大容量 W max ),則將其裝入;如果下一個是快遞件但裝不下了(這時新的快遞件裝箱),或者下一個來的就是箱子,或者已經沒有貨物過來了,則停止當前的裝箱工作,檢查當前這個箱子的重量,超過 W 2 就裝車 —— 這條線有 2 號攝像頭拍攝裝車的箱子編號并記錄;如果重量不足,則繼續前進到 A 口,與新到的快遞件匯合。D 點繼續處理下一個排隊的箱子或快遞件。 而到 A 口的箱子則要看匯合的快遞件能否裝入:如果可以就裝箱,向 B 進發;不行就一直等待,直到下一個可以裝箱的快遞裝進去,或者沒有任何新的快遞到達,才繼續向 B 進發。當有多只箱子從 D 轉過來時,按到達的順序排隊。 簡單起見,我們假設快遞件勻速進入流水線,所有快遞件從一個點到下一個點都只需要一個單位時間,并且在 B 和 C 的停留時間可忽略不計。當 B 發現重量大于 W 1 的是已經在箱子里的貨物時,則不必再新開一個箱子。 輸入格式: 輸入在第一行給出 4 個正整數:N 為快遞件的數量;W max 、W 1 和 W 2 ,如題面所述。其中 N≤10 4 ,W 1 2 max ≤10 3 。 隨后一行給出 N 個不超過 W max 的正整數,為順序到達的快遞件的重量。 輸出格式: 在第一行中先后輸出第 1、2 號攝像頭拍攝的裝車箱子的數量、以及最后轉盤上剩下的箱子的數量。第二行按非遞減序輸出剩下的箱子的重量。如果沒有箱子剩下,則輸出 None。 同一行數字間以 1 個空格分隔,行首尾不得有多余空格。 輸入樣例: 11 100 50 80 85 25 60 21 10 52 80 95 78 15 3 輸出樣例: 2 1 4 40 55 78 80 樣例說明: 我們按照“單位時間:事件”的格式描述整個過程。 時間 A B C D 1 85 - - - 2 25 85裝箱 - - 3 60 25 85裝車,1號拍攝 - 4 21 60裝箱 25 - 5 10 21 60一箱 25裝箱 6 52 10 21 60一箱到,25一箱啟動 7 80不能裝箱,25一箱等待 52裝箱 10 21裝箱得到81一箱 8 95不能裝箱,25一箱等待 80裝箱 52一箱 10裝箱得到91一箱 9 78不能裝箱,25一箱等待 95裝箱 80一箱 52一箱到,91一箱裝車,2號拍攝 10 15裝箱得到40一箱 78裝箱 95一箱裝車,1號拍攝 80一箱到,52一箱啟動 11 3裝箱得到55一箱 40一箱 78一箱 80一箱 此時攝像頭 1 拍攝了 2 次,攝像頭 2 拍攝了 1 次,轉盤上還剩 4 只重量為 55、40、78 和 80 的箱子。 題意:模擬流水線,塞個貨物進傳送帶,然后往后運動,更新一下每個點的狀態,如果有貨物運出就答案加一,照著題目意思做就行。 思路: A、D 點用雙端隊列處理(因為有塞回去的情況),B、C用普通隊列處理。 用一個 pair 存儲貨物狀態,分別記錄重量和是否裝箱,每次按題目要求更新即可。 #include 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 7-4 塔防游戲 30 有一種簡單的塔防游戲是這樣的:給定一張由 n 行 m 列個方格子構成的地圖,玩家可以任選一個格子放置自己的大本營,還可以在任意一個格子里放置自己的防御堡壘。大本營和每個防御堡壘都有自己的防御能力值 d,表示可以抵御 d 個僵尸的攻擊。每一輪游戲開始時,玩家在規定時間內將本級別可以用的防御堡壘布置在地圖中,然后僵尸們就從地圖邊界涌入地圖中,向著大本營發起攻擊。每輪進攻持續一個固定的時長,結束后剩余的僵尸就原地蒸發。 每隊僵尸可以向一個方格的上下左右四個方向移動。如果相鄰的目標方格沒有堡壘,它們就可以用 1 秒的時間移動過去,否則會被堡壘阻擋或者消滅。對每一隊僵尸(從同一地點出發的所有僵尸)而言,每秒會被堡壘消滅 1 個隊友,同時消耗掉該堡壘 1 個單位的防御能力。當防御能力降為 0,則該堡壘消失,剩下的僵尸則用 1 秒移動到這個方格繼續行進。注意:如果有多支僵尸隊都進入了同一個方格,它們并不會合并成一支隊伍。 所有的僵尸隊都會根據進攻開始時的地圖選擇被殲滅最少的到達大本營的路線,并且一直按照這個路線行進,中途不因為地圖狀態的改變而改變。當這樣的進攻路徑不唯一時,選擇能最快到達大本營的路徑。題目保證這樣的路徑所打掉的堡壘的布局是唯一的。 本題就要求你計算出一輪攻擊結束時,地圖上的布局情況。 輸入格式: 輸入首先在第一行中給出三個正整數:不超過 100 的 n 和 m,為地圖的尺寸;不超過 1000 的 T,為一輪攻擊持續的時長。 隨后給出 n+2 行,每行給出 m+2 個數字,每行中的數字都用空格分隔,表示攻擊開始前地圖上的布局。其中第 1 行、第 1 列、第 n+2 行、第 m+2 列是地圖邊界外僵尸們出發的位置,這些位置上,0 表示沒有僵尸,其他正整數表示從該位置出發的僵尸們的數量。而地圖中的每個位置上,0 表示沒有堡壘,其它正整數表示該位置上堡壘的防御能力值。大本營是一個特殊的建筑,我們用一個負數 ?D 表示這里是大本營,其防御能力值為 D。這里的防御值和任一隊僵尸的數量都不超過 100。 注意:僵尸不可在地圖邊界外移動,它們的第一個移動目標必須在地圖中,所以四個角落里出現的僵尸可以被忽略,因為它們沒有進入地圖的途徑。 輸出格式: 輸出 n 行,每行 m 個數字,對應攻擊結束后地圖上每個方格的狀態。狀態的表示與輸入相同:沒有堡壘的地方輸出 0,有堡壘的地方輸出其剩余防御值,大本營的位置上輸出其剩余防御值的負值。 注意每行數字間以 1 個空格分隔,行首尾不得有多余空格。 當大本營被攻陷時,游戲即刻結束。此時應輸出結束時的地圖狀態,并且在最后一行輸出一句 Game Over。 輸入樣例 1: 7 5 17 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 2 1 0 0 0 0 7 5 3 0 8 0 1 4 -10 1 0 0 0 0 3 3 0 0 0 0 8 0 9 0 0 0 0 0 4 0 0 0 輸出樣例 1: 0 0 0 0 0 0 0 8 0 0 0 0 0 2 0 0 0 7 5 0 0 0 0 -1 0 0 0 0 2 0 0 8 0 9 0 樣例說明: 地圖布局如下圖所示。 map.JPG 規模為 13 和 8 的兩隊僵尸都有兩種選擇,攻打藍色或者紫色堡壘都是消耗最少的。在這種情況下,規模為 13 的僵尸隊走藍色比較快,需要 1+1+1+2+4+2=11 秒到達大本營邊上;規模為 8 的僵尸隊走紫色比較快,需要 1+2+5=8 秒到達大本營邊上。 規模為 4 的僵尸隊比較慘,只能選擇綠色堡壘,最后被大本營邊上的綠色堡壘消滅。注意到在攻擊過程中,其實它們可以等到紫色堡壘被攻陷之后走紫色原始值為 4 的方格,但是因為路徑是在初始狀態下選定就不能改的,所以它們不能這樣選擇。 攻打大本營時,規模為 8 的僵尸隊剩下了 3 只先到達,在第 11 秒被大本營消滅。此時大本營還剩 7 個單位的防御值,同時規模為 13 的僵尸隊剩下的 8 只進入了大本營相鄰的方格,開始攻擊。但此時距離本輪結束只剩 6 秒,結果大本營在結束時還剩 1 個單位的防御值,玩家勝。 輸入樣例 2: 7 5 20 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 2 1 0 0 0 0 7 5 3 0 8 0 1 4 -10 1 0 0 0 0 3 3 0 0 0 0 8 0 9 0 0 0 0 0 4 0 0 0 輸出樣例 2: 0 0 0 0 0 0 0 8 0 0 0 0 0 2 0 0 0 7 5 0 0 0 0 0 0 0 0 0 2 0 0 8 0 9 0 Game Over 樣例說明: 樣例 2 與樣例 1 唯一的區別在于攻擊時長變為 20。但實際上,攻擊在第 18 秒就結束了。 題意:T秒為一輪游戲的時長,然后n行m列的地圖為玩家領地,領地中有防御為-D的大本營和防御為a[i][j]的堡壘,防御值可以和僵尸1:1換血。僵尸從四周一圈(n+2行,m+2列)往中間走,走的路線為開局時被殲滅最少的去大本營的路線。求最后僵尸能不能打下大本營。 思路: 首先:比較難搞的就是開局時僵尸走的最短路線,因為起點不同而終點一致,我們可以從終點出發的跑最短路,因為是網格圖,所以可以跑帶優先隊列的 Dijkstra不容易被卡。 然后:確定了僵尸的行走路線之后,就是按照時間移動僵尸模擬即可。做法就是維護僵尸在的位置,每次掃一遍所有的僵尸,對于還活著的僵尸,嘗試向最短路路徑上的下一個點移動一步,如果有堡壘擋住就原地打堡壘。 坑點:當3個僵尸同時攻打某個防御值為2的堡壘,該堡壘消失的同時,3個僵尸都會被扣1滴血。 #include 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 大賽 開發者 機器人
版權聲明:本文內容由網絡用戶投稿,版權歸原作者所有,本站不擁有其著作權,亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容,請聯系我們jiasou666@gmail.com 處理,核實后本網站將在24小時內刪除侵權內容。