# 延平中學 113-2 高中部程式設計競賽題解
[點這裡](https://codeforces.com/contestInvitation/f8c85a97d6c5629bc97ddd52fca2a0d34c355df8)可以找到題目敘述，也可以上傳程式碼。
[計分板連結](https://0x0c5cbae8.github.io/ranking-113-2/)
#### 非常感謝 :
- 陳妙如老師的指導；
- howard20060216, kenkenken, Justinshao, ub33, Ststone 幫忙驗題；
- [少年圖靈計劃](https://www.tw-ytp.org/)提供比賽的環境和系統！
#### 一些有趣的數據 :
AI 解出的分數（maximum of 5 tries）：
- OpenAI o3-mini: 984.07 / 1100 分
- xAI Grok 3 Think: 884.07 / 1100 分
- Gemini 2.0 Flash Thinking: 686.72 / 1100 分
AI 推測每一題的 Codeforces Rating:
- pA: 800
- pB: 800
- pC: 800
- pD: 800
- pE: 1000
- pF: 1400
- pG: 3200
- pH: 1600
- pI: 2200
- pJ: 2000
- pK: 2400
注意這只是整題的難度 ，有很多題的子任務難度跟整題的差很多。
## pA - 威利
### 子任務二、三 （$|P| \le 10$）
:::spoiler 解題思路
子任務二跟子任務三的想法都是一樣的：在 $S$ 的每個位置跟 $P$ 對比，看一不一樣。可以從左到右比對，找到一樣的就 `break;` ，如果都沒找到就輸出 $-1$ 。用 `std::find` 也可以。
時間複雜度： $O(|S| \cdot |P|)$
:::
:::spoiler 程式碼
```cpp=
// subtasks 2,3 solution
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
string s, t;
cin>>s>>t;
int n=s.size(), m=t.size();
bool ok=0;
for(int i=0;i<n-m+1;i++){
if(ok) break;
for(int j=0;j<m;j++){
if(s[i+j]!=t[j]) break;
if(j==m-1){
cout<<i+1<<'\n';
ok=1;
}
}
}
if(!ok) cout<<-1<<'\n';
}
return 0;
}
```
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
這題的「無特殊限制」子任務只佔一分。原因是因為原題只有 $|P| \le 10$ 的限制，但因為有一個 $O(|S|+|P|)$ 的演算法解法，所以就加了這個一分的子任務，來獎勵一下知道這個演算法的同學。其實有很多演算法可以在 $O(|S|+|P|)$ 內解出這一題，例如 [KMP](https://cp-algorithms.com/string/prefix-function.html) 、 [Z Algorithm](https://cp-algorithms.com/string/z-function.html) 、 [String Hashing](https://cp-algorithms.com/string/string-hashing.html) 等。下面程式碼是用 Z Algorithm 解的。
時間複雜度： $O(|S|+|P|)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
string s, p;
cin>>s>>p;
s = p + '#' + s;
int n = s.size(), m = p.size();
vector<int> z(n, 0);
int l=0, r=0;
for(int i=1;i<n;i++){
if(i<r) z[i]=min(z[i-l], r-i);
while(i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++;
if(i+z[i]>r) l=i, r=i+z[i];
}
bool ok=0;
for(int i=m+1;i<n;i++){
if(z[i]==m){
cout<<i-m<<'\n';
ok=1;
break;
}
}
if(!ok) cout<<-1<<'\n';
}
return 0;
}
```
:::
## pB - 排球
### 子任務二（對於所有 $i$ ， $a_i=1$ 。）
:::spoiler 解題思路
從特殊的限制可以得知 $a_1=1$ ，代表一號同學永遠只會傳給自己。因此只有在 $n=1$ 的情況下，老師會被滿足。所以寫 `cout<<((n-1)?"No\n":"Yes\n");` 就好了。
時間複雜度： $O(n)$
:::
### 子任務三（無特殊限制）
:::spoiler 解題思路
模擬那顆排球球將會傳給哪些人。初始一個長度為 $n$ 的 boolean 陣列 `vis[n]` 並設為 `false` ，每次傳給下一個人 $x$ 的時候設 `vis[x]` 為 `true` ，如果傳了很多次之後 `vis` 還有 `false` 的，就代表他們沒有拿過球，老師不會被滿足；反則反之。
但傳了「很多次」到底是多少次呢？
其實傳了 $n$ 次之後，就不會再傳給新的人了，也就是說，傳了 $n$ 次之後 `vis` 不會再有值從 `false` 變成 `true` 了。
原因其實很簡單：因為傳球時終究會有一個人第二次拿到了球。假設第一位拿到球兩次的人座號為 $x$ ，那他就會傳給 $a_x$ 號，而 $a_x$ 號也肯定不是第一次拿到球（因為 $x$ 號第一次拿到球時已經傳給 $a_x$ 過了）。按照這種邏輯推理，可發現之後傳給的人肯定是之前已經傳過的，不可能新傳給另一個之前沒拿過球的人。
最後，因為班上只有 $n$ 個人，所以前 $n+1$ 個拿到球的人至少有一個人是重複的（也就是說至少有一個人拿到超過一次球），因此之後不會有新拿到球的人。
跟這題有關的主題： [Functional Graphs](https://usaco.guide/silver/func-graphs?lang=cpp)
時間複雜度： $O(n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i], a[i]--;
vector<bool> vis(n, 0);
int x=0;
for(int i=0;i<n;i++){
vis[x]=1;
x=a[x];
}
bool ok=1;
for(int i=0;i<n;i++)if(!vis[i])ok=0;
cout<<(ok?"Yes\n":"No\n");
}
return 0;
}
```
:::
## pC - 分解
### 子任務二（$x < 2^{30}$）
:::spoiler 解題思路
先把二進位轉成十進位，再看數字能整除二幾次。
時間複雜度： $O(t \cdot log(x))$
:::
### 子任務三（無特殊限制）
:::spoiler 解題思路
就像十進位數字的最後有幾個 $0$ 代表它能整除 $10$ 幾次，二進位數字也有同樣的性質：最後有幾個 $0$ 代表它能整除 $2$ 幾次。
> 證明
>
> 假設 $a_1, a_2, ..., a_n$ 為二進位數字 $x$ 裡 $1$ 所出現的位置（從右往左數。）
>
> 則 $x = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$ 。
>
> 而因為 $a_1 < a_2 < \cdots < a_n$ ，所以可以提出 $2^{a_1}$，得到 $x = 2^{a_1}(1 + 2^{a_2-a_1} + \cdots + 2^{a_n-a_1})$
>
> 移項得到 $\frac{x}{2^{a_1}} = 1 + 2^{a_2-a_1} + \cdots + 2^{a_n-a_1}$
>
> 而右邊的式子是奇數，所以最多能除以 $a_1$ 次 $2$ ，而 $a_1=$ 最右邊的 $1$ 的位置，也就是 $x$ 右邊 $0$ 的數量。
所以答案是 $x$ 最後 $0$ 的數量。
時間複雜度： $O(log(x))$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int ans=0;
for(int i=(int)s.size()-1;i>=0;i--){
if(s[i]=='1')break;
ans++;
}
cout<<ans<<'\n';
}
return 0;
}
```
:::
## pD - 星座
### 子任務二（$n \le 7$）
:::spoiler 解題思路
枚舉所有星座 $b$ 的星星的順序，並跟星座 $a$ 比對是否可以只靠平移就可以重合。
時間複雜度： $O(t \cdot n! \cdot n)$
:::
### 子任務三（無特殊限制）
:::spoiler 解題思路
解法一：一個蠻天才的想法是如果兩個星座是相同的，那代表平移之後，它們的重心（所有座標加起來除 $n$ ）也會是相同的。所以可以先求兩個座標的重心，把星座 $b$ 平移到跟星座 $a$ 的重心一樣的地方。最後把兩個星座星星的座標都 sort ，如果座標都一樣代表星座也是相同的。
解法二：其實可以不用求重心，直接 sort 之後比對，而因為 sort 的定義就是按照小到大排序，就算有平移也不會影響他們相對的大小排序。
以下程式碼是用解法二的想法。
時間複雜度： $O(t \cdot n \: log \: n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<pair<int, int>> a(n), b(n);
for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
for(int i=0;i<n;i++)cin>>b[i].first>>b[i].second;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for(int i=0;i<n;i++)a[i].first-=b[i].first,a[i].second-=b[i].second;
bool ok=1;
for(int i=1;i<n;i++){
if(a[i].first!=a[0].first||a[i].second!=a[0].second){
cout<<"No\n";
ok=0;
break;
}
}
if(ok)cout<<"Yes\n";
}
return 0;
}
```
:::
## pE - 徘徊
### 子任務二（$\sum^n_{i=1}{a_i} \le 2 \times 10^5$ 且 $q=1$）
:::spoiler 解題思路
因為陣列 $a$ 的和不超過 $2 \times 10^5$ ，因此可以照順序慢慢模擬施教授的移動，然後因為 $q=1$ ，所以模擬到 $t_1$ 的時候施教授所在的位置就是答案。
時間複雜度： $O(\sum a_i)$
:::
### 子任務三（$\sum^n_{i=1}{a_i} \le 2 \times 10^5$）
:::spoiler 解題思路
承子任務二，這個子任務也可以照順序慢慢模擬施教授的移動，但因為 $q>1$ ，所以可以先輸入所有的 $q$ 值，按照時間先後 sort ，模擬到 $t_i$ 的時候施教授所在的位置就是第 $i$ 個要輸出的答案。
時間複雜度： $O(\sum a_i + q \: log \: q)$
:::
### 子任務四（$q = 1$）
:::spoiler 解題思路
因為 $q=1$ ，然後從題目敘述可得知施教授走的路徑長等於開始考試後經過的時間，所以就看施教授每次轉彎時她走的路徑長有沒有超過 $t_1$ 。如果有超過就代表是在上一次轉彎過後的某一刻時間剛好經過 $t_1$ 。求確切的位置的方法就看她當時面朝的方向，然後算她會走多久時間才會到就好了。
時間複雜度： $O(n)$
:::
### 子任務五（無特殊限制）
:::spoiler 解題思路
解法一：結合子任務三、四的想法，先輸入所有的 $q$ 值，按照時間先後 sort ，再依序看施教授每次轉彎時她走的路徑長有沒有超過 $t_i$ 。
解法二：可以用兩個前綴和陣列，一個存施教授目前走過的路徑長，另一個存施教授的位置。每次詢問時就用 upper\_bound 查路徑長前綴和在哪一次轉彎後時間有經過 $t_i$ ，再用位置前綴和找到確切的位置。
以下程式碼是用解法二的想法。
時間複雜度： $O(n + q \: log \: q)$ 或 $O(n + q \: log \: n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin>>n>>q;
vector<ll> a(n), pre(n+1), d(n+1);
for(int i=0;i<n;i++){
cin>>a[i];
pre[i+1]=pre[i]+a[i];
d[i+1]=d[i]+a[i]*(i%2?-1:1);
}
while(q--){
ll t;
cin>>t;
int ind = upper_bound(pre.begin(), pre.end(), t)-pre.begin()-1;
ll pos = d[ind];
pos += (t-pre[ind])*(ind%2?-1:1);
cout<<pos<<' ';
}
return 0;
}
```
:::
## pF - 拔河
因為這些朋友關係可以以一顆樹表示，所以以下會以樹的術語講解。
### 子任務二（$t=1$ 且 $n \le 2000$）
:::spoiler 解題思路
枚舉被拆開的朋友對。對於每條邊，刪掉之後會形成兩顆樹（分別代表兩隊的人），而算出那兩棵樹的大小（用 DFS 或 BFS 等）後，求相減絕對值的最小值。
時間複雜度： $O(n^2)$
:::
### 子任務三（$t=1$）
:::spoiler 解題思路
承子任務二，可以先做一次 DFS 求出所有子樹的大小，然後枚舉刪掉的邊的時候就不需要重複求兩顆樹的大小，而是可以直接從子樹的大小算出來答案。
時間複雜度： $O(n)$
:::
### 子任務四（$t=2$ 且 $n \le 2000$）
:::spoiler 解題思路
枚舉不被拆開的朋友對。對於每條邊，刪掉之後會形成兩顆樹（分別代表兩隊的人），而算出那兩棵樹的二分圖（用 DFS 或 BFS 等）後，把節點按照二分圖塗成黑色或白色，求黑色總和減白色總和絕對值的最小值。
時間複雜度： $O(n^2)$
:::
### 子任務五（$t=2$）
:::spoiler 解題思路
承子任務四，可以先做一次 DFS 求出所有子樹的黑色節點數和白色節點數，然後枚舉刪掉的邊的時候就不需要重複求兩顆樹的二分圖，而是可以直接從子樹的黑白節點數算出來答案。
時間複雜度： $O(n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int mx=2e5+5;
vector<int> adj[mx];
int sz[mx], color[mx][2];
// t=1
void dfs1(int u, int e){
sz[u]=1;
for(int i:adj[u]){
if(i==e) continue;
dfs1(i, u);
sz[u]+=sz[i];
}
}
// t=2
void dfs2(int u, int e, int c){
color[u][c]=1;
for(int i:adj[u]){
if(i==e) continue;
dfs2(i, u, 1-c);
color[u][0]+=color[i][0];
color[u][1]+=color[i][1];
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, t;
cin>>n>>t;
for(int i=0;i<n-1;i++){
int u, v;
cin>>u>>v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
if(t==1){
dfs1(0, -1);
int ans=n;
for(int i=1;i<n;i++){
ans=min(ans, abs(n-2*sz[i]));
}
cout<<ans<<'\n';
} else {
dfs2(0, -1, 0);
int ans=abs(color[0][0]-color[0][1]);
for(int i=1;i<n;i++){
int c1=color[0][0]-color[i][0]+color[i][1];
int c2=color[0][1]-color[i][1]+color[i][0];
ans=min(ans, abs(c1-c2));
}
cout<<ans<<'\n';
}
return 0;
}
```
:::
## pG - 機器
這題沒有解到 $20$ 分的需要好好檢討一下。
### 解法一（大約 $20$ 到 $30$ 分）
:::spoiler 解題思路
只用一臺機器人，並輸出 `TL 20000 1 2 3 4 ... 20000` 。
這樣的 $x=1$ ，且 $t \approx 20000^2$ ，算出 $c \approx 750$ ，拿得到 $20$ 到 $30$ 分。
:::
### 解法二（大約 $50$ 到 $60$ 分）
:::spoiler 解題思路
接續解法一的想法，採用一種貪心的方法，儘量最小化到達下一塊髒瓷磚的距離。不能每次都算所有的髒瓷磚和目前位置的距離，因為會 TLE ，因此每次移動時可以隨機選擇還沒被清理的其中 $100$ 個瓷磚，看哪個和現在的位置最近，然後移動到該瓷磚。
這樣拿得到 $50$ 到 $60$ 分。
:::
### 解法三（大約 $80$ 到 $90$ 分）
:::spoiler 解題思路
[就是這一題](https://codeforces.com/contest/576/problem/C)。
這樣拿得到 $80$ 到 $90$ 分。
:::
### 解法四（$100$ 分）
:::spoiler 解題思路
前面的解法都用 $x=1$ ，但最佳解並不是優先最小化 $x$ ，而是先最小化 $t$ 。
首先，很容易可以推斷出來 $t$ 的最小值是 $2n-2$ ，只要永遠不往回走就能達到這個最小值。帶入公式後得到 $c=x \times \sqrt[3]{(2n-2)−2n+\frac{17}{8}} = x \times \frac{1}{2}$ 。
接下來，可以推出左上出發和右上出發的機器人其實一開始可以分別被放到右下和左下角，然後路徑倒過來走。這樣簡化了我們需要考慮的情況。
因為 $t$ 被我們設定一定要是最小值，所以左下出發的只能往右或往上移動；右下出發的只能往左或往上移動。如果把髒瓷磚的位置看成一維陣列（先照 $x$ sort 再照 $y$ sort），那前者經過的髒瓷磚形成一個非嚴格遞增序列，後者經過的髒瓷磚形成一個非嚴格遞減序列。
從分數表得知只要 $c \le 100$ ，就能拿到滿分，代表要讓 $x$ 小於等於 $200$ 。因為 $200$ 等於 $\sqrt{2n}$ ，所以我們要想到一種使用小於等於 $\sqrt{2n}$ 臺機器人的分法。
因此可以先求出髒瓷磚的最長遞增子序列（LIS），然後以 LIS 的長度大於 $\sqrt{2k}$ 或小於 $\sqrt{2k}$ 作為分界：
- 如果 LIS 大於 $\sqrt{2k}$ ，其中 $k$ 是目前剩餘的髒瓷磚數量，則放一臺清潔機器人在左下角，然後把 LIS 對應的瓷磚都設為已清潔，再回到步驟一求出新的 LIS 。
- 否則，利用[這個定理](https://usaco.guide/gold/lis#application-2---minimum-number-of-increasing-sequences)推斷出可以把髒瓷磚恰好分割成 $\sqrt{2k}$ 個遞減子序列。
這裡解釋一下為什麼這樣做一定可以在 $200$ 臺內完成清潔：
如果 LIS 大於 $\sqrt{2k}$ ，代表每次選擇完一臺機器放在左下角後，髒瓷磚的數量至少會減少原本 $k$ 塊裡的 $\lfloor \sqrt{2k} \rfloor$ 塊。從 $20000$ 開始往下減的話，減了 $199$ 次就減到 $0$ 了。
否則，因為 Minimum Decreasing Subsequence Cover = $len(LIS)$ ，所以使用的機器人個數（=最長遞增子序列的長度）也是小於 $\sqrt{2k}$ 。
Bonus Challenge: 試著找到一個測資使得 $x$ 恰好等於 $199$ 。
實作的時候，求 LIS 時用一般的 Patience Sort 方法就好了，但要記得再加一個記錄遞增序列的 Parent Array ，這樣才能輸出 LIS 的值。最後求遞減序列時也是使用 Patience Sort 的陣列就可以了。
Edit: 出完題之後找到[這一題](https://codeforces.com/contest/1097/problem/E)類似題，沒想到 Rating 居然有 3400 ，太扯了！
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n;
vector<bool> vis(n, 0);
vector<array<int, 3>> a(n);
for(int i=0;i<n;i++){
int x, y;
cin>>x>>y;
a[i] = {x, y, i};
}
sort(a.begin(), a.end());
vector<pair<bool, vector<int>>> ans;
for(int cnt=0;cnt<n;){
vector<pair<int, int>> lis;
vector<int> plis(n, -1), plds(n, -1);
for(int i=0;i<n;i++){
if(vis[a[i][2]]) continue;
int x=a[i][1];
int ind = upper_bound(lis.begin(), lis.end(), make_pair(x, 1000000))-lis.begin();
if(ind==(int)lis.size()) lis.push_back({x, a[i][2]});
else plds[a[i][2]]=lis[ind].second, lis[ind] = {x, a[i][2]};
if(ind) plis[a[i][2]] = lis[ind-1].second;
}
int k=lis.size();
if(k*k<=2*(n-cnt)){
for(int i=0;i<k;i++){
ans.push_back({1, {}});
for(int j=lis[i].second;j!=-1;j=plds[j]){
vis[j] = 1;
ans.back().second.push_back(j+1);
}
}
break;
}
ans.push_back({0, {}});
cnt+=k;
for(int i=lis.back().second;i!=-1;i=plis[i]){
vis[i] = 1;
ans.back().second.push_back(i+1);
}
}
cout<<ans.size()<<'\n';
for(auto& [b, v]: ans){
cout<<(b?"BR":"TR")<<' '<<v.size()<<' ';
for(int i: v) cout<<i<<' ';
cout<<'\n';
}
return 0;
}
```
:::
## pH - 病毒
### 子任務二（對於所有 $1 \le i \le m$ ， $w_i=1$）
:::spoiler 解題思路
先從節點一做 BFS ，在每一個節點 $i$ 都存與節點一的距離 $dist_i$ 。
可以發現對於每個邊，它所連接的兩個節點 $a$ 跟 $b$ 的距離差 $|dist_a-dist_b|$ 不可能大於 $1$ ，因為如果距離差大於一的話，距離較大的節點在 bfs 時就會被改成距離較小的節點 $+1$ ，它們的差就會變成一了。
瞭解了這個前提之後，就可以發現對於某個邊如果 $dist_a=dist_b$ ，代表病毒會同時擴散到兩節點，因此答案就是 $0.5$ ，否則答案是 $-1$ 。
時間複雜度： $O(n + m)$
:::
### 子任務三（$\sum^m_{i=1}{w_i} \le 2 \times 10^5$）
:::spoiler 解題思路
因為 $\sum w_i \le 2 \times 10^5$ ，所以可以把每個邊都拆成距離等於一的小塊，讓整個圖簡化成子任務二的樣子，也就是每個邊的長度都是一。
時間複雜度： $O(n + \sum w_i)$
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
接續子任務二的想法，把 BFS 改成 Dijkstra's ，發現 $|dist_a-dist_b| \le w_i$ ，然後就看病毒分別擴散到兩節點的時間，如果 $|dist_a-dist_b| = w_i$ 答案是 $-1$ ，否則是 $\frac{1}{2}(w_i+dist_b-dist_a)$ 。
時間複雜度： $O(n + m \: log \: m)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=2e5+5;
vector<pair<int, ll>> adj[mx];
array<ll, 3> edges[mx];
ll dist[mx];
int main(){
cin.tie(0)->sync_with_stdio(0);
memset(dist, 0x3f, sizeof(dist));
int n, m;
cin>>n>>m;
for(int i=0;i<m;i++){
int a, b; ll w;
cin>>a>>b>>w;
a--; b--;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
edges[i]={a, b, w};
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, 0});
dist[0]=0;
while(!pq.empty()){
auto [d, u]=pq.top();
pq.pop();
if(d!=dist[u]) continue;
for(auto [v, w]:adj[u]){
if(d+w<dist[v]){
dist[v]=d+w;
pq.push({dist[v], v});
}
}
}
for(int i=0;i<m;i++){
int a=edges[i][0], b=edges[i][1];
ll w=edges[i][2];
if(abs(dist[a]-dist[b])==w) cout<<"-1\n";
else cout<<fixed<<setprecision(1)<<(w+dist[b]-dist[a])/2.0<<'\n';
}
return 0;
}
```
:::
## pI - 電梯
### 子任務二（$t=1$）
:::spoiler 解題思路
首先，可以從範例測資的解釋發現四臺電梯的操作是獨立的，代表只要這四臺電梯最後有把每個人都載到相對的目標樓層，那全部所花的時間就是四臺裡最久的。
因此，可以把每一樓層都分配到其中一臺電梯，讓那臺電梯負責載那一樓的學生。
以範例測資來說，一到六層樓的學生被分配到第一臺電梯；七、八層樓的學生被分配到第二臺電梯；九、十層樓的學生被分配到第三臺電梯；十一、十二層樓的學生被分配到第四臺電梯。
所以，我們把問題分成兩個步驟：先求出載完這 $12$ 層樓的任一個 subset 的樓層的學生，所需的最少時間，再用求出的值來算出在所有 $4^{12}$ 種分配樓層的方法中，哪一個所需時間最小。
第一個步驟裡，想到 subset 就應該要想到位元 DP ：令 $dp_{S, i, j}$ 為第 $j$ 臺電梯從起始樓層出發，載了 subset $S$ 樓層的學生，並最終停靠在 $i$ 樓所需的最短時間。
初始值為 $dp_{\varnothing, w, 1} = dp_{\varnothing, x, 2} = dp_{\varnothing, y, 3} = dp_{\varnothing, z, 4} = 0$ 。
轉移式為：
$$
dp_{S, a_x, j} = min_{k=1}^{12}(dp_{S \backslash x, k, j}+|k-x|+|x-a_x|)
$$
其中 $S \subseteq \{1, 2, \cdots, 12\}$ 且 $x \in S$ ， $1 \le j \le 4$ 。
接著再定義 $cost_{S, j} = min_{x=1}^{12}(dp_{S, x, j})$ 。
求出來了這個 $cost$ 陣列後，來想第二步驟。
第一個想法是：枚舉所有 $4^{12}$ 種情況並選擇四個裡面的最大值最小的。數學式為：
$$
min_{1 \le p_1, p_2, \cdots, p_{12} \le 4}(max_{k=1}^4(cost_{\{p_i|p_i=k, 1 \le i \le 12\}, k}))
$$
要這樣枚舉求出來的時間複雜度是 $O(4^{12} \times 12) \approx 2 \times 10^8$ ，過得了這個子題。
時間複雜度： $O(2^{12} \times 12^2 \times 4 + 4^{12} \times 12)$
:::
### 子任務三（$t \le 10$）
:::spoiler 解題思路
承子任務二，第二步驟用枚舉求出來的時間複雜度是 $O(4^{12} \times 12)$ , 過不了 $t=10$ 的限制。
因此需要想另一種解法：可以遞迴所有可能性，這樣就省掉了乘以 $12$ 的複雜度，變成是 $O(4^{12}) \approx 1.7 \times 10^7$ ，過得了這個子任務。
時間複雜度： $O(t \times (2^{12} \times 12^2 \times 4 + 4^{12}))$
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
承子任務三，第二步驟用遞迴求出來的時間複雜度是 $O(4^{12})$ , 過不了 $t=100$ 的限制。
因此需要想另一種解法：定義 $ans_{S, i}$ 為前 $i$ 個電梯，被分配到 subset $S$ 的樓層，所需的最小時間。
初始值為： $ans_{S, 1}=cost_{S, 1}$ 。
轉移式為：
$$
ans_{S, i} = min_{T \subseteq S}(max(ans_{T, i-1}, cost_{S \backslash T, i}))
$$
這個 DP 看似還是 $O(4^{12} \times 4)$ ，但因為求所有 subset 的所有 sub-subset 只需要花 $3^n$ 次運算，所以實際上的複雜度為 $O(3^{12} \times 4)$ 。
時間複雜度： $O(t \times (2^{12} \times 12^2 \times 4 + 3^{12} \times 4))$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int dp[1<<12][12][4];
int mp[1<<12][4];
int ans[1<<12][4];
int b[4], a[12];
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
for(int i=0;i<4;i++)cin>>b[i], b[i]--;
for(int i=0;i<12;i++)cin>>a[i], a[i]--;
memset(dp, 0x3f, sizeof(dp));
memset(mp, 0x3f, sizeof(mp));
for(int it=0;it<4;it++){
dp[0][b[it]][it]=0;
for(int i=0;i<(1<<12);i++){
for(int j=0;j<12;j++){
if(!(i&(1<<j)))continue;
for(int k=0;k<12;k++)
dp[i][a[j]][it] = min(dp[i][a[j]][it], dp[i^(1<<j)][k][it]+abs(k-j)+abs(j-a[j]));
}
}
for(int i=0;i<(1<<12);i++)
for(int j=0;j<12;j++)
mp[i][it]=min(mp[i][it], dp[i][j][it]);
}
for(int i=0;i<(1<<12);i++) ans[i][0]=mp[i][0];
for(int it=1;it<4;it++){
for(int i=0;i<(1<<12);i++){
ans[i][it]=mp[i][it];
for(int j=i;j>0;j=(j-1)&i)
ans[i][it]=min(ans[i][it], max(ans[j][it-1], mp[i^j][it]));
}
}
cout<<ans[(1<<12)-1][3]<<'\n';
}
return 0;
}
```
:::
## pJ - 序列
### 子任務二（$n, q \le 2000$）
:::spoiler 解題思路
暴力解。求 $f(S)$ 時可以用 stack 模擬，每次配對到 `()` 時就 `pop` 掉，最後的答案就是那個 stack 的 size 。
時間複雜度：$O(nq)$
:::
### 子任務三（對於所有詢問， $t=2$）
:::spoiler 解題思路
定義陣列 $a$ 為 $a_i = (S_i=$ `(` $) ? 1 : -1$ 。
定義陣列 $p$ 為 $p_0 = 0, p_i = \sum^{i}_{j=1} a_j$ 。
一個 $l$ 到 $r$ 的合法括號序列在陣列 $p$ 中的定義是： $p_{l-1} = p_r = min_{i=l-1}^r(p_i)$ 。也可推理出在加入最少括弧的前提下修復括弧序列的其中一個方法是把要插入的左括弧都放在左邊，把要插入的右括弧都放在右邊。因此再經過一些推理可得： $f(S[l:r]) = p[l-1]+p[r]-2 \cdot min(p[l-1:r])$ ，其中 $min(p[l-1:r])$ 可以用線段樹或稀疏表快速求解。
時間複雜度：$O(n+q \: log \: n)$
:::
### 子任務四（對於所有 $t=1$ 的詢問， $l=r$）
:::spoiler 解題思路
接續子任務三，可以發現如果在位置 $i$ 把一個右括弧改成左括弧，對陣列 $p$ 的影響是 $p[i:n]$ 都減 $2$ ；把一個左括弧改成右括弧，對陣列 $p$ 的影響是 $p[i:n]$ 都加 $2$ 。
因此用線段樹+懶人標記做 Range Add Range Min 就好了。
時間複雜度：$O(n+q \: log \: n)$
:::
### 子任務五（無特殊限制）
:::spoiler 解題思路
接續子任務三、四，先想想看如果對於所有 $t=1$ 的詢問， $r=n$ 要怎麼解。如果題目要反轉 $S[l:n]$ ，對陣列 $p$ 的影響是 $p_i=2 \cdot p_l - p_i$ $(l \le i \le n)$ 。這個也可以用線段樹+懶人標記做 Range Affine Range Min ，但線段樹除了存 min 還要再多存一個 max 值，因為反轉時最大會變成最小；最小會變成最大。最後，想要做 $S[l:r]$ 的反轉，就先反轉 $S[l:n]$ ，再反轉 $S[r+1:n]$ 。
時間複雜度：$O(n+q \: log \: n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int mxn=2e5+5;
struct node{
int mx, mn, a, b;
}t[mxn*4];
int a[mxn];
void push(int v){
t[v*2].a *= t[v].a;
t[v*2].b = t[v*2].b*t[v].a + t[v].b;
t[v*2].mx = t[v*2].mx*t[v].a + t[v].b;
t[v*2].mn = t[v*2].mn*t[v].a + t[v].b;
if(t[v*2].mx < t[v*2].mn) swap(t[v*2].mx, t[v*2].mn);
t[v*2+1].a *= t[v].a;
t[v*2+1].b = t[v*2+1].b*t[v].a + t[v].b;
t[v*2+1].mx = t[v*2+1].mx*t[v].a + t[v].b;
t[v*2+1].mn = t[v*2+1].mn*t[v].a + t[v].b;
if(t[v*2+1].mx < t[v*2+1].mn) swap(t[v*2+1].mx, t[v*2+1].mn);
t[v].a = 1;
t[v].b = 0;
}
void build(int v, int tl, int tr){
if(tl == tr){
t[v].mx = t[v].mn = a[tl];
t[v].a = 1;
t[v].b = 0;
}else{
int tm = (tl+tr)/2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v].mx = max(t[v*2].mx, t[v*2+1].mx);
t[v].mn = min(t[v*2].mn, t[v*2+1].mn);
t[v].a = 1;
t[v].b = 0;
}
}
void update(int l, int r, int a, int b, int v, int tl, int tr){
if(r<tl || tr<l) return;
if(l<=tl && tr<=r){
t[v].a *= a;
t[v].b = t[v].b*a + b;
t[v].mx = t[v].mx*a + b;
t[v].mn = t[v].mn*a + b;
if(t[v].mx < t[v].mn) swap(t[v].mx, t[v].mn);
}else{
push(v);
int tm = (tl+tr)/2;
update(l, r, a, b, v*2, tl, tm);
update(l, r, a, b, v*2+1, tm+1, tr);
t[v].mx = max(t[v*2].mx, t[v*2+1].mx);
t[v].mn = min(t[v*2].mn, t[v*2+1].mn);
}
}
int query(int l, int r, int v, int tl, int tr){
if(r<tl || tr<l) return 1e9;
if(l<=tl && tr<=r) return t[v].mn;
push(v);
int tm = (tl+tr)/2;
return min(query(l, r, v*2, tl, tm), query(l, r, v*2+1, tm+1, tr));
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, q;
string s;
cin>>n>>q>>s;
for(int i=0;i<n;i++)a[i+1]=a[i]+(s[i]=='('?1:-1);
build(1, 0, n);
while(q--){
int t, l, r;
cin>>t>>l>>r;
l--;
if(t==1){
int v = query(l, l, 1, 0, n);
update(l, n, -1, v*2, 1, 0, n);
v = query(r, r, 1, 0, n);
update(r, n, -1, v*2, 1, 0, n);
} else {
int x = query(l, l, 1, 0, n);
int y = query(r, r, 1, 0, n);
int mn = query(l, r, 1, 0, n);
cout<<x+y-mn*2<<'\n';
}
}
return 0;
}
```
:::
## pK - 選舉
### 子任務二（$\sum n \le 100$ 且 $q=1$）
:::spoiler 解題思路
題目裡的人口密度就是陣列區間的平均。
因此枚舉每個區間的所有前綴/後綴的平均，然後將對應的路段塗色就可以了。
時間複雜度：$O(n^4)$
:::
### 子任務三（$\sum n \le 2000$ 且 $q=1$）
:::spoiler 解題思路
承子任務一，因為區間的平均等於總和除以區間長度，所以：
我們利用前綴和先預處理陣列的所有區間的和，然後看 B 黨塗的顏色時，枚舉左界，並對於每個左界看有哪些右界是滿足條件的（其實只需要找到最右邊滿足條件的右界，因為塗色後其他右界較靠左的區間肯定會被包含在這個大區間裡面）。看 R 黨塗的顏色時就反過來。
時間複雜度：$O(n^2)$
:::
### 子任務四（$q=1$）
:::spoiler 解題思路
承子任務二，我們定義陣列 $p$ 為陣列 $a$ 的前綴和陣列，其中 $p_0=0$ ， $p_i=\sum_{k=1}^i a_k$ 。
再來重新定義 $density(l, r)=\frac{p_r-p_{l-1}}{r-(l-1)}$ 。
好巧的是，兩點的斜率公式是 $\frac{y_2-y_1}{x_2-x_1}$ ，如果我們把 $p$ 陣列看成是有 $n+1$ 個點 $(i, p_i)$ ，那平均就等於斜率了！
經過剛才神奇的轉換，我提出一個更神奇的主張：最終藍色路段和紅色路段的數量分別是 $p$ 的下凸包的點數減 $2$ 和上凸包的點數減 $2$ 。~~我已經發現了一個絕妙的證明，但這個頁邊太窄，無法容納（也有可能是因為我太懶），所以就不寫了。~~
因此答案輸出下凸包的點數減 $2$ 和上凸包的點數減 $2$ 。
時間複雜度：$O(n)$
:::
### 子任務五（無特殊限制）
:::spoiler 解題思路
為了能支持動態的凸包，我們先把一開始的上/下凸包分別放到兩個set裡。
每次有人遷移後，對陣列 $p$ 的影響是 $p_k=p_k-x$ 。
對於下凸包，可以看成是加了一個點 $(k, p_k-x)$ ，然後更新set的方法是從新的點往左往右看，把往內凹的點刪掉。
這樣做總共會 insert $O(n+q)$ 個點和 erase $O(n+q)$ 個點，因此時間複雜度為 $O((n+q) \: log \: n)$ 。
但是對於上凸包，不能把人口遷移看成加了一個點，因為新的值比原本的值小，加了也沒用。
而解決的方法是把操作反過來，從最後一個往前做（就變成人口往西方遷移了），這樣對陣列 $p$ 的影響是 $p_k=p_k+x$ ，剩下就跟下凸包的計算方法一樣。
時間複雜度：$O((n+q) \: log \: n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
const ll inf=2e11+7;
set<pair<ll, ll>> s;
void init(int n){
s.clear();
s.insert({-1, -inf});
s.insert({n+1, -inf});
}
ll cross(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c){
return (b.f-a.f)*(c.s-a.s)-(b.s-a.s)*(c.f-a.f);
}
void ins(pair<ll, ll> p){
auto it = s.lower_bound({p.f, -inf});
if(it->f==p.f)it=s.erase(it);
while(it->s>=0 && cross(p, *it, *next(it))>=0)it=s.erase(it);
it--;
while(it->s>=0 && cross(p, *prev(it), *it)>=0)it=s.erase(it), it--;
if(cross(p, *it, *next(it))>0) s.insert(p);
}
int main(){
int t;
cin>>t;
while(t--){
int n, q;
cin>>n>>q;
vector<ll> a(n+1, 0);
vector<pair<int, ll>> qs(q);
vector<pair<int, int>> ans(q);
for(int i=0;i<n;i++)cin>>a[i+1], a[i+1]+=a[i];
for(int i=0;i<q;i++)cin>>qs[i].f>>qs[i].s;
init(n);
for(int i=0;i<=n;i++)ins({i, a[n]-a[i]});
for(int i=0;i<q;i++){
a[qs[i].f]-=qs[i].s;
ins({qs[i].f, a[n]-a[qs[i].f]});
ans[i].s=s.size()-4;
}
init(n);
for(int i=0;i<=n;i++)ins({i, a[i]});
for(int i=q-1;i>=0;i--){
ans[i].f=s.size()-4;
a[qs[i].f]+=qs[i].s;
ins({qs[i].f, a[qs[i].f]});
}
for(auto x:ans)cout<<x.s<<' '<<x.f<<'\n';
}
}
```
:::
Sign in with Wallet
Connect another wallet