112 學年度竹科實中校內賽題解

# 112 學年度竹科實中校內賽題解 ## pA. 區間第k大 #### writer: PixelCat #### 定位：水 :::warning :::spoiler 滿分因為題目有保證陣列 $A$ 是嚴格遞增，所以 $[L,R]$ 範圍中第k大的數字就是 $A[R-k+1]$。直接輸出即可。 ::: :::info :::spoiler sample code ```cpp= #include<iostream> using namespace std; int n,arr[105],l,r,k; int main(){ cin>>n; for (int i=1;i<=n;i++) cin>>arr[i]; cin>>l>>r>>k; cout<<arr[r-k+1]<<endl; } ``` ::: ## pB. 構造LIS #### writer: Cookie197 #### 定位：中 :::warning :::spoiler subtask 2 $n=2$ 的只有兩種可能的 $p$，即 $1,2$ 或 $2,1$。 ::: :::warning :::spoiler subtask 3,4 $n\le 8$，可以利用 `next_permutation` 枚舉所有可能的答案，並利用經典算法計算出每個位置的 LIS 長度。例如 $O(n^2)$ DP。找到其中一組合法答案即可輸出。 ::: :::warning :::spoiler subtask 3,5 0.5倍可以發現 $a$ 為非嚴格遞增，且會呈現 $1,1, \cdots 2,2, \cdots 3,3, \cdots$ 的形式。我們可以在每次換數字的地方讓 $p_i$ 遞增，不是換數字的地方就讓 $p_i$ 遞減。例如：$a=[1,1,2,2,2,3,3,3]$ 可以構造 $p=[6,5,7,4,3,8,2,1]$。其中 $a_1=6,a_3=7,a_6=8$ 為遞增，$a_2=5,a_4=4,a_5=3,a_7=2,a_8=1$ 為遞減。 ::: :::warning :::spoiler 滿分 1. 首先發現「從根節點到 $i$ 的 $LIS$ 長度」必定大於等於「從根節點到 $i$ ，並最後一項元素是 $p_i$ 的 $LIS$ 長度」，$a_i \ge b_i$，a 陣列只是 b 陣列的前綴最大值，所以滿足 b 必定會滿足 a。 2. 觀察 $b_i$ 相同的 $i$，可以發現同一條鏈上越深者（or數線上越右邊） $p_i$ 會越小。 3. 接著，以$\ge 2$ 的 $b_i$ 而言，必須存在至少一個 $i$ 的祖先節點 $j$ 使得 $b_j = b_i - 1$ 且 $p_i > p_j$ ，因為在算LIS時 $i$ 才可以接在 $j$ 後面。 4. 我們可以建立大小關係的有向圖，從 $p_i$ 大的指向小的。第3點中，每個點找到一個 $b$ 小1且離他最近的祖先節點建邊。第2點則是 $b$ 相同的祖孫互相連接。最後只要依拓撲序給節點們 $p_i$ 就好。 * 這題還有很多不同的解法，大家可以想想看 ::: :::info :::spoiler 滿分另解 (code) 其實這題有看起來像唬爛的超短解。 ```cpp= int main(){ cin>>n; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=n;i++) {cin>>b[i]; v[b[i]].push_back(i);} for (int i=2;i<=n;i++) int x, cin>>x; int x = n; for (int i=n;i>=1;i--){ for (int u:v[i]) { ans[u] = x; x--; } } for (int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; } ``` ::: ## pC. 核電廠 #### writer: PixelCat #### 定位：中 :::warning :::spoiler subtask 2 假如是第一天那一定要拿。假如不是第一天的話，要嘛拿起來獲得 $a_i - p$ 元，要嘛放棄然後什麼都拿不到，因為前一天亂乘之後會立刻變零。每一天的決策之間不會互相影響，greedy 就好。時間複雜度 $O(n)$。這個子題的目的是讓你有機會撈分，順便告訴你 greedy 是錯的。 ::: :::warning :::spoiler subtask 3 暴搜。時間複雜度 $O(n 2^n)$。這個子題的目的是讓你有機會撈分。 ::: :::warning :::spoiler subtask 4 注意到一根燃料棒被使用到的時間是一個連續區間，賺到的收入是從這個區間的第一天開始往後面一直乘加起來的總和。令 $f(i, j)$ 代表如果第 $i$ 天買的燃料棒一直用，會在第 $j$ 天獲得多少收入；$S(i, j)$ 帶表第 $i$ 天買的燃料棒一路用到第 $j$ 天的賺錢總和： $$ f(i, j) = \begin{cases} a_i, & \text{if $i = j$} \\ f(i, j - 1) \cdot c, & \text{otherwise} \end{cases} \\ S(i, j) = \sum_{k = i}^j f(i, k) $$ 我們考慮動態規劃：`dp[i]` 代表第 $i$ 天結束的時候你能賺幾元，我們有以下轉移式： $$ dp_0 = 0 \\ dp_i = \max_{0 < j \le i} \left( dp_{j - 1} + S(j, i) \right) $$ 枚舉 $i, j$ 之後暴力算 $S(j, i)$ 可以在 $O(n^3)$ 時間算完。 ::: :::warning :::spoiler subtask 5 **作法一** 剛剛的 $S(j, i)$ 可以預處理建表，$O(1)$ 查詢，複雜度是 $O(n^2)$。 **作法二** 剛剛是枚舉每一段和前一段的結尾，但因為 $S$ 函數比較容易由前往後算，這次我們枚舉每一段的開頭、往後枚舉結尾，更新後面的答案。 ```cpp= auto f = [&](long long x) { return (x * c) / 1000; }; for(int i = 1; i <= n; i++) { long long cur = a[i]; long long sum = a[i] - pen; for(int j = i; j <= n; j++) { dp[j] = max(dp[j], dp[i - 1] + sum); cur = f(cur); sum += cur; } } ``` 複雜度同樣是 $O(n^2)$。改成由後往前做也可以做到 $O(n^2)$，可能有人會覺得比較直覺一點。留給讀者做為練習。 ::: :::warning :::spoiler subtask 6 觀察到 $c < 1$，所以 $f(i, j) > 0 \Rightarrow f(i, j) > f(i, j + 1)$，在 $\max \left(a_i\right)$ 天後一根燃料棒將不再提供收入。也就是說，$S(i, j)$ 在 $j > 100 \geq \max \left(a_i\right)$ 時是定值，不用一個一個更新，可以丟進某個地方存起來，以後查最大值就好。沿用上一個子任務的作法，每次我們往後轉移 100 天，時間複雜度 $O(n \cdot \max{a_i})$。 ::: :::warning :::spoiler subtask 7 觀察到奇怪的條件 $c \le 0.95$，不會太大。 $$ \log_{1/c}\left( \max a_i \right) = \log_{1/0.95}10^9 < 405 $$ 也就是說，在這麼多回合之後，所有燃料棒都會失效。時間複雜度 $O(n \cdot \log_{1/c}\left( \max a_i \right))$。 ::: :::info :::spoiler Model Solution ```cpp= #include<bits/stdc++.h> #define int LL using namespace std; using LL = long long; const int MAXN = 200'000; int a[MAXN + 10]; int dp[MAXN + 10]; int mx[MAXN + 10]; int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // =^-w-^= int n, c, pen; cin >> n >> c >> pen; for(int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = -1e18; } for(int i = 0; i <= n; i++) { mx[i] = -1e18; } auto f = [&](int x) { return (x * c) / 1000; }; for(int i = 1; i <= n; i++) { int cur = a[i]; int sum = a[i] - pen; for(int j = i; j <= n; j++) { if(cur == 0) { mx[j] = max(mx[j], dp[i - 1] + sum); break; } dp[j] = max(dp[j], dp[i - 1] + sum); cur = f(cur); sum += cur; } mx[i] = max(mx[i], mx[i - 1]); dp[i] = max(dp[i], mx[i]); } cout << dp[n] << "\n"; return 0; } ``` ::: ## pD. 通行證 #### writer: Cookie197 #### 定位：中 :::warning :::spoiler subtask 2 $n,m$ 都很小，可以暴力枚舉所有可能的 $1$ 到 $n$ 的路徑，並算出所有路徑中的最少花費。 ::: :::warning :::spoiler subtask 3 $f \le 7$，可以 $2^f$ 枚舉所有幫派的 subset，只考慮那個 subset 對應的合法邊，看看能不能從 $1$ 走到 $n$。最後再從所有合法的 subset 找出最小花費。複雜度 $O((n+m)2^f)$ ::: :::warning :::spoiler subtask 4,5 題目有說明 $a_i \ge 2$，也就是說 $c_i$ 會 $\ge c_1 + c_2 + \cdots c_{i-1}$。所以我們可以從最大的 $c$ 考慮「有沒有辦法不選他」。對於某個 $i$，如果忽略含有 $i$ 幫派的道路時仍能從 $1$ 走到 $n$，那就可以不付 $c_i$ 的錢，並要記得隨後的檢查都不能再走含有幫派 $i$ 的道路。反之，我們就一定要選 $c_i$。複雜度 $O((n+m)f)$ ::: :::warning :::spoiler subtask 5 另解其實就是 bitwise-or 最短路，$f\le 256$ 可以用 bitset 做。 ::: ## pE. 叫外送 #### writer: Cookie197 #### 定位：難 :::warning :::spoiler subtask 2 $n=1$ 分成兩個情形： * 由左到右為 + -：直接走到底 * 由左到右為 - +：先拿披薩再走回住家 ::: :::warning :::spoiler subtask 3 利用`next_permutation`暴力枚舉所有 $(2n)!$ 種可能的路線，在所有合法路線中找出距離最小值。複雜度：$O(n(2n)!)$ ::: :::warning :::spoiler subtask 4 1. 若不是在結尾，「拿一個披薩，送一個披薩」一定比「拿兩個披薩，送兩個披薩」好。（因為你送完要往右走，會有更大一個區塊被多算到）畫一些圖就會發現（也可以參考 subtask 6 的圖），最佳解一定是「拿一個披薩，送一個披薩，拿一個披薩，送一個披薩...最後拿 $k$ 個披薩，送 $k$ 個披薩」對於每個詢問枚舉這個 $k$ 就好。複雜度：$O(nq)$ ::: :::warning :::spoiler subtask 5 2. 最佳解的回頭點一定是發生在「住家數量前綴 = 店家數量前綴」的地方，因此我們可以把一串東西「簡化」成一個「- +」或「+ -」（剩下左右兩個「重要點」）然後再套 subtask 4 的作法。例如：「- - + - + +」 $\Rightarrow$ 「- +」 3. 「+ -」可以直接從左邊走到右邊，因此可以直接忽略，但是如果是在結尾就要小心簡化完就跟 subtask 4 一樣了複雜度：$O(nq)$ ::: :::warning :::spoiler subtask 6 4. 我們把 subtask 4 中，$k=1$ 到 $n$，「每個區間被算到幾次」寫出來，發現會是一串 1 和 3 交替，最後是一個 1 和一串 2，如下圖 ![](https://hackmd.io/_uploads/H1P8efwJp.png =50%x) 5. 我們把 $k=x$ 時的答案稱為 $f(x)$。當某個區間的長度增加 $val$ 時，會存在某個 $p$ 使得以下兩者之一成立： * $f(1)$ 到 $f(p)$ 都增加 $3v$ ，$f(p+1)$ 到 $f(n)$ 都增加 $v$ (當區間編號為偶數) * $f(1)$ 到 $f(p)$ 都增加 $v$ ，$f(p+1)$ 到 $f(n)$ 都增加 $2v$ (當區間編號為奇數) 6. 因此我們可以用一個支援區間加值，全域最小值的線段樹來維護這個答案。一個建築的座標變動時，會有兩個區間的距離改變。複雜度：$O(q\log(n))$ ::: :::warning :::spoiler subtask 7 7. 根據 subtask 5，我們可以把建築物的排列「簡化」。簡化完再套剛剛的線段樹就好了！如果修改的建築不是「重要點」那可以直接忽略此次修改。 8. 若結尾是「+ -」請特別注意。在此不贅述。複雜度：$O(q\log(n))$ ::: ## pF. 夏日祭 #### writer: Cookie197 #### 定位：易 :::warning :::spoiler 滿分擷取高木，西片，和觀景台的座標。接著分成以下幾個情形來討論： * 沒有觀景台：答案就是兩人的曼哈頓距離。 * 有觀景台： * 高木西片觀景台的 x 座標相同： * $n=1$：若觀景台的 y 座標在兩人中間，則答案為 -1，否則答案為兩人的曼哈頓距離 +2。 * $n>1$：答案為兩人的曼哈頓距離 +2。 * 高木西片觀景台的 y 座標相同：答案為兩人的曼哈頓距離 +2。 * 以上皆非：答案為兩人的曼哈頓距離。 ::: :::warning :::spoiler 滿分另解使用 BFS。 :::