## 112 學年度建國中學校內資訊能力競賽 複試題解 ---- # 難度 ## B<C<E<A<D --- ## pA 貓咪與老鼠 Setter : becaido ---- ### Subtask 1 $l_i=1,r_i=i$ ---- $i$ 可以看到 $\leq i$ 的所有魚 所以 $a_i$ 會是 $a_1\sim a_i$ 的最大值 直接掃過去，複雜度 $O(n)$ ---- ### Subtask 2 $n\leq 3000,r_i\leq i$ ---- $i$ 看到的人編號都比自己小 可以從編號小的往大的掃 ---- 因為 $n$ 很小， 每次直接 $O(n)$ 找 $a_{l_i}\sim a_{r_i}$ 的最大值 跟 $a_i$ 取 $\max$，複雜度 $O(n^2)$ ---- ### Subtask 3 $r_i\leq i$ ---- 不要暴力掃，用一個線段樹 複雜度 $O(n\log n)$ ---- ### Subtask 4 $l_i=r_i$ ---- 可以考慮建邊 如果 $i$ 可以看到 $j$， 那代表 $a_i=\max(a_i,a_j)$ 可以建一條 $j\to i$ 的邊 ---- 接下來有兩種做法 ---- 做法一： $n$ 點 $n$ 邊的有向圖會是很多個水母圖 ---- 一個點會有恰好一條入邊，$0$ 條或若干條出邊 ---- 先把環上點的 $a_i$ 都設成環上 $a_i$ 的最大值， 然後對每棵樹遍歷一次， 把自己的 $a$ 跟父節點的 $a$ 取最大值 ---- 做法二： 先將 $a_i$ 由大到小排序 ---- 從 $a_i$ 大的開始 bfs 將還沒走到點的 $a$ 設成此次 bfs 起點的 $a$ 如果一個點之前已經被走過 就可以不用把它當作起點了 ---- 複雜度 $O(n)$ 或 $O(n\log n)$ ---- ### Subtask 5 $\sum\limits_{i=1}^ n(r_i-l_i+1)\leq 5\times 10^ 5$ ---- 沿用前一子題的想法建邊 邊的數量 $\leq 5\times 10^5$ ---- 直接用做法二跑一次 複雜度 $O(n\log n+m)$，$m$ 為邊數 ---- ### Subtask 6 無其他限制 ---- 一個點會有很多條入邊 直接建是不行的 ---- 可以用線段樹的想法 對每個區間存這個區間的所有點會向哪裡連邊 ---- 在 bfs 到點 $i$ 時，可以看 $i$ 會被哪些區間包到 比如說 $n=8$，$3$ 會被 $[3,3],[3,4],[1,4],[1,8]$ 包到 對這些區間存的點，並且還沒走過的 bfs， 看完這個區間的點後就可以直接 clear 了， 因為存的點都會被走到 ---- 時間複雜度 $O(n\log n)$ 空間複雜度 $O(n\log n)$ [Code](https://ideone.com/TLJEqv) ---- 如果想耍毒可以寫線段樹優化建圖甚至是 SCC --- ## pB 拿鍋貼 Setter : 八方雲集同學 ---- ### 題敘 應該寫的夠清楚了吧，要用的方程式也在題敘寫出來了 比較需要注意的地方是轉成 $\sum_{j=1}^ i(a_j-x_j) \geq 0$ 會比較好處理 ---- ### subtask 2 呃，原本只是不知道要怎麼出 subtask 就放了，有特殊作法的人可以上台講 ---- ### subtask 1 考慮 $dp_{i,j}$ 表示現在考慮了前 $i$ 個人，目前這些人總共拿了 $j$ 個鍋貼會有幾種可能 轉移從 $b_i$ 枚舉到 $c_i$ 就好 記得判邊界 ---- ### 整題 從 $b_i$ 枚舉到 $c_i$ 這步可以前綴和優化 只要多開一個 $sum_{i,j}$ 表示 $\sum_{k=1}^j dp_{i,j}$ 然後就可以 $O(1)$ 算出 $dp_{i,j}$ --- ## pC 黃鼠狼與雞 Setter : PCC ---- ### 題敘 給一棵樹與多個節點的祖孫關係，求有幾個節點可以當作跟使得所有祖孫條件被滿足 ---- 假設條件的祖先是 $a$ ，子孫是 $b$ ---- ### Subtask 1 $N,Q \le 500$ ---- 暴力枚舉根，然後暴力從每個條件的子孫往回走到根，看是否經過祖先 複雜度 $O(N^2Q)$ ---- ### Subtask 2 $N,Q \le 3000$ ---- 跟上一個子題一樣，觀察到一個條件合法若且唯若 $LCA(a,b) = a$ 對於每個條件做 LCA 找答案 複雜度 $O(NQ\log N)$ ---- 也可以用每個人的 dfs 序判斷 複雜度 $O(NQ)$ ---- ### Subtask 3 $|u_i-v_i| = 1$ 簡單說就是一條鍊 ---- 考慮每個條件 如果 $a>b$ ，則可行的答案範圍就是 $[a,N]$ 如果 $a<b$ ，則可行的答案範圍就是 $[1,a]$ 把所有可行範圍取交集就是最終答案 複雜度 $O(N+Q)$ ---- ### Subtask 4 $a_i,b_i$ 是一條邊的兩端 ---- 考慮把每個條件的邊定向為 $a_i \rightarrow b_i$ 然後把其他不被任何條件包住的點縮起來變成 DAG 答案就是度數為 0 的連通塊 複雜度 $O(N+Q)$ ---- ### Subtask 5 無其他限制 ---- 把 $a_i\rightarrow b_i$ 之間的所有邊都定向再找度數為0的連通塊就是答案了 ---- 但是怎麼區間定向? ---- 樹鍊剖分! ---- 才怪，這題有比較好的做法 ---- 定根在1  假設問 $2,5$ 合法的答案區間長怎樣? ---- 定根在1  假設問 $3,4$ 合法的答案區間長怎樣? ---- 根據觀察， 如果 $LCA(a,b) = a$ ，合法的答案區間就是 $a$ 以上的所有點 否則就是 $a$ 的子樹 對每個條件算合法區間之後取交集就好 複雜度 $O(N+Q)$ 如果好好用 dfs 的話 用倍增則是 $O((N+Q)\log N)$ ---- ## code ``` != #include <bits/stdc++.h> #pragma comment(linker, "/STACK:8000000") using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second const int mxn = 2e5+10; vector<int> tree[mxn]; vector<int> dfn,ans; vector<int> req[mxn]; int idx[mxn]; int dp[mxn],val[mxn]; int n,q; void dfs(int now,int par){ idx[now] = dfn.size(); dfn.push_back(now); for(auto &i:req[now]){ if(idx[i] == -1){ val[i]++; } else{ val[1]++; val[dfn[idx[i]+1]]--; } } for(auto nxt:tree[now]){ if(nxt == par)continue; dfs(nxt,now); } dfn.pop_back(); idx[now] = -1; return; } void dfs2(int now,int par){ dp[now] += val[now]; for(auto nxt:tree[now]){ if(nxt == par)continue; dp[nxt] = dp[now]; dfs2(nxt,now); } return; } int main(){ //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int i = 1;i<n;i++){ int a,b; cin>>a>>b; tree[a].push_back(b); tree[b].push_back(a); } memset(idx,-1,sizeof(idx)); cin>>q; for(int i = 0;i<q;i++){ int a,b; cin>>a>>b; req[b].push_back(a); } dfs(1,1); dfs2(1,1); for(int i = 1;i<=n;i++)if(dp[i] == q)ans.push_back(i); cout<<ans.size()<<'\n'; for(auto &i:ans)cout<<i<<' '; return 0; } ``` ---- 但是好像還有各種奇形怪狀的解都會過??? --- ## pD 山脈與山谷 Setter : becaido ---- 這題如果看成一個 $n\times m$ 的平面 第 $i$ 行第 $j$ 列格子 $X_{i,j}=(a_i-b_j)^2$ 求一條只能向右、向下走的路徑的 $X$ 總和最小 這樣會比較好想 ---- ### Subtask 1 $n,m,k\leq 10$ ---- 總路徑數只會有 $C_{n-1}^{n+m-2}$ 條 直接 dfs 暴搜所有路徑 ---- 真的有人會不寫 DP 來拿這筆嗎 (? ---- ### Subtask 2 $n,m,k\leq 400$ ---- 令 $dp_{i,j}$ 為從 $(1,1)$ 走到 $(i,j)$ 的最小總和 $dp_{i,j}=\min(dp_{i-1,j},dp_{i,j-1})+(a_i-b_j)^2$ ---- 注意 $i=1$ 或 $j=1$ 的情況 複雜度 $O(nmk)$ ---- ### Subtask 3 $n,m,k\leq 5000$ ---- 既然 $a,b$ 遞增， 那想必有一些性質可用 ---- 令 $p_i$ 為 $(a_i-b_j)^2$ 最左邊最小值發生的 $j$ 令 $[l_i,r_i]$ 是在最小總和的路徑下第 $i$ 行會走到的範圍 $l_i=r_{i-1}$ ---- 現在來看 $i,i+1$ 這兩行 當 $j<p_i$ 的時候，$X_{i,j}<X_{i+1,j}$ 當 $j>p_{i+1}$ 的時候，$X_{i,j}>X_{i+1,j}$ ---- 可以得知 $p_i\leq r_i=l_{i+1}\leq p_{i+1}$ 因為在 $p_i$ 左邊的走上面一定比較好 在 $p_{i+1}$ 右邊的走下面一定比較好 所以分界點會在 $p_i,p_{i+1}$ 之間 ---- 那 $r_i$ 具體來說會是多少 會是 $\sum\limits_{j=p_i}^k X_{i,j}+\sum\limits_{j=k}^{p_{i+1}} X_{i+1,j}$ 發生最小值的 $k$ ----  這個分界點正好會是最小滿足 $X_{i+1,j}\leq X_{i,j+1}$ 的 $j$ ---- 於是導出了一個 greedy 的做法： 每次走右邊、下面比較小的那一個 複雜度 $O((n+m)k)$ ---- 這個 greedy 在 $a,b$ 嚴格遞增的時候是好的 但如果非嚴格遞增呢？ 你能找出會讓 greedy 爛掉的 case 嗎？ ---- ### Subtask 4 $n=2$ ---- 每次可以二分搜出 $r_1$ 是多少 $\sum (a_i-b_j)^2$ 的值要怎麼維護 ---- $\sum\limits_{j=1}^{r_1}(a_1-b_j)^2$ $=\sum\limits_{j=1}^{r_1}(a_1^2-2a_1b_j+b_j^2)$ $=r_1a_1^2-2a_1\sum\limits_{j=1}^{r_1}b_j+\sum\limits_{j=1}^{r_1}b_j^2$ ---- 可以開兩個 BIT，一個維護 $\sum b_j$，一個維護 $\sum b_j^2$ $\sum\limits_{j=l_2}^m (a_2-b_j)^2$ 的同理 複雜度 $O(n+k\log n)$ ---- ### Subtask 5 地殼變動形式只會是 $1\ x\ h$ ---- $p_1\leq p_2\leq\dots\leq p_n$ 我們將 $p_i$ 相同的 $a$ 設成一組 ---- 同一組內除了首尾兩個元素之外， 其他人的 $l_i=p_i=r_i$ ---- 開四個 BIT 記錄 $\sum a_i,\sum a_i^2,\sum b_j,\sum b_j^2$ 區間可以用 set 維護 ---- 改動 $a_x$ 時， $p,l,r$ 可能會變動的只有 $a_x$ 那組、$a_x$ 前一組、$a_x$ 後一組 ---- 每次先清空這三組的答案 然後重新對這些人分組 組數是 $O(1)$ 的 ---- 當確定一個組的前端是 $u$ 後 可以二分搜出最後一個 $p_d=p_u$ 的 $d$ ---- 二分搜的方法有兩種 一種是每次再二分搜找出這個人的 $p$ 是多少 一種是直接檢查 $p_u$ 是不是這個人的 $p$ ---- 如果用第一種複雜度 $O(n\log n+q\log^2 n)$ 用第二種複雜度 $O((n+q)\log n)$ 不過時間沒有差很多， 因為 set 的 $\log$ 常數很大 ---- ### Subtask 6 無其他限制 ---- 現在 $b$ 也有可能被改變了 沿用剛剛的想法 去找 $p=b_y$ 所在的組 （找不到就視為這組為 $0$ 個人） ---- 發現有可能會被更動到的有五組 $b_y$ 這組、前兩組、前一組、後一組、後兩組 ---- 清空這些組後 就一樣可以二分搜重新分組 ---- 時間複雜度 $O((n+q)\log n)$ [Code](https://ideone.com/dTrfbX) --- ## pE 中卷遊戲 Setter : becaido ---- 首先注意到每個 $a_{i,j}$ 的模逆元都可以預處理 之後可以 $O(1)$ 直接拿到 接下來 $\sum\limits_{i=1}^n m_i$ 都表示成 $M$ ---- ### Subtask 1 $m_i\leq 10$ ---- 每次問 $x,y$， 直接 $m_x\times m_y$ 暴力枚舉要派哪隻中卷 複雜度 $O(M\log C + qm_i^2)$ ---- ### Subtask 2 $q\leq 10$ ---- 詢問 $x,y$ 可以 $O(m_x+m_y)$ 算 先將每個人的 $a_{i,1}\sim a_{i,m_i}$ 都排序好後 就可以利用類似 merge sort 的想法線性算答案 複雜度 $O(M(\log C+\log M) + qm_i)$ ---- ### Subtask 3 無其他限制 ---- 除了每次詢問暴力做， 最多要 $O(M)$ 的方法 有另外一種做法 ---- 對於每個 $i$， 計算 $x=i,y=i$ 的所有答案 可以將全部 $a_{i,j}$ 排序一遍後 $O(M)$ 算 複雜度 $O(nM)$ ---- 如果我選一個分界點 $K$ 呢？ ---- $m_i\leq K$ 的套用第一種算法 $m_i>K$ 的套用第二種算法 ---- 複雜度分析： 第一種每次詢問最多花 $O(K)$，共 $O(qK)$ 第二種最多只會有 $\frac{M}{K}$ 人的 $m_i>K$， 總共要 $O(\frac{M}{K}\times M)=O(\frac{M^2}{K})$ ---- $O(qK + \frac{M^2}{K})$， $K$ 取 $O(\frac{M}{\sqrt{q}})$ 最好 實作上會有常數的差異， $K$ 不要太大或太小基本上都可以過 複雜度 $O(M\sqrt{q})$ [Code](https://ideone.com/gY7mDz) ---- 這題有預處理的做法也有離線的做法 預處理時只要不要每次做加法 都呼叫一次 map / unordered_map 基本上都不會被卡 ---- 此外，PCC 發現一個另解： 每次問 $x,y$，枚舉 $m_x,m_y$ 比較小的那個人 對另外一個人二分搜，並把算過的答案存起來 複雜度雖然會多一個 $\log$，但是常數很小 這樣為什麼是好的就留給讀者自行證明了 :P --- ## 北市賽加油 > <