---
tags: 全國模擬賽 2019
title: 108 學年度 全國資訊學科能力競賽模擬賽 題目講解
---

# 108 學年度 全國資訊學科能力模擬賽 題目講解

- [題本載點](https://brian.su/r/pre-nhspc2019-problems)

## pA. 要回家的銷售員 (Salesman)
- Task provider: yp155136
- Task setter: baluteshih

### Subtask 1
在 $2\times 2$ 的方格內，唯一有可能相異的兩條路徑只有下圖兩條
所以我們只需要判斷該兩條路徑是否全然相同即可。

### Subtask 2
對於 $N=2$ 的方格，若存在兩條相異路徑經過的序列相同，則肯定是存在兩分歧點 $L,R$，使得 $a_{0,L+1}=a_{1,L},a_{0,L+2}=a_{1,L+1},\cdots,a_{0,R-1}=a_{1,R-2},a_{0,R}=a_{1,R-1}$
故我們只需要枚舉所有 $L,R$ 就可以驗證是否存在滿足的兩條相異路徑，同時因為 $M\le 30$ 不需要太擔心時限上的問題。

### Subtask 3
我們可以將兩個人走路的「狀態」都對應到一張圖上的某個點，也就是每個點都代表著三個參數 $(a,b,d)$ 意義為「兩人都各走了 $d$ 步，且第一個人現在位於第 $a$ 行、第二個人現在位於第 $b$ 行」。
只要把合法的走法建邊，就等價詢問 $(1,1,0)$ 是否可以抵達 $(N,N,N+M-2)$，於是我們就有了 $O(NM(N+M))$ 的做法。

因為範圍夠小，如果不小心寫爛東西應該也會過。
~~然後如果常數夠小，用這個方法也能通過本題。~~

### Subtask 4
觀察到對於任意兩條相異合法路徑，肯定存在兩條路徑分岔開來的點，若只注意該點為左上角形成的 $2\times 2$ 方格的話，可以發現該 $2\times 2$方格也會是有解的一組輸入，即 $a_{i+1,j}=a_{i,j+1}$。

同時，若我們能在方格內找到任意一個 $a_{i+1,j}=a_{i,j+1}$，那麼只需要讓兩人從 $(1,1)$ 走到 $(i,j)$，兩人分岔走到 $(i+1,j+1)$，再從 $(i+1,j+1)$ 走到 $(N,M)$ 即可。

故本題只需要花費 $O(NM)$ 的時間尋找到是否存在 $a_{i+1,j}=a_{i,j+1}$ 即可以找出答案。

## pB. 無環圖 (Acyclic_graph)
- Task provider: briansu
- Task setter: baluteshih

### Subtask 1
可以發現，每個點連的邊不超過兩條所形成的圖，肯定是由一堆樹和一堆單獨的環所構成。
我們不需要理會樹，又對於每一個環，我們只需要移除他身上權重最小的邊即可使其無環，所以我們可以遍歷每一個連通塊，只要發現他身上的點數恰等於邊數，就把這個連通塊的最小邊權加進答案內，最後輸出。

### Subtask 2
利用貪心的想法，把邊由小到大嘗試移除，如果連通塊數量變多，那麼我們就不移除該條邊，重複執行以上動作直到每條邊都被枚舉過一次為止。

每次移除一條邊我們都得花費 $O(N+M)$ 的時間計算連通塊數量，故總複雜度為 $O(M(N+M))$。

### Subtask 3
既然所有邊權都是 $1$，那麼我們只需要計算每個連通塊邊數 $E$ 和點數 $V$，因為我們希望盡量多的邊留下來，也就是留下一棵生成樹即可，所以此時只要把答案加上 $E-V+1$ 就好了。

### Subtask 4
可以發現原題等價 所有邊權總和 扣去 最大生成森林的權重和，於是我們可以直接採用Kruskal算法幫助我們得出最大生成森林的權重和。
時間複雜度 $O(M\log N + N)$。

使用Prim算法的話也能通過本題，但需要確保每個點都有被遍歷過。

## pC. 序列構造 (Sequence)
- Task provider: leo900807
- Task setter: leo900807

### Subtask 1
因為 $N$ 只有 $16$ 且序列元素只有 $0$ 跟 $1$ ，所以只要 $01$ 枚舉序列元素，每次 $O(Q)$ 檢查序列是否符合詢問，只要用前綴和就可以每次 $O(1)$ 查詢，總複雜度 $O(2^NNQ)$ 。

### Subtask 2
這個 Subtask 詢問結果僅有 $1$ ，我們可以將這題對應到經典的「射線段問題」，將每個詢問區間映射到覆蓋區間 $[l,r]$ 的線段，即可用 Greedy 解，總複雜度 $O(N)$ 。

### Subtask 3
同 Subtask 2 ，但需要維護詢問為 $0$ 的區間，可以 $O(N+Q)$ 預處理把非 $0$ 區間的位置獨立出來，每次要射線段時就射該位置，最後再 $O(N)$ Greedy 求解，總複雜度 $O(N+Q)$ 。

### Subtask 4 & 5
做 $30$ 次 **Subtask 3** ，若在處理的過程中多帶一個 $\log N$ ，則只會拿到 Subtask 4 的分數，總複雜度 $O((N+Q)\log C)$ 。

## pD. 土地徵收 (Land)
- Task provider: baluteshih
- Task setter: baluteshih

### Subtask 1
可以透過問 $120$ 種 $1\times 60$ 的矩形來獲得上下左右界，詢問僅 $120$ 次。

### Subtask 2
考慮二分搜。
觀察發現，詢問所有的合法矩形 $[(0,0),(1,t)]$，可以發現當 $t>b$ 時，回傳的面積肯定為正；否則為 $0$。
故有此單調性後，我們可以詢問 $⌈\log_2 10^9⌉=30$ 次來二分搜出 $b$ 的位置，同理 $d$ 也可以完成。
詢問共 $60$ 次。

### Subtask 3

#### $120$ 次
有了Subtask 2的做法，可以改成詢問矩形 $[(0,0),(t,10^9)]$ 來獲得 $a$ 的位置，同樣再二分搜三次來獲得 $b,c,d$ 的位置。

#### $91$ 次
當二分搜三次得到 $a,b,c$ 後，詢問矩形 $[(0,0),(10^9,10^9)]$ 將可以獲得總面積 $A$ ，此時顯然高為 $\frac{A}{c-a}$，於是有 $d=b+\frac{A}{c-a}$。

#### $62$ 次
當二分搜兩次得到 $a,b$ 後，詢問矩形 $[(a,0),(a+1,10^9)]$、$[(0,b),(10^9,b+1)]$ 各一次將可以獲得長及寬，此時可以直接得出 $c,d$。

#### $60$ 次
在二分搜 $a,b$ 的過程中，可以使用一點技巧使得兩次二分搜各存在一次二分搜的詢問是詢問矩形 $[(0,0),(a+1,10^9)]$、 $[(0,0),(10^9,b+1)]$，該兩次將可以獲得長及寬，此時可以直接得出 $c,d$。

## pE. AI-777 賺多少 (AI)
- Task provider: briansu
- Task setter: baluteshih

### Subtask 1
等價「最大連續和」問題。
我們可以做前綴和 $s_i=s_{i-1}+d_i,s_0=0$，對於每個 $s_i$，都去查詢 $s_0\sim s_{i-1}$ 的前綴最小值 $m_{i-1}$，並求出 $s_i-m_i$ 的最大值即為答案，而我們可以簡單得出 $m_i=\min(m_{i-1},s_{i}),m_0=0$。

故整個演算法只需要 $O(N)$ 的時間。

### Subtask 2
類似Subtask 1的想法，我們可以反著跑類似地求出後綴和 $ss_i$、後綴最小值 $ms_i$。
由於 $K=1$，可以窮舉要更改哪個位置 $i$，對所有 $s_{i-1}-m_{i-2}+x_1+ss_{i+1}-ms_{i+2}$ 取最大值即為更改一個的答案。
演算法同樣只需要 $O(N)$，最後要記得和 $K=0$ 的答案取最大值輸出。

### Subtask 3
考慮DP，令 $dp[i][j]$ 代表前綴 $1\sim i$ 中 $K=j$ 的答案，則有 $dp[i][j]=\max\{dp[i-1][j]+d_i,dp[i-1][j-1]+x_1,0\}$

時間複雜度 $O(NK)$。

### Subtask 4
如果改了 $K$ 個位置，那麼取 $x_i$ 中前 $K$ 大的肯定最好，所以實際上我們只需要對 $x_i$ 由大到小排序，將轉移式改為 $dp[i][j]=\max\{dp[i-1][j]+d_i,dp[i-1][j-1]+x_j,0\}$ 即可答對本題。

$O(NK)$。

## pF. 直升機載寶 (Helicopter)
- Task provider: yp155136
- Task setter: yp155136

### subtasl 1

可以發現，這是一個 greedy 的 subtask題目，以下提供一個作法。

把寶可夢按照體重排序，有大到小考慮。

每當考慮到寶可夢 $X$ 時，每次盡量讓體重最重，但是可以跟 $X$ 一起放在直升機的寶。

可以使用 std::set 來作到這件事情，複雜度為 $O(N \log N)$ 。

當然，以上作法只是「其中一種」作法而已，當然還有其他的 greedy 解。

### subtask 2

可以發現，寶可夢的值域只有在 $200$ 裡面，所以可以開一個陣列 $cnt$ 去統計每個體重的寶可夢有多少個。

並且，可以想辦法把你在 subtask 1 所使用的 greedy 策略，想辦法在 $O(200)$ 的時間內算完。

這樣的複雜度就是 $O(NW)$，其中 $W = 200$

### subtask 3

既然你成功的解出 subtask 2，你可以試著把你在 subtask 2 使用到的 greedy 策略，想辦法用資料結構去維護，達到 $O(N \log N)$ 的複雜度。

這邊，我會提供另外一個 greedy 策略。

我們把一個在直升機的兩隻寶，假設體重分別為 $x, y$，分成以下兩種 case

1. $\max(x, y) > \frac{W}{2}$
2. $\max(x, y) \le \frac{W}{2}$

我的策略變成，盡量最大化第一種 case 的數量。最大化第一種 case，之後，在統計有多少有多少寶可夢體重 $\le \frac{W}{2}$，多少 $> \frac{W}{2}$。之後就可以把 $\le \frac{W}{2}$ 兩兩放在直升機上，其他的自己做一台直升機。

所以現在的問題就是要最大化第一種 case，我們可以使用另外一個經典問題：括號匹配來幫助我們。

括號匹配的問題是：給你一串由 () 構成的字串，算出最多有多少括號匹配。這個經典問題可以配合線段樹在 $O(Q \log N)$ 的時間內回答問題，詳細的作法可以參考 CF 380C 這道題目。

之後，我們把體重 $\le \frac{W}{2}$ 的寶可夢當成左括號 ```(```，體重 $> \frac{W}{2}$ 的寶可夢當成右括號 ```)```。

並且把寶可夢的體重，按照 $W, 1, W - 1, 2, W - 2, 3, \dots$ 的順序排好。依照這個順序排好後，把這題轉換成括號匹配問題。得到的括號匹配的最大值，就是上述 greedy 算法的第一種 case 的最大值了！

剩下實做細節的部份，就交給讀者們思考了！如果有任何問題，歡迎跟出題者討論～

## pG. 競程精靈 (Elves)
- Task provider: yp155136
- Task setter: yp155136

這題我打算直接講出解出這題的作法。

首先，有一個性質是，如果找到兩個環，那兩個環的邊都不一樣。但是他們擁有三個以上的共點，其中有一個點是 $x$ 。

那麼我們可以保證，$x$ 那個點一定住著競程精靈，因為一定可以找到符合條件的兩個環，他們經過 $x$ ，但是只有共兩個點（包括 $x$）。可以考慮把那兩個環進行 xor ，就可以證明這件事情！

考慮使用點雙連通分量（Biconnected Component），對於每個點，如果存在四條邊，那四條邊中，有兩個邊在同一個 BCC $S$ ，另外兩邊邊也在同一個 $T$ （$S$ 跟 $T$ 可以是一樣的），那麼，那個點就是有競程精靈所在的點，否則就不是。

複雜度為 $O(N + M)$。

Hint: 這題也可以用邊雙連通分量做掉，讀者們可以想想看要怎麼做。

Hint: 這題還有另外一個 $O(N \log N \log N)$ 的在樹上做啟發式合併的作法喔！

有任何問題，歡迎跟出題者討論～

## pH. 城市分析 (City)
- Task provider: yp155136
- Task setter: yp155136

### subtask 1

首先，開一個陣列 $cnt[100000]$ ，$cnt[i]$ 代表 $i$ 這個數字出現過的次數。

對於每筆詢問 $L, R, l, r$ ，先把 $[L, R]$ 的 $cnt[ a[i] ]$ 加上 $1$ 。之後，答會就會是 $cnt[ a[i] ]$ 的總和，其中 $i$ 在 $[l, r]$ 裡面！

複雜度為 $O(NQ)$ 。

### subtask 2

可以發現值域只有 $10$ ，所以你可以開 $10$ 棵線段樹，去維護在某個區間內，那 $10$ 個數字出現過多少次。這樣的話，就可以算出答案。具體來講，假設 $cnt(i, L, R)$ 代表 $[L, R]$ 內出現 $i$ 的次數，那麼答案就是 $cnt(0, L, R) \times cnt(0, l, r) + cnt(1, L, R) \times cnt(1, l, r) + \dots + cnt(9, L, R) \times cnt(9, l, r)$

### subtask 3

可以考慮莫隊算法。

要一次算 $(L, R)$ 到 $(l, r)$ 可能有點難，但是如果要算 $(0, x)$ 到 $(0, y)$ 是很簡單的，而且這個東西很好莫隊（開個兩個陣列統計$(L, R)$ 中，左邊的 pointer 跟右邊的 pointer 每個數字出現的次數，這樣就可以很好的莫隊了）。

所以，對於每筆詢問 $(L, R), (l, r)$，可以拆成四個部份：$(R, r) - (L - 1, r) - (R, l - 1) + (L - 1, l - 1)$。

因此，我們就可以把這些詢問給蒐集起來，使用莫隊算法。複雜度為 $O(N^{1.5})$！

如果想要更詳細的資訊，可以參考 <<SNOI 2017 一個簡單的詢問>> 這道題目！

### subtask 4

沒有辦法莫隊了，那麼我們嘗試來分塊吧！

讓我們把 $K = \sqrt{N}$ 的東西分成一塊。

對於每一塊，開個陣列紀錄，某個數字在這塊出現了多少次，並且這個東西也要做前綴和（$x_{i, j}$ 代表，$j$這個數字在前 $i$ 塊中出現過幾次），並且做一個陣列 $a_{i, j}$ ，代表第 $i$ 塊跟第 $j$ 塊的答案（把詢問當成這兩塊的區間，紀錄這個的答案）。並且對 $a_{i, j}$ 做二維前綴和。

以上的東西，都能夠在 $O(N^{1.5})$ 做好預處理！

接下來，在做詢問時，$(L, R)$ 可以分成（小塊，大塊，小塊）這三個部份，因此，我們要處理的答案，可以拆成（大塊 vs 大塊）、（小塊 vs 大塊）、（小塊 vs 小塊）這三個部份。

大塊 vs 大塊的部份，我們可以用剛剛預處理好的前綴和陣列，作到 $O(1)$ 查詢。

小塊 vs 大塊，可以跑過小塊裡面的所有數字，查詢在大塊裡面出現過幾次（查詢前綴和），可以作到 $O(N^{0.5})$ 查詢。

小塊 vs 小塊，可以使用 subtask 1 的作法，答案 $O(N^{0.5})$ 的作法。

因此，最後的複雜度為 $O(Q \times N^{0.5}) = O(N^{1.5})$ ，並且是在線的作法！

### subtask 5

這筆 subtask 有很多種作法，這邊講一個延伸 subtask 3的作法。

簡單來講，這筆 subtask 可以使用帶修改莫隊來做，複雜度為 $O(N^{1.666667})$ 。

或者是，在 subtask 4 的分塊中，把 $K = N^{0.666666}$ 個數字分成一塊，然後修改的時候，把前綴和陣列打掉重作，並且好好修改 $x$ 陣列（在 subtask 4 提到的 $x$），這樣的複雜度為 $O(N^{1.666666})$ 的在線作法。

### subtask 6

讓我們延伸 subtask 4 的作法。

subtask 4 作法無法延伸到這裡的原因，是因為單點修改在（大塊 vs 大塊）的時候會慘掉，而在（小塊 vs 小塊）、（小塊 vs 大塊），目前都可以在 $O(N^{0.5})$ 的時間內做好修改。

因此，我們現在不要做「二維前綴和」，我們改做 $N^{0.5}$ 個「一維前綴和」，並且讓詢問的答案，採用 $O(N^{0.5})$的方式。

但是，在單點修改的時候，修改的 $a_{i, j}$ ，會是一個十字型狀的東西。對於橫的那條，可以直接重新建造那條前綴和陣列，但是對於直的，每次都修改一個值會採用太慘的複雜度（不過這邊也可以改成$N^{0.5}$ 個 BIT（Binary Indexed Tree），讓總體複雜度為 $O(N^{1.5} \log N)$ ，如果常數夠小是有機會 AC 的！）。

因此，我們可以「再」開 $N^{0.5}$ 條「直的」前綴和，每次就把「直的」前綴和陣列更新。在詢問的時候，答案就會是（「橫的」前綴和 + 「直的」前綴和）。進而達到修改 $O(N^{0.5})$，詢問 $O(N^{0.5})$ 的複雜度。

因此，總體的複雜度，就會是 $O(N^{1.5})$ 的在線演算法！

如果需要更詳細的實做細節，或者是其他問題，歡迎跟出題者討論～