# 111學年度建國中學校內資訊能力競賽 初試題解 --- ## pA 外賓接待 Setter: PeiGan ---- ### subtask 1: 答案就是 6^6 ```cpp cout << 46656 << "\n"; ``` ---- ### subtask 2: 枚舉 46656 種可能，然後依次判斷可不可以 O(6^6\*6) --- ## pB 割韭菜 Setter: 8e7 ---- $a_{ij} \geq 0$ ---- 一次刪掉完整的一排是最佳的 所以看所有直排跟橫列的總和最大值即可 ---- $n \leq 30$ ---- 四維 DP? 沒有人真的這樣寫吧... ---- $n \leq 300$ $n \leq 1500$ ---- 注意到，任何一段直的或橫的連續區間都有可能被取出，因此答案是這些區間裡面的最大值。 最大連續和！ 如果用 $O(n^2)$ 的方式的話只會過 $n \leq 300$。 ---- 構造字串：把多餘的部份（上下左右）切掉之後最後切橫的/直的即可。 ---- [AC code](https://pastebin.com/PHBHg7Zm) --- ## pC 礦物採集 setter: Peigan ---- 前序、中序、後序遍歷：dfs ---- 必須相同：建邊、看連通塊 ---- ### subtask 1: 沒有特定解法 ---- ### subtask 2: ---- 建一張圖，節點就是$1 \sim n$，三種遍歷完後將對位建邊，最後dfs那張圖，看有幾個連通塊 ---- ### subtask 3: 利用 subtask 2 的想法，每次加邊後重新dfs找連通塊 ---- ### subtask 4: 你需要並查集。 好好記錄每次連完一條邊$(O( \alpha (n)))$後，記錄有幾個連通塊，就能$AC$。 總複雜度：$O((n+q) \times \alpha(n))$ --- ## pD 芒果不想寫 [p7](https://dmoj.ca/problem/cco20p3) setter: alvingogo ---- ### subtask 1: 枚舉 [l,r] 用前綴和維護區間快樂度總和 ---- ### subtask 2: 一個想法是枚舉右界，看每個左界對他的最大值 可以發現如果右界更右邊的話可行的左界只會更右 因為 $a_i \geq 0$，所以只要左界盡量靠左就好，用雙指標+前綴和維護，複雜度 O(n) ---- ### subtask 3: 從上一個 subtask 的想法過來 用雙指針維護目前的區域，用 set 或是線段樹維護區間最大值就好了 複雜度 $O(n \times log(n))$ code: [https://pastebin.com/neN68z9Z] ---- ## subtask 4: 可以發現如果一個點比左邊的小，那麼左邊的永遠不會用到，於是可以用 deque 維護目前的左界。新增的時候從後面看，要是他比當前結尾大就 dq.pop_back()；如果左界的過期了也要 pop_front() 然後 dq.front() 就是目前最小值 複雜度 O(n) 這個做法又叫做單調隊列 code: [https://pastebin.com/GVkxPqLP] ---- 我不會生測資 QQ ---- ### 鞭屍 有用線段樹的舉手 ---- ### Debug 記得輸進來的字串是 0-based --- ## pE [Tetris](https://jstris.jezevec10.com/) Idea: FHVirus Setter: 8e7 ---- ### Subtask 1 $n \le 15$ 可以 DFS ，在遇到每一個方塊的時候決定要不要 hold ，最後把生成的陣列轉成 `vector<int>` 丟進一個 `set<vector<int>>` 裡面最後看他的大小就好了。 ---- ### Subtask 1 $n \le 15$ 也可以用位元枚舉做。 複雜度： $2^n \cdot n \log (n \cdot 2^n)$ ---- ### Subtask 2 $a_i = i$ 從上一個 subtask 隱約可以發現最多要決定 $n-1$ 次 hold ，而且每一種 hold or not 的 01 字串都會唯一對應到一種放下的順序 答案就是 $2 ^ {n-1} \pmod {1e9 + 7}$ ！ ---- ### Subtask 3 $n \le 1000$ 考慮 DP ， $dp[i][j]$ 代表遇到 $i$ 個方塊後，手上 Hold 是第 $j$ 種，並在現在 queue 最前面的方塊和 hold 一樣的時候強制 hold，轉移： $$ dp[i][a[i]] = \sum _ {k = 1} ^ {n} dp[i-1][k] $$ 基底狀態：假設遇到第一個一定是 $Hold$ 起來的 ---- ### Subtask 4 每個數字最多出現十次 其實沒什麼用？ ---- ### Full credit 紀錄 $\sum dp_i$ 優化就好。 ---- ### Notes 好像比我想的難？ ---- ### AC Code by TLE_simulator ```cpp= #include <iostream> using namespace std; int c[200000], C; int main(){ ios_base::sync_with_stdio(false); int n, a; cin >> n >> a; C = c[a - 1] = 1; while (--n){ cin >> a; int i = C - c[--a]; if (i < 0) i += 1000000007; if ((c[a] += i) >= 1000000007) c[a] -= 1000000007; if ((C += i) >= 1000000007) C -= 1000000007; } cout << C << endl; } ``` ---- ### 鞭屍 ---- #### ckcon22_41 ```cpp= #include<iostream> using namespace std; int main(){ cout << 84; return 0; } ``` 同學你想達成什麼？ ---- #### ckcon22_32 ```cpp= #include<iostream> #include<vector> using namespace std; int main(){ cout<<42; } ``` 你也是，到底想幹嘛？ ---- #### ckcon22_14 ```cpp= #include<iostream> using namespace std; int main(){ int n, i; cin >> n; int a[n]; for(i=0; i<n; i++){ cin >> a[i]; } cout << 1248; } ```