0. preface
我爛，只寫(xiě) ABDE 就溜了，所以以下 writeup 只包含 ABDE ，其他等我跑完畢業(yè)流程有空再想。
以下照當(dāng)時(shí)解題順序排序。
pD. LEGO Brick
給定一堆 1x3 的磚塊，要排進(jìn) 3xN 的格子，試問(wèn)有幾種排法？
簡(jiǎn)單的 DP 問(wèn)題，直接計(jì)算 
就好。
就好。嗎？
時(shí)限：1s...
???
看來(lái)正常的 
是沒(méi)救了，開(kāi)始尋找 
的方法。
是沒(méi)救了，開(kāi)始尋找 的方法。既然遞迴式有了，解一下特徵根直接算好了！
修但幾壘，這人考研讀到腦子怪怪的。
想到一般計(jì)算費(fèi)式數(shù)列也會(huì)用矩陣快速冪，那這題也能用對(duì)吧。
寫(xiě)出矩陣版遞迴式，再用快速冪求解，寫(xiě)好邊界條件，簡(jiǎn)單AC。
pA. Buffet
給定一堆食物，各有一份，每個(gè)食物有各自的飽足感和滿足值；
給定一堆盤(pán)子，每個(gè)盤(pán)子上各有一些空位，每個(gè)空位最多放一道食物；
求：至多用完全部盤(pán)子和飽足感不超過(guò)一定值的情況下，最大化滿足值。
很裸的背包問(wèn)題，盤(pán)子數(shù)不重要，所以直接把他們的格子加起來(lái)就好。
其餘用滿足值和格子數(shù)下去做 DP，簽到題。
pE. One Piece
給定一個(gè)連通圖，每個(gè)邊各有權(quán)重，其權(quán)重代表修復(fù)這條邊所需的天數(shù)，每條邊會(huì)同時(shí)修復(fù)；
求：給定一堆查詢，找出從一點(diǎn)到另外一點(diǎn)，至少需要多少天？
第一個(gè)想法：做 Floyd-Warshall 找任兩點(diǎn)最短路徑，再把路徑權(quán)重和改成選最重路徑， 
。
。看了一下N跟時(shí)限...
一秒 &
ok, 看來(lái)要 
才會(huì)過(guò)呢，哈哈。
才會(huì)過(guò)呢，哈哈。想了想，要是把連接兩個(gè)點(diǎn)的環(huán)上拔掉最重邊，再求剩下邊上的最重邊...聽(tīng)起來(lái)有點(diǎn)久。
再想一想，反正可以對(duì)圖先做處理，找出可以最早連通整張圖的邊集合，
那就做個(gè) Kruskal ，時(shí)間複雜度也還在預(yù)算之內(nèi)，
再來(lái)就簡(jiǎn)單了，隨便作 DFS 再用 jumping pointers 紀(jì)錄路徑上最重邊，對(duì)每筆查詢找其點(diǎn)對(duì)的 LCA 中最重邊就好。
對(duì)吧（？
pB. Beautiful Beach
給定海灘上的一排貝殼的美麗值，只能照順序撿，而且每個(gè)新?lián)斓呢悮ひ惹耙粋€(gè)更好看；
求：撿最多貝殼的情況下，字典序最大的一個(gè)可能。
應(yīng)該也算裸的 LIS 問(wèn)題，但平常要找的都是字典序最小的...
那就轉(zhuǎn)成負(fù)數(shù)再反著求 LIS 就好了對(duì)吧 (?
最後再記得把答案轉(zhuǎn)回來(lái)。
不過(guò)其實(shí)我對(duì) LIS 不熟，裡面的東西都是考試的時(shí)候憑印象捏出來(lái)的...
能動(dòng)就好，沒(méi)問(wèn)題。
差不多先這樣，剩下四題就是有生之年了。
達(dá)人
