## 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
![](https://hackmd.io/_uploads/Hy7JXXwe6.png)
假設問 $2,5$
合法的答案區間長怎樣?
----
定根在1
![](https://hackmd.io/_uploads/S1FfXQvep.png)
假設問 $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$
----
![](https://hackmd.io/_uploads/BkkBG-Klp.png)
這個分界點正好會是最小滿足 $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
---
## 北市賽加油 > <
{"title":"建中資訊校內賽題解","slideOptions":"{\"theme\":\"night\",\"transition\":\"fade\"}","contributors":"[{\"id\":\"44be8f10-8a3c-4f95-9084-6a5f98bc8bf5\",\"add\":2539,\"del\":55},{\"id\":\"419a2967-b6a7-40d3-9328-00c86c8ea526\",\"add\":394,\"del\":11},{\"id\":\"52026c9b-045c-4e64-9cc6-78986ed19085\",\"add\":4887,\"del\":94}]"}