題目： UVa - 1203 - Argus 題目說明給一些 Register 的編號及週期，根據題目要求前 K 個被執行的 Register。若有執行相同的 Register 則編號小的優先執行。 解題思路建造一個 Structure 並 Overload operator< 之後使用 Priority_queue 實作即可，每次 Register 執行後將時間加上週期後重新推入。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream>#include <queue>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();struct reg{ int num; int pe ...

題目： UVa - 12207 - That is Your Queue 題目說明給兩個數字，P、C，P 代表列表中的序號個數，從 1 開始，一開始的排序為升冪排序，例如 P = 3 則列表為 {1, 2, 3}。C 代表接下來有幾行指令，若指令為 N 表示輸出列表最前面的序號並且將此序號移到列表的尾端，若為 E 加上一個序號代表將該序號代表將該序號移到列表的前端。 解題思路使用 List 模擬操作並且使用 Unordered_map 提升搜尋速度即可。需要注意的是，若 C 的值小於 P 的值則我們一開始只需要推入 C 個序號即可，因為後面的序號除非被往前移動，否則絕對不會使用到。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>#include <unordered_map>#include <list>using namespace std;static auto __ = [ ...

題目： UVa - 11988 - Broken Keyboard (a.k.a. Beiju Text) 題目說明給 String，模擬鍵盤輸入的情況，'[' 為 home 鍵，']' 為 end 鍵，求模擬輸出後的字串為何。 解題思路使用 List 儲存結果，使用 iterator 紀錄目前游標的位置，遍歷 String，當碰到 '[' 將 it 更新為 begin()，碰到 ']' 將 it 更新為 end()，其餘情況則使用 insert() 將字元放入即可。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#include <list>#include <string>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(false); ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-10-19截止時間：2020-10-25 題目說明這次的作業是 UVa 中的 6 題題目。三題與 Map 相關，三題與 Set 相關。 與 Map 相關 Uva 10226 - Hardwood Species：UVa - 10226 解題紀錄 UVa 10282 - Babelfish：UVa - 10282 解題紀錄 UVa 11286 – Conformity：UVa - 11286 解題紀錄 與 Set 相關 UVa - 978 - Lemmings Battle!：UVa - 978 解題紀錄 UVa - 11136 - Hoax or what：UVa - 11136 解題紀錄 UVa - 11572 - Unique Snowflakes：UVa - 11572 解題紀錄

題目： UVa - 11572 - Unique Snowflakes 題目說明給一串數字代表雪花的編號，編號不同的雪花代表形狀不同，求一次最多能裝出多少個不同的雪花，只能按照順序裝，不可跳過任意的雪花。 Input： 測資起始於一個整數 n，代表有 n 組資料，每組資料起始於一個整數 N，代表有 N 片雪花，接下來 N 行每行會有一個數字，代表雪花的編號。 Output： 輸出能最多能裝出的雪花的個數。 解題思路題目其實就是在求一個陣列中最長的不重複子陣列，依此想法去解題即可。r 為當前讀取到的元素個數。 解法一：使用 DP 及 Sliding window 的概念，使用 Unordered_map 儲存每個數字最後出現的 index，每次讀取一個元素時，先判斷是否已經存在於 map，若存在則 Window 的 l 需更新為 l、及該 index + 1 兩者的較大者，此時 Window 的長度為 r - l + 1，接著更新該元素在 map 中的 index，並且更新 ret。 解法二：使用 Unordered_set 及 Vector 依序儲存讀取到的元素，使用一個整數 l 從 ...

題目： UVa - 11136 - Hoax or what 題目說明超市進行促銷，把帳單放入一個箱子中，每天會放入一些帳單，接著取出金額最大及最小的帳單，並且支付 最大 - 最小 的金額，求 n 天後總共需要支付多少錢。 Input： 每組測資起始於一個整數 n，代表接下來有 n 行資料代表放入的帳單，若 n 為 0 代表結束，每行資料起始於一個整數 num，表示今天有 num 筆帳單要放入，中間以空格隔開。 Output： 輸出每組測資經過 n 天後總共需要支付多少錢。 解題思路使用 Multiset 儲存帳單，接著每天從頭跟尾取出資料即可。使用 Multiset 的原因是可能會有兩張相同金額的帳單。需要注意的是因為測資的大小，所以結果使用 long long 儲存。 參考解法123456789101112131415161718192021222324252627282930313233#include <iostream>#include <set>using namespace std;// fast IOstatic auto __ = []()&# ...

題目： UVa - 978 - Lemmings Battle! 題目說明有兩個隊伍需要戰鬥，每個隊伍裡面的戰士都有一個戰力，每次從隊伍裡面挑選 B 個人 ( 若任一隊伍不足 B 個人則以較少隊伍的人數當作 B ) 出來依序戰鬥，若是被分配到的兩者戰力相等則同歸於盡，否則戰力較高的戰士減去戰力較低的戰士的戰力並回到隊伍中。 Input： 測資起始於一個整數 n，代表接下來會有 n 組資料。每組資料的第一行為三個整數，分別代表 B、SG、SB，SG 為綠隊的人數，SB 為藍隊的人數，三者以空格隔開，接下來 SG 行為綠隊戰士的戰力，SB 行為藍隊戰士的戰力。 Output： 若兩支隊伍最後都沒有戰士了則輸出 "green and blue died"，否則輸出勝利的隊伍，並且列出勝利隊伍剩餘戰士的戰力，並由大至小排序。兩組輸出結果中間須以空行隔開。 解題思路使用兩個 Priority_queue 分別儲存兩隊戰士的戰力，並且每次 pop() 對應的人數戰鬥，使用 Vector 暫存戰鬥結果，最後依照戰鬥的結果將戰士重新 push() 回去即可。 參考解法1234567 ...

題目： UVa - 11286 - Conformity 題目說明每組測資會給一個整數，代表接下來會有幾組課程代號，每組課程代號會有五個代號，代表某個學生選擇的五堂課，求最多人選擇的組合。 Input： 每組測資起始於一個整數 n，若 n 為 0 代表結束。否則接下來 n 行中，每行會有 5 個 3 位數的整數代表課程代號，中間以空格隔開。每組測資中間沒有空行，整數與課程代號中也沒有空行。 Output： 求最多人選擇的那組課程代號的人數，若同時有超過一組最多人選擇的話則將人數相加，例如 Sample 的第二組資料，有三組不同的組合則答案為 1 + 1 + 1 = 3。 解題思路想法： 整體思路為，將每個人選擇的課程代號以小到大排序，即可避免順序不同但組合相同的問題，接著使用 Unordered_map 記數，最後遍歷找出答案即可。 作法： 先讀取 n，接下來每一行使用 cin 讀取課程代號，並先存放到一個 Vector，讀取 5 個後先對 Vector 進行排序，最後把它存放到一個 String 裡面當作 key，接著將 key 對應的 val 加一即可。讀取完後遍歷 map，使用 ...

題目： UVa - 10282 - Babelfish 題目說明給動物名稱及對應的叫聲，依據叫聲輸出對應的動物名稱。 Input： 測資分為兩部分，前面的部分每一行會有兩個字串，分別代表動物名稱及叫聲，中間以空格隔開。後面的部分為動物的叫聲，兩部分中間以空行隔開。 Output： 根據測資前面的部分輸出叫聲對應的動物，若是沒有在前面出現過則輸出 “eh”。 解題思路使用 Unordered_map 建立叫聲及動物名稱的映射即可。使用 getline() 以行為單位讀取資料，讀取後先判斷，若為空代表前半部分讀取完畢，否則使用 String 中的 find() 找到空格的 index，將字串分為兩部分，以叫聲為 key，名稱為 val，建立映射即可，當前半部分讀取完後開始讀取叫聲，先判斷這種叫聲是否出現過，若出現過直接輸出名稱即可，否則輸出 “eh”。 參考解法12345678910111213141516171819202122232425262728293031323334#include <iostream>#include <string>#include ...

題目： UVa - 10226 - Hardwood Species 題目說明測資開始於一個整數，代表接下來會有幾組資料，一開始的整數後及每組資料間都有空行隔開，可見 Sample I/O。 Input： 每組資料會有許多行字串，每個字串代表一種樹木，出現的次數即為樹木的數量。直到讀取到空的字串為止。 Output： 輸出每種樹木的名字及所佔的百分比 ( 順序為樹木名字的升冪排序，百分比輸出到小數點後四位 )，每組輸出的資料中間需有空行隔開。 解題思路先讀取最前面的整數，由於接下來要使用 getline()，所以先呼叫 cin.ingore() 將輸入流中的 '\n' 清除，再呼叫一次 getline() 讀取整數與第一組資料間的空行，接著就可以開始讀取資料，使用 map 紀錄一組資料中的各個樹木種類出現的次數，同時需要紀錄樹木的總數，最後計算百分比並輸出即可。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#incl ...