前往
大廳
主題

112下 NYCU 競程(一)期末部分 writeup

⎝༼ ◕Д ◕ ༽⎠ | 2024-06-16 00:59:41 | 巴幣 2014 | 人氣 177

0. preface

我爛,只寫 ABDE 就溜了,所以以下 writeup 只包含 ABDE ,其他等我跑完畢業流程有空再想。
以下照當時解題順序排序。

pD. LEGO Brick

給定一堆 1x3 的磚塊,要排進 3xN 的格子,試問有幾種排法?

簡單的 DP 問題,直接計算 就好。
嗎?
時限:1s...
???

看來正常的 是沒救了,開始尋找 的方法。
既然遞迴式有了,解一下特徵根直接算好了!
修但幾壘,這人考研讀到腦子怪怪的。

想到一般計算費式數列也會用矩陣快速冪,那這題也能用對吧。
寫出矩陣版遞迴式,再用快速冪求解,寫好邊界條件,簡單AC。


pA. Buffet

給定一堆食物,各有一份,每個食物有各自的飽足感和滿足值;
給定一堆盤子,每個盤子上各有一些空位,每個空位最多放一道食物;
求:至多用完全部盤子和飽足感不超過一定值的情況下,最大化滿足值。

很裸的背包問題,盤子數不重要,所以直接把他們的格子加起來就好。
其餘用滿足值和格子數下去做 DP,簽到題。


pE. One Piece

給定一個連通圖,每個邊各有權重,其權重代表修復這條邊所需的天數,每條邊會同時修復;
求:給定一堆查詢,找出從一點到另外一點,至少需要多少天?

第一個想法:做 Floyd-Warshall 找任兩點最短路徑,再把路徑權重和改成選最重路徑,
看了一下N跟時限...
一秒 &
ok, 看來要 才會過呢,哈哈。

想了想,要是把連接兩個點的環上拔掉最重邊,再求剩下邊上的最重邊...聽起來有點久。
再想一想,反正可以對圖先做處理,找出可以最早連通整張圖的邊集合,
那就做個 Kruskal ,時間複雜度也還在預算之內,
再來就簡單了,隨便作 DFS 再用 jumping pointers 紀錄路徑上最重邊,對每筆查詢找其點對的 LCA 中最重邊就好。
對吧(?


pB. Beautiful Beach

給定海灘上的一排貝殼的美麗值,只能照順序撿,而且每個新撿的貝殼要比前一個更好看;
求:撿最多貝殼的情況下,字典序最大的一個可能。

應該也算裸的 LIS 問題,但平常要找的都是字典序最小的...
那就轉成負數再反著求 LIS 就好了對吧 (?
最後再記得把答案轉回來。
不過其實我對 LIS 不熟,裡面的東西都是考試的時候憑印象捏出來的...
能動就好,沒問題。


差不多先這樣,剩下四題就是有生之年了。

創作回應

小小狼群
所以你為什麼要從 D 開始寫 [e10]
2024-06-16 01:07:26
⎝༼ ◕Д ◕ ༽⎠
我就英文不好,看不懂pA題目[e10]
2024-06-16 01:09:11
娃娃音
強...
2024-06-16 01:07:49
⎝༼ ◕Д ◕ ༽⎠
還在等你罩CP2
2024-06-16 01:09:29

更多創作