暑期訓練─題解

Week 1─Virtual Judge

tags: 搜尋 排序 貪心

	題目	題解	uDebug
A	Flip Sort	排序 基本題 bubble sort就夠用	Uva 10327
B	Age Sort	排序 基本題 知道矩陣index可以達到快速排序即可	Uva 11462
C	Conformity	Hash 基本題 暴力比對組合，或是hash都可行	Uva 11286
D	Guessing Game	模擬題 基本題 看最後猜的是不是在區間內	Uva 10530
E	Ancient Cipher	腦筋急轉彎 基本題 動腦一下，暴力或著統計字母數量排序	Uva 1339
F	Bridge Hands	模擬題 基本題 會寫程式就能過關	Uva 555
G	Vito's Family	腦筋急轉彎 基本題 考到爛掉的題目，中位數算距離	Uva 10041
H	Shoemaker's Problem	貪心法 詳解	Uva 10026
I	The Bus Driver Problem	貪心法 基本題 想想高斯怎麼算1加到100的就能解了	Uva 11389
J	Watering Grass	貪心法 區間覆蓋 詳解	Uva 10382
K	Ultra-QuickSort	排序 基本題 叫做Quicksort但要用Merge sort的題目，用 BIT 也行	Uva 10810

有些題目我覺得不用詳細寫題解，所以就簡單文字敘述一下
如果同學想寫或想補充更多都歡迎編輯~mathlin

---

Week 2─Virtual Judge

tags: 資料結構 STL

	題目	題解	uDebug
A	Parentheses Balance	stack 基本題 左括弧→stack 右括弧→pop比對 注意本題測資包括空白行	Uva 673
B	Matrix Chain Multiplication	stack map 基本題 字母 $\stackrel{map}{\to }$ 行、列 遇字母 $\stackrel{push}{\to }$stack 右括號 $\stackrel{pop}{\to }$取出2個 檢查+運算 輸出即可	Uva 442
C	Printer Queue	queue priority queue 基本題 pair (1)索引 (2)優先程度 資訊 $\stackrel{push}{\to }$(1)p_q (2)queue if p_q.top()==自己 ans+/pop else pop+push	Uva 12100
D	Uncompress	link-list deque vector link-list搜尋字詞存在與否，不存在則push_front進去，遇到數字就找位置對應的字詞，刪除再push進去	Uva 245
E	Argus	priority queue 基本題 typedef 存頻率、目前、名字 cmp 比較目前，相同則名字小在前 每次從p_q取出，now再加頻率然後輸出，再丟回去p_q	Uva 1203
F	I Can Guess the Data Structure!	stack queue priority queue 基本題 照著定義3個結構 $1\stackrel{push}{\to }STL$ $2\to check\stackrel{pop}{\to }STL$ 看哪幾個符合條件輸出即可 注意STL有可能為空	Uva 11995
G	Ubiquitous Religions	disjoint-set 基本題 直接刻一個disjoint-set，如果在同一個集合表示有同一個信仰，做完union後從頭掃到尾，如果等於自己就+1，這題就解了(算總共有多少個集合)	Uva 10583
H	Almost Union-Find	disjoint-set set vector 運用vector的push和clear，達到union的效果，再一個vector儲存root $1\to \text{(all)root + vector push \& pop}$ $2\to \text{(one)root, vector push \& pop}$ $3\to \text{visit all and count}$ 2的時候主要是利用vector，先找其root，再從root的vector中把自己刪除，加到q的root內；1把小的併入大的內，特別注意小的所有root都要改變；3直接visit該數字的root即可	Uva 11987
I	Islands	disjoint-set Kruskal 每格欄位紀錄其高度、行、列，再存入set或其它STL 按照高度由高到低排序，一一檢索後，上下左右若也高於指定高度，就合併(此時區塊數-1) 主要因為測資大，加上最後的海拔高度是嚴格遞增 disjoint-set只能合併不能分割，因此由高海拔(露出的陸地少→多)就能運用disjoint-set合併的速度，若要用disjoint-set，此題必須逆向思考，聽說有Kruskal的解法，歡迎同學補充！	Uva 1665
J	Borrowers	模擬題 map set 個人用set，先定義pair為title, author，再直接利用cmp按author再按title排序 定義3個set(3個狀態) 1. 在圖書館架子上(可借閱) 2. 被借走 3. 已歸還尚未上架 直接模擬從相對印的set中移除，移入即可，注意遇到SHELVE時，先上架再確認自己是不是第一本書 若是要輸出"first"，不是則after輸出他的前一本書	Uva 230
K	Database	map 暴力會TLE, 利用map檢索string的話速度會太慢，因此將string編號為數字比較 定義map<string, int>，按照目前map大小對應string 再定義map<pair<int,int>,int> 簡單說，先把尚未出現的string編號，再將兩個string對應到的int編號，此時搜尋map中有沒有出現過一樣的數字，出現就print行列，沒出現就print"YES"	Uva 1592

最近比較忙，比較沒時間寫詳解

I,K知道怎麼解不過還沒寫，這兩題應該是這串題目集比較難(？)的，還請大神們協助寫解答給系隊的朋友們

較難的題目可以另寫一個筆記，從這裡link到您撰寫的筆記那邊，如
範例格式 (不一定要依此格式，您可以將此筆記複製貼上修改會比較快)mathlin

---

Week 3─Virtual Judge

tags: 圖論 狀態搜尋 拓樸排序

	題目	題解	uDebug
A	Bicoloring	基本題 DFS BFS 直接DFS，塗色可以利用visit陣列，極基本題XD	Uva 10004
B	The Party, Part I	基本題 BFS 這題是看和源頭跳舞的間接程度，因此在乎的是此人是「第幾層」，故直接BFS尋訪即可，不過此題要特別注意格式，相鄰測資必須間隔一行(空白)	Uva 10959
C	Oil Deposits	基本題 DFS BFS 看油有幾灘，尋訪時注意方向包含斜邊(8個方向)，能執行幾次BFS／DFS就代表有幾團油漬了	Uva 572
D	Lotto	基本題 DFS 給一串序列，輸出任選其中六個的結果並且按照字典序輸出，此題可直接用遞迴，DFS也可以，紀錄長度跟cur，每次dfs(cur+1, len+1)，當len等於6時輸出答案	Uva 441
E	Risk	基本題 BFS Floyd-Warshall 此題共有20個城鎮，保證相連，給指定起點、終點，輸出最短距離，因為測資小對效率沒有嚴格限制，所以可以直接執行好幾次BFS處理，如果測資不友善會需要使用到Floyd-Warshall ps. 因為測資極小，單純BFS因此判定為基本題	Uva 567
F	How Many Dependencies?	基本題 DFS BFS 算出最多依賴的工作，所以直接DFS其實就可以了，不過其實disjoint-set也能解這題，要特別注意輸出的是 依賴最多任務的最小編號	Uva 10926
G	Longest path in a tree	DFS BFS 這題我的想法是，先隨便對一個節點做BFS，算出各節點之於該起點的距離，再從中以距離該起點最長或最短的節點再做一次BFS，其中不斷更新ans的最大值輸出即可	SPOJ PT07Z
H	Fill	priority queue BFS 此題關鍵在建圖，將水杯當前狀態(a,b,c)當作一個節點，每次尋訪時，可以分成a->b, a->c…等六種倒法，並且紀錄每個節點所需的倒水量，因為該題要求的是 最小倒水量而非最小次數，尋訪時可利用priority_queue從最小倒水量的節點開始尋訪(才能保證是最小倒水量)	Uva 10603
I	Ordering Tasks	基本題 拓樸排序 DFS stack 裸題，只要輸出任一種符合的順序即可，建圖後做DFS，到了沒路能尋訪的節點時，直接Push節點進stack內，特別注意是沒有連通的tack自成一個節點，其擺放位置不影響	Uva 10305
J	Guess	拓樸排序 DFS stack 原本給定序列，依照其數值的區間和建造一個sign matrix，接著題目反過來，給定sign matrix要輸入任一個符合條件的序列，既然sign matrix給定的都是區間和的關係，就直接按照每個區間和的關係建圖，例如若1,4位置為+，則代表 $sum[4]-sum[0]>0\to sum[4]>sum[0]$，遇到0時則利用disjoint-set處理連通，釐清區間和彼此間的大小關係順序後，直接從5依序給值，就能符合題目要求的關係了	Uva 1423
K	John's trip	歐拉迴路 DFS 此題已保證節點間連通，並且為歐拉迴路而非歐拉路徑，所以如果要確定歐拉迴路存在，必須檢查: (1) 圖是連通的 (2) 各節點入邊等於出邊 (3) 對於每個節點，出邊+入邊的數量為偶數 不符合上述條件就不可能有歐拉迴路，接著直接DFS + stack輸出即可，不過要注意這題若有多種路徑可能，輸出字典序最小的路徑 (ps. 既然為歐拉迴路，代表從哪個地方當起點都可以，因此可直接從編號最小的路開始走)	Uva 302
L	Catenyms	歐拉路徑 歐拉迴路 DFS 之前NCPC決賽有碰過幾乎一樣的題目，關鍵在於建圖，出現過的字母(頭尾)，當作節點，而單字則當作邊，利用map紀錄每個單字出現的次數，接著最大的麻煩就是歐拉路要存在一定圖要連通，因此用disjoint-set和出現過幾個字母去檢查有沒有連通，第二個要檢查的是入邊等於出邊，若為歐拉路徑，則起點與終點，入邊+出邊為奇數，接著就是決定起點，如果是歐拉路徑則在前面檢查時，就要先紀錄 出邊大於入邊的節點，從此處開始尋訪，若為歐拉迴路則代表從每個節點出發都可以，因此從Ascii最小的字母尋訪接著輸出即可(題目要求輸出字典序最小的狀況)	Uva 10441

---

Week 4─Virtual Judge

tags: 動態規劃

$\boxed{\text{Practice END}}$

Date: 8/2 ~ 8/9
這段時間稍忙，只有寫基本題四題(PA,B,C,D)
還請協助補充

---

Week 5─Virtual Judge

tags: MST

	題目	題解	uDebug
A	Freckles	基本題 Kruscal Prim TBD	Uva 10034
B	Bus Problem	基本題 Kruscal Prim TBD	Uvl 7001
C	Oreon	基本題 Kruscal Prim TBD	Uva 1208
D	Arctic Network	變化題 Kruscal Prim 小變化而已，先好好思考怎麼利用衛星，儘可能縮短距離(待VJ結束後補充)	Uva 10369
E	Frogger	經典題 Kruscal 最小瓶頸路 disjoint-set 善用Kruscal的原理(hint: weight排序、disjoint union的涵義)，你也可以Prim再DFS	Uva 534
F	Airports	變化題 Kruscal Prim 有很多種想法，每次可選擇蓋機場或蓋路…也有設立一個超級起點的版本，想像看蓋機場的意義相當於什麼?	Uva 11733
G	Slim Span	變化題 Kruscal 可直接暴力法輾壓，暫時想不到較好的方法	Uva 1395

Source: 2020_暑訓─(@tcchiang)

HackMD Error: 403 error