2021 師大附中資訊校隊培訓模擬競賽題解

--- title: 2021 師大附中資訊校隊培訓模擬競賽題解 tags: 2021 師大附中資訊校隊培訓 slideOptions: transition: fade --- ### 2021 師大附中資訊校隊培訓模擬競賽題解 [程式碼看我](https://gist.github.com/wiwiho/6e263471274404b2985cf2f40201a547) --- ## pE 校慶紀念品 (Souvenir) 「欸我今天 vir 到一個酷題」 - joy  ---- 白話文：對於 $1 \leq i \leq K$ 你想知道每個物品都只能選 0 個或 i 個時的最大總價值 ---- ### subtask 3 $K=1$ 只要算 $i=1$ 的狀況等同 0/1 背包 ---- ### subtask 4 $w_i=1$ 當要算 $k$ 個人的狀況時送給一個人的紀念品不能超過 $N/k$ 個直接選最受歡迎的 $N/k$ 個就好 ---- ### subtask 5 選一組紀念品，總價錢是 $w$，總受歡迎度是 $v$ 送給 $k$ 個人，總價錢是 $kw$、總受歡迎度是 $kv$ $kw \leq M \implies w \leq M/k$ 找到在只有 $M/k$ 元時，每種紀念品最多買一個的最大受歡迎度乘上 $k$ 後就是有 $k$ 個人的答案  做一次 0/1 背包就能算完，時間 $O(NM+K)$  --- ## pA 圓錐 (Cone) 題源：台大 ADA 作業圓角錐到底有角還是沒角？  ---- ### subtask 2 $N \leq 10$ 用遞迴暴搜要先偷哪些圓錐 $O(N!)$ ---- ### subtask 3 $A_i$ 是質數，且每種數字都會出現恰 2 或 3 次因為不同的數都會互質，所以能一起偷的只有同一個數而已而且數量一定是 2 或 3，代表只能全部一起偷答案是固定的，問題只在判斷有沒有解無解：3 2 3 2 3 有解：3 2 2 3 3  把同一種數字看成一對括號掃描線 $O(n)$  ---- ### subtask 4,5 $dp[i][j]=$ 把 $[i,j]$ 偷光後的最大滿足度偷法有一些 case 1. $[i,k]$、$[k+1,j]$ 分開偷 2. 先偷 $i$ 和 $j$，再偷 $[i+1][j-1]$ 3. 先偷 $i$、$j$ 和 $k$（$i < k < j$），再偷 $[i+1,k-1]$ 和 $[k+1,j-1]$  ---- 如果每次 $\gcd$ 都重算會花 $O(n^3)$ 的時間預處理  --- ## pD 足球場 (Soccer) 「我覺得在校內賽放計幾不太健康」 - joy  ---- 怎麼判斷四個點能不能構成矩形？四個角要是直角外積判斷 ---- ## subtask 2 $N \leq 80$ 枚舉四個點判斷是不是矩形 $O(N^4)$ ---- ## subtask 3 $N \leq 200$ 枚舉其中三個點可以發現到第四個點的位置是唯一的判斷是否存在那個點就好 $O(N^3 \log N)$ ---- ## subtask 4 一直把注意力放在頂點上好像有點麻煩改把注意力放到對角線呢？對角線有什麼性質？ ---- ![](https://i.imgur.com/0WhTejK.png) ---- 長方形的兩條對角線 - 相交在它們的中點 - 長度一樣對於兩兩點對的連線如果兩條線滿足長度一樣、相交在中點這兩條線就可以當矩形的對角線 ---- 只要是中點在同一個位置且長度一樣的兩個點的連線就能當同一個矩形的對角線把每一條兩個點的連線按照中點位置和長度分類同一類的可以一起當對角線 ---- 有一類有 $c$ 條線那這一類可以做出 $\frac{c(c-1)}{2}$ 個矩形  避免浮點數：中點座標可以不用除以 2 長度可以不用開根號 $O(N^2 \log N)$ --- ## 拿破崙改 (Napoleon) 題源：[CF 103186B](https://codeforces.com/gym/103186/problem/B) 「我是秘書我是秘書我是秘書」 - ZCK  ---- ### subtask 3 $C=1$ 如果已經選好了哪一組要選 $c$ 可以先假裝其他都要選 $a$ 如果有一組要改選 $b$ 那麼總和會改變 $b-a$ 取最大的 $B$ 個 $b_i-a_i$  ---- 可以直接把每一組按照 $b_i-a_i$ 大到小排序當要選 $c_i$ 的那組編號 $\leq B$ 時選到 $b_i$ 的就是第 1 到 $B+1$ 組除了他否則就是第 1 到 B 組 $O(N)$ ---- ### subtask 4 $N \leq 500$ $dp[i][j][k]=$ 前 $i$ 組中，有 $j$ 個選 $a$、$k$ 個選 $b$ 的最大總和選 $c$ 的數量是 $i-j-k$ $O(N^3)$ ---- ### subtask 5 $N \leq 5000$ 把前兩個子題的想法混合先照 $b_i-a_i$ 大到小排序 $dp[i][j]=$ 前 $i$ 組裡選 $c$ 的恰有 $j$ 個時的最大總和 ---- 如果第 $i$ 個要選 $c$ 那就是 $dp[i-1][j-1]+c_i$ 不然，$i$ 如果是扣掉選 $c$ 的人之後的前 $B$ 個就要選 $b_i$，否則選 $a_i$ 條件：$i-j \leq B$  $O(N^2)$ ---- ### subtask 6 可以很直覺地猜到這應該可以 Greedy ---- ### 一種 Greedy 的方法在做到第 $i$ 組的時候如果 $i \leq A$，就前 $i$ 組全部選 $a$ 如果 $i \leq A+B$，找前 $i$ 組選恰 $A$ 個 $a$ 的最大總和否則，我想知道前 $i$ 組選恰 $A$ 個 $a$、恰 $B$ 個 $b$ 的最大總和 ---- 前兩種很好算重點是第三種如果第 $i$ 組要選 $c_i$ 那麼顯然我們前 $i-1$ 組就要有恰 $A$ 個 $a$、恰 $B$ 個 $b$ 可以直接計算 ---- 假設第 $i$ 組想要選 $a$ 那前 $i-1$ 組就要有恰 $A-1$ 個 $a$、恰 $B$ 個 $b$ 怎麼從「前 $i-1$ 組有恰 $A$ 個 $a$、恰 $B$ 個 $b$」推出它？ ---- 亂想：把某個本來是選 $a$ 的換成選 $c$ 或者把某個本來是選 $a$ 的換成選 $b$、某個本來是選 $b$ 的換成選 $c$ ---- 為什麼這樣是對的？把「前 $i-1$ 組有恰 $A$ 個 $a$、恰 $B$ 個 $b$」的最好選法和有恰 $A-1$ 個 $a$ 的最好選法視為一個只包含 $a,b,c$ 的字串 $S_1$ 跟 $S_2$ 想像一個三個節點的圖，節點分別對應到 $a,b,c$ 如果某個位置在 $S_1$ 上和 $S_2$ 上分別是 $t_1,t_2$ 就連一條邊 $t_1 \to t_2$ ---- 邊的意思就是我們把那個位置換掉權重是換掉後總和會改變多少這個圖上如果有環的話那這個環正著走和倒著走一圈（倒著走權重要變負的）要嘛都是 0，要嘛有一個是正的 ---- 如果正著走是正的就代表可以把 $S_1$ 上的那些邊對到的位置換掉每種花色的數量不會改變，而總和會變大和他是最好選法矛盾反著走同理只是變成把 $S_2$ 的換掉如果都是 0，那做了根本不會變好可以把那些邊對到的位置 $S_2$ 變得和 $S_1$ 一樣它還會是最佳選法 ---- 得出這張圖不會有環而且 $a$ 的出度要比入度多 1 $c$ 的入度要比出度少 1 $b$ 的出入度相等滿足這樣的圖只有 - 只有一條 $a \to b$ - 只有一條 $a \to b$ 和 $b \to c$ ---- 所以只考慮這兩種 case 會是好的用 set 維護我想找一個特定花色改成另一個，最好的選擇是誰 $O(n \log n)$ 也有別種 Greedy 法但應該差不多都是這樣換來換去的 --- ## 長頸鹿園 (Giraffe) 有長頸鹿那有沒有短頸鹿  ---- 白話文：把 $N$ 個節點依序加到樹上每次加完後求現在樹上有幾條直徑 ---- ### subtask 2 $N \leq 500$ 每次加完後，花 $O(N^2)$ 的時間看過樹上所有路徑的長度 $O(N^3)$ ---- ### subtask 3 這棵樹是星狀圖把 1 拆掉後會變成一些鏈直徑肯定是兩條鏈接起來（或者一條，如果只有一條的話）維護長度最長的那些鏈（如果長度最長只有一條，還要找次長的）然後算一下 $O(N)$ ---- ### subtask 4 $N \leq 5000$ 有一個性質是所有直徑都會經過樹圓心然後我們看一下怎麼用樹圓心找直徑數量 ---- 若樹直徑的邊數是 $d$ 定義「樹半徑」是 $\lfloor \frac{d}{2} \rfloor$ ---- 當樹直徑上有奇數個點的時候圓心只有一個樹直徑會是從它的某個子樹裡的葉節點到另一個子樹裡的葉節點而且那兩個葉節點的深度是樹半徑數有幾對葉節點，滿足它們在不同子樹且深度都是樹半徑  ---- ![](https://i.imgur.com/Q5l0iij.png) ---- 當樹直徑上有偶數個點圓心會有兩個樹直徑會是跨越它們之間那條邊以兩側某個葉節點為端點的路徑這兩個葉節點到中間那條邊的距離都是樹半徑數兩側有多少節點在那一側的子樹深度是樹半徑然後乘起來  ---- ![](https://i.imgur.com/RAMTvmS.png) ---- ### subtask 5 想辦法動態維護那些東西 ---- 首先要會動態維護圓心如果新加的點到比較近的圓心的距離超過樹半徑那樹直徑就會變長而且樹圓心會往它的方向移動 ---- 如果本來只有一個圓心，那舊圓心還是圓心然後往新加的點的方向走一步的那個會成為第二個圓心如果本來有兩個圓心那只有比較靠近新加的點的那個會繼續是圓心 ---- 會維護圓心了！我們還要維護那些子樹裡有幾個深度是樹半徑的點的資訊可以從本來圓心的資訊得出新圓心的資訊 $O(n \log n)$ ---- ![](https://i.imgur.com/7NXKOv7.png) ---- ![](https://i.imgur.com/p4RfQxc.png)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.