# 延平中學 114-1 高中部程式設計競賽題解
[點這裡](https://codeforces.com/contestInvitation/22e2c5e28c20657295b13f9c152fce088d2acbf5)可以找到題目敘述，也可以上傳程式碼。
[計分板連結](https://0x0c5cbae8.github.io/ranking-114-1/)
#### 非常感謝 :
- 陳妙如老師的指導；
- 黃子睿、曾悠然、王宥翔幫忙驗題；
- 黃子睿提供 pC；
- 曾悠然提供 pH；
- [少年圖靈計劃](https://www.tw-ytp.org/)提供比賽的環境和系統！
#### 一些有趣的數據 :
AI 解出的分數（maximum of 3 tries）：
- GPT-5: 1064 / 1100 分
- Grok 4: 1000 / 1100 分
- Gemini 2.5 Pro: 921 / 1100 分
大家推測每一題的 Codeforces Rating:
| 題號 | ChatGPT | 0x0c5cbae8 | rey | 平均 |
| --- | ------- | ---------- | ---- | ---- |
| pA | 800 | 800 | 800 | 800 |
| pB | 800 | 800 | 800 | 800 |
| pC | 900 | 800 | 800 | 833 |
| pD | 800 | 900 | 1000 | 900 |
| pE | 1300 | 1100 | 1100 | 1166 |
| pF | 1400 | 1300 | 1600 | 1433 |
| pG | 1700 | 1600 | 2000 | 1766 |
| pH | 1800 | 1800 | 1800 | 1800 |
| pI | 2100 | 2300 | 2400 | 2266 |
| pJ | 2100 | 2300 | 2400 | 2266 |
| pK | 2100 | 1900 | 2100 | 2033 |
注意這只是整題的難度，有很多題的子任務難度跟整題的差很多。
## pA - DD 上物理課
### 子任務二 （同一字串裡只有質子或只有電子）
:::spoiler 解題思路
因為所有粒子都排斥，所以輸出的時候在每個字元間都加一個空格。
時間複雜度： $O(|S|)$
:::
:::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 n=s.size();
for(int i=0;i<n;i++)cout<<s[i]<<" \n"[i==n-1];
}
return 0;
}
```
:::
### 子任務三（無特殊限制）
:::spoiler 解題思路
從左到右觀察字串的每個字元的時候，看是否跟下一個字元相同，如果相同就多輸出一個空格。
時間複雜度： $O(|S|)$
:::
:::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;
for(int i=0;i<(int)s.size()-1;i++){
cout<<s[i];
if(s[i]==s[i+1])cout<<' ';
}
cout<<s[s.size()-1]<<'\n';
}
return 0;
}
```
:::
## pB - DD 上體育課
### 子任務二（$a=0, b=1, c=0, d=1$）
:::spoiler 解題思路
由於羽球場的範圍是 $0$ 到 $1$，其實沒有可嚴格處於內部的點；只有 4 個頂點：
- `corner`：$(0,0),(0,1),(1,0),(1,1)$
- `outside`：其他所有情況。
因此可直接用 `if` 決定結果。
時間複雜度： $O(t)$
:::
### 子任務三（$a=0, b=2, c=0, d=2$）
:::spoiler 解題思路
整個 $[0,2]\times[0,2]$ 的整數點只有 9 個，可分類如下：
- `corner`：4 個頂點 $(0,0),(0,2),(2,0),(2,2)$
- `border`：4 個邊界點 $(0,1),(1,0),(1,2),(2,1)$
- `inside`：唯一點 $(1,1)$
- `outside`：其他所有情況。
可以用簡單的 if-else 依序判斷。
時間複雜度： $O(t)$
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
一般情況下必須處理任意整數區間 $[a,b]$ 和 $[c,d]$：
- `inside`：$a < x < b$ 且 $c < y < d$
- `outside`：$x<a$ 或 $x>b$ 或 $y<c$ 或 $y>d$
- `corner`：$(x, y)=(a, c)$ 或 $(a, d)$ 或 $(b, c)$ 或 $(b, d)$
- `border`：其他所有情況。
時間複雜度： $O(t)$
:::
:::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 a, b, c, d, x, y;
cin>>a>>b>>c>>d>>x>>y;
if(a<x&&x<b&&c<y&&y<d)cout<<"inside\n";
else if(x<a||b<x||y<c||d<y)cout<<"outside\n";
else if((x==a||x==b)&&(y==c||y==d))cout<<"corner\n";
else cout<<"border\n";
}
return 0;
}
```
:::
## pC - DD 上英文課
### 子任務二 （$n=1$）
:::spoiler 解題思路
只有一個單詞，計算老師和 DD 有多少字元是不一樣的，並設這個數為 $c$ 。
再比較 $c \times x$ 與 $y$，取最小值。
時間複雜度： $O(字串總長度)$
:::
### 子任務三 （$x=1, y=10^9$）
:::spoiler 解題思路
因為修改單個字母成本極低，重寫成本極高，所以對每個單詞，一定選擇逐字修改，而總成本為所有字串裡不同字元的數量。
時間複雜度： $O(字串總長度)$
:::
### 子任務四 （$x=10^9, y=1$）
:::spoiler 解題思路
因為修改每個字母成本極高，重寫單詞成本極低，所以對每個單詞，只要一處錯字就整字重寫，否則不花費。
因此總成本為錯誤單詞的計數乘以 $y$ 。
時間複雜度： $O(字串總長度)$
:::
### 子任務五（無特殊限制）
:::spoiler 解題思路
對每個單詞：
- 計算老師和 DD 有多少字元是不一樣的，並設這個數為 $c_i$ 。
- 比較 $c_i\times x$ 與 $y$ ，取最小。
最後累加所有單詞的最小成本。
時間複雜度： $O(字串總長度)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
int n;
ll x, y;
cin>>n>>x>>y;
vector<string> a(n), b(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
ll ans=0;
for(int i=0;i<n;i++){
int c=0;
for(int j=0;j<(int)a[i].size();j++)
if(a[i][j]!=b[i][j])c++;
ans+=min(x*c, y);
}
cout<<ans<<'\n';
}
return 0;
}
```
:::
## pD - DD 上歷史課
### 子任務二 （$n=1$）
:::spoiler 解題思路
因為只有一行，所以只需要看有沒有漢胡相鄰的，有的話就建牆就可以隔開了。
因此答案就是漢胡相鄰的數量。
時間複雜度： $O(m)$
:::
### 子任務三（無特殊限制）
:::spoiler 解題思路
把子任務二裡一維的想法展開成二維：
一般情況下，對每個格子 $(i,j)$ ：
- 若上鄰 $(i-1,j)$ 存在且不同，則必須蓋一面牆；
- 若左鄰 $(i,j-1)$ 存在且不同，則必須蓋一面牆；
最後肯定就沒有漢胡接壤的地方了。
時間複雜度： $O(nm)$
:::
:::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, m;
cin>>n>>m;
vector<string> a(n);
for(int i=0;i<n;i++)cin>>a[i];
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i>0&&a[i][j]!=a[i-1][j])ans++;
if(j>0&&a[i][j]!=a[i][j-1])ans++;
}
}
cout<<ans<<'\n';
}
return 0;
}
```
:::
## pE - DD 吃營養午餐
### 子任務二（$t \le 100$ 且 $r=1$）
:::spoiler 解題思路
方法數其實就是 $n$ ，所以題目就是問 $n$ 的質因數分解式。
至於分解方法可參照 Zerojudge a010.
時間複雜度： $O(t \cdot n)$
:::
### 子任務三（$r=1$）
:::spoiler 解題思路
方法數其實就是 $n$ ，所以題目就是問 $n$ 的質因數分解式。
至於分解方法可參照下面的程式碼。
時間複雜度： $O(t \sqrt{n})$
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
因為夾第一道菜的時候有 $n$ 種選擇，夾第二道菜的時候剩 $n-1$ 種選擇，夾第三道菜的時候剩 $n-2$ 種選擇...
夾第最後一道菜的時候剩 $n-r+1$ 種選擇。
所以總共的方法數是 $(n) \cdot (n-1) \cdot (n-2) \cdot \: ... \: \cdot (n-r+1)$ 。
至於如何質因數分解這麽大的數，可以發現其實它已經被分解成 $n$ 、$n-1$ 、$n-2$ ... 的數了。
所以只需要分解所有 $n$ 到 $n-r+1$ 的數，然後把所有的質因數分解式都合併，就可以得出答案。
時間複雜度： $O(r \sqrt{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, r;
cin>>n>>r;
vector<int> ans;
for(int i=0;i<r;i++){
int x=n-i;
for(int j=2;j*j<=x;j++){
while(x%j==0){
x/=j;
ans.push_back(j);
}
}
if(x>1)ans.push_back(x);
}
sort(ans.begin(), ans.end());
for(int i=0;i<(int)ans.size();i++)
cout<<ans[i]<<' ';
cout<<'\n';
}
return 0;
}
```
:::
:::spoiler Bonus
這題原本是問 $C^n_r$, 而不是 $P^n_r$ ，但後來因為 $C^n_r$ 有點偏難就改成求 $P^n_r$ 了。你能想到怎麼解原本的嗎？
:::
## pF - DD 上數學課
### 子任務二（add）
:::spoiler 解題思路
因為陣列裡的每個值都出現了 $n-1$ 次（跟每個其他值都配對了一次，共 $n-1$ 次），
因此答案為 $(n-1) \sum_{i=1}^n a_i$ 。
時間複雜度： $O(n)$
:::
### 子任務三（max）
:::spoiler 解題思路
因為答案要求所有數對的總和，所以其實陣列的順序不重要。
因此我們先 sort 整個陣列，這樣取 $\max$ 的時候就是取後面的那個值。
因此答案為 $\sum_{i=1}^n (i-1) a_i$ 。
時間複雜度： $O(n \log n)$
:::
### 子任務四（add2）
:::spoiler 解題思路
直觀來說，答案應該離子任務二 add 的答案 $/2$ 很接近。
而誤差的來源是無條件捨去的時候會減掉一些 $1/2$ 。
所以我們只要數有幾個 $1/2$ 需要扣掉，就能求出答案。
仔細想想，只有在 $a_i+a_j$ 是奇數的時候，才會被扣。
$a_i+a_j$ 是奇數的時候就是 $a_i$ 或 $a_j$ 恰好其中一個是奇數。
而整個陣列裡總共有 $n_{even} \cdot n_{odd}$ 對恰好其中一個是奇數的數對。
其中 $n_{even}$ 代表陣列裡偶數的數量， $n_{odd}$ 代表陣列裡奇數的數量。
因此答案為 $$\frac{ (n-1) \sum_{i=1}^n a_i - n_{even} \cdot n_{odd} }{2}$$
時間複雜度： $O(n)$
:::
### 子任務五（max2）
:::spoiler 解題思路
定義陣列 $b$ ，其中 $b_i$ 為 $\max(a_i, i)$ 。
因此 $\max(a_i, a_j, i, j)=\max(\max(a_i, i), \max(a_j, j))=\max(b_i, b_j)$ 。
就變成子任務三的 max 了。
時間複雜度： $O(n \log n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int mx=2e5+5;
void solve_add(){
int n;
cin>>n;
vector<ll> a(n);
for(int i=0;i<n;i++)cin>>a[i];
ll ans=0;
for(int i=0;i<n;i++)ans+=a[i]*(n-1);
cout<<ans<<'\n';
}
void solve_max(){
int n;
cin>>n;
vector<ll> a(n);
for(int i=0;i<n;i++)cin>>a[i];
sort(a.begin(), a.end());
ll ans=0;
for(int i=0;i<n;i++)ans+=a[i]*i;
cout<<ans<<'\n';
}
void solve_add2(){
int n;
cin>>n;
vector<ll> a(n);
for(int i=0;i<n;i++)cin>>a[i];
ll ans=0, cnt=0;
for(int i=0;i<n;i++)ans+=a[i]*(n-1);
for(int i=0;i<n;i++)cnt+=a[i]%2;
ans-=cnt*(n-cnt);
cout<<ans/2<<'\n';
}
void solve_max2(){
int n;
cin>>n;
vector<ll> a(n);
for(int i=0;i<n;i++)cin>>a[i], a[i]=max(a[i], (ll)i+1);
sort(a.begin(), a.end());
ll ans=0;
for(int i=0;i<n;i++)ans+=a[i]*i;
cout<<ans<<'\n';
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
string op;
cin>>t>>op;
while(t--){
if(op=="add") solve_add();
else if(op=="max") solve_max();
else if(op=="add2") solve_add2();
else if(op=="max2") solve_max2();
}
return 0;
}
```
:::
## pG - DD 上美術課
### 子任務二（$-2 \le x_1, y_1, x_2, y_2 \le 2$）
:::spoiler 解題思路
把平面看成一個圖，整數座標點設為節點，共有 $5 \times 5=25$ 個節點。如果兩個相鄰的格子是屬於同一個十字圖案，則建權重為 $0$ 的邊，若屬於不同十字，則建權重為 $1$ 的邊。
然後使用 bfs 或 Floyd-Warshall 預處理每個座標到座標的距離。
時間複雜度： $O(5^4 + t)$
:::
### 子任務三（$t \le 100$ 且 $0 \le x_1, y_1, x_2, y_2 < 100$）
:::spoiler 解題思路
承子任務二，因為平面太大不能硬暴所有的邊的權重，要找到這些圖案分布的規律。
如果只看每個十字的中央，可以發現他們都滿足 $(x, y) = a \times (1, 2)+b \times (2, -1)$ 。
因此枚舉 $a, b$ ，找到所有在平面上的十字的位置，之後就可以按照這個資訊建邊，最後使用 bfs 尋找答案。
時間複雜度： $O(100^2 \cdot t)$
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
承子任務三，可以發現同一個十字的五個座標節點可以合併為同一個節點，因為邊的權重都是 $0$ 。
合併之後，發現剩下的點和邊連成了一個四方位的網狀系統，而且剩下的邊權重都是 $1$ ，這其實就是一個旋轉過後的二維座標平面。
因此把原本的座標轉換成新的座標 $(x'_1, y'_1)$ 和 $(x'_2, y'_2)$ 後，答案就是 $|x'_1-x'_2|+|y'_1-y'_2|+1$ 。
時間複雜度： $O(t)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<ll, ll> convert(ll x, ll y){
pair<ll, ll> p;
p.first = roundl((x+2*y)/5.0l);
p.second = roundl((2*x-y)/5.0l);
return p;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
ll x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
pair<ll, ll> p1=convert(x1, y1);
pair<ll, ll> p2=convert(x2, y2);
cout<<abs(p1.first-p2.first)+abs(p1.second-p2.second)+1<<'\n';
}
return 0;
}
```
:::
## pH - DD 上生物課
### 子任務二（$m=0$ 且 $n=k$）
:::spoiler 解題思路
這其實就是最基本的背包 DP 問題：背包容量為 $x$ ，物品的重量為 $a$ ，價值為 $b$ 。
定義 $dp_i$ 為重量總和為 $i$ 中，價值總和的最大值。
轉移式為 $dp_{i+a}=\max(dp_{i+a}， dp_i+b)$ 。
最後答案為 $dp$ 陣列的最大值。
時間複雜度： $O(nx)$
:::
### 子任務三（$m=0$）
:::spoiler 解題思路
承子任務二，這個子任務裡我們還需要保證西瓜蟲的使用數量不超過 $k$ 。
因此我們的 $dp$ 還要加一個維度，來存目前有幾個西瓜蟲被使用。
定義 $dp_{i,j}$ 為物品數量為 $i$ ，且重量總和為 $j$ 中，價值總和的最大值。
轉移式為 $dp_{i+1, j+a}=\max(dp_{i+1, j+a}， dp_{i,j}+b)$ 。
最後答案為 $dp_0$ 到 $dp_k$ 所有陣列的最大值。
時間複雜度： $O(nkx)$
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
承子任務三，這個子任務裡我們還需要保證西瓜蟲和企鵝的使用數量差不超過 $k$ 。
最簡單的解法就是把企鵝想成 $-1$ 個物品。
因此承子任務三的轉移式，再加一個 $dp_{i-1, j+c}=\max(dp_{i-1, j+c}， dp_{i,j}+d)$ 。
最後答案為 $dp_{-k}$ 到 $dp_k$ 所有陣列的最大值。
因為這個陣列可能索引會到負數，因此實作的時候可以把整個 $dp$ 陣列往下位移 $m$ 單位，這樣就不會有負數的問題了。
時間複雜度： $O((n+m)^2x)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define chmax(x, y) x=max(x, y)
typedef long long ll;
ll dp[201][2001];
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
int n, m, k, x;
cin>>n>>m>>k>>x;
vector<int> a(n), b(n), c(m), d(m);
for(int i=0;i<n;i++)cin>>a[i]>>b[i];
for(int i=0;i<m;i++)cin>>c[i]>>d[i];
for(int i=0;i<201;i++)
for(int j=0;j<2001;j++)dp[i][j]=-1e18;
dp[m][0]=0;
for(int i=0;i<n;i++)
for(int j=n+m-1;j>=0;j--)
for(int l=0;l<=x-a[i];l++)
chmax(dp[j+1][l+a[i]], dp[j][l]+b[i]);
for(int i=0;i<m;i++)
for(int j=1;j<=n+m;j++)
for(int l=0;l<=x-c[i];l++)
chmax(dp[j-1][l+c[i]], dp[j][l]+d[i]);
ll ans=0;
for(int i=max(0, m-k);i<=min(n+m, m+k);i++)
for(int j=0;j<=x;j++)
chmax(ans, dp[i][j]);
cout<<ans<<'\n';
}
return 0;
}
```
:::
## pI - DD 上社團課
### 子任務二（只有 XOR 的限制）
:::spoiler 解題思路
這個子任務是二分圖的推廣。
把每個限制看成是一條連 $i$ 跟 $j$ 節點的邊，且邊的值為 $k$ 。
如果 $k$ 都是 $1$ 的話，那其實就是問這個圖是否為二分圖。
雖然題目的 $k$ 不一定為 $1$ ，但其實解的方法幾乎跟判斷是否為二分圖一樣，就直接用 dfs 先把節點都掃過一遍，每次到新節點就把他的值設為父節點的值 $\oplus \: k_{edge}$，如果有看到不符合的就是 `-1` ，否則答案就是 dfs 過後的結果。
時間複雜度： $O(n+q)$
:::
### 子任務三、四（所有 $k$ 都 $=1$ 、無特殊限制）
:::spoiler 解題思路
這題需要用到 2-SAT 來解。
首先，可以看出來 $k$ 的每個位元都是獨立的，因此以下我們可以只討論 $k=0$ 或 $1$ 的狀況（ $a_i$ 也變成只能是 $0$ 或 $1$ 。）寫程式時對於每個位元都重複一次就好了。
至於解法，可以把「 $a_i$ 是否為 $1$ 」視為一個布林變數，並把每個限制轉成 2-SAT 的表示法：
- $OR$ $i$ $j$ $1$ $\Rightarrow$ $(i \vee j)$
- $OR$ $i$ $j$ $0$ $\Rightarrow$ $(\neg i \vee \neg i) \wedge (\neg j \vee \neg j)$
- $AND$ $i$ $j$ $1$ $\Rightarrow$ $(i \vee i) \wedge (j \vee j)$
- $AND$ $i$ $j$ $0$ $\Rightarrow$ $(\neg i \vee \neg j)$
- $XOR$ $i$ $j$ $1$ $\Rightarrow$ $(i \vee j) \wedge (\neg i \vee \neg j)$
- $XOR$ $i$ $j$ $0$ $\Rightarrow$ $(i \vee \neg j) \wedge (\neg i \vee j)$
時間複雜度： $O((n+q) \log n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=2e5+5;
vector<int> adj[mx], radj[mx], ord;
bool vis[mx];
int comp[mx], ans[mx];
void dfs(int u){
vis[u]=1;
for(int i:adj[u])if(!vis[i])dfs(i);
ord.push_back(u);
}
void dfs2(int u, int cl){
comp[u]=cl;
for (int i:radj[u])if(!comp[i])dfs2(i, cl);
}
void clear(int n){
n*=2;
for(int i=0;i<n;i++)adj[i].clear(), radj[i].clear();
ord.clear();
fill(vis, vis+n, 0);
fill(comp, comp+n, 0);
}
bool twosat(int n, int k) {
n*=2;
for(int i=0;i<n;i++)if(!vis[i])dfs(i);
int cnt=1;
for(int i=n-1;i>=0;i--)
if(!comp[ord[i]])dfs2(ord[i],cnt++);
for(int i=0;i<n;i+=2){
if(comp[i]==comp[i+1])return 0;
if(comp[i]>comp[i+1])ans[i/2]|=1<<k;
}
return 1;
}
void ae(int a, bool na, int b, bool nb) {
a=a*2^na; b=b*2^nb;
adj[a^1].push_back(b); radj[b].push_back(a^1);
adj[b^1].push_back(a); radj[a].push_back(b^1);
}
void solve(){
int n, q;
cin>>n>>q;
vector<array<int, 3>> qs(q);
vector<char> typ(q);
for(int i=0;i<q;i++){
string s;
cin>>s;
cin>>qs[i][0]>>qs[i][1]>>qs[i][2];
qs[i][0]--; qs[i][1]--;
typ[i]=s[0];
}
bool ok=1;
for(int k=0;k<30;k++){
for(int i=0;i<q;i++){
bool b=(qs[i][2]>>k)&1;
int u=qs[i][0], v=qs[i][1];
if(typ[i]=='A'&&b==0)ae(u,1,v,1);
if(typ[i]=='A'&&b==1)ae(u,0,u,0),ae(v,0,v,0);
if(typ[i]=='O'&&b==0)ae(u,1,u,1),ae(v,1,v,1);
if(typ[i]=='O'&&b==1)ae(u,0,v,0);
if(typ[i]=='X'&&b==0)ae(u,0,v,1),ae(u,1,v,0);
if(typ[i]=='X'&&b==1)ae(u,0,v,0),ae(u,1,v,1);
}
if(!twosat(n, k))ok=0;
clear(n);
}
if(!ok)cout<<"-1\n";
else{
for(int i=0;i<n;i++)cout<<ans[i]<<' ';
cout<<'\n';
}
for(int i=0;i<n*2;i++)ans[i]=0;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}
```
:::
:::spoiler Bonus
如果再加上 $NAND$ , $NOR$ ，和 $XNOR$ 的限制，要怎麼解呢？
:::
## pJ - DD 放學了
### 子任務二（$n, m, q \le 2000$）
:::spoiler 解題思路
先定義一個 $n \times n$ 的二維陣列 `adj` ，如果 $i$ 和 $j$ 是朋友就把 `adj[i][j]` 設為 $1$ 。
詢問的時候看 `adj[a]` 和 `adj[b]` 兩行陣列裡，有幾個索引 $k$ 使得 `adj[a][k]` 和 `adj[b][k]` 都是 $1$ 。
時間複雜度： $O(nq+m)$
:::
### 子任務三（$n, m, q \le 20000$）
:::spoiler 解題思路
解法一：
承子任務二，使用 bitset 存 `adj` 陣列，詢問的時候用 `(adj[a]&adj[b]).count()` 就是答案。
時間複雜度： $O(\frac{nq}{64}+m)$
解法二：
先 sort 所有 adj 陣列，然後用雙指針求解。
時間複雜度： $O(mq)$
:::
### 子任務四（無特殊限制）
:::spoiler 解題思路
先將所有節點按「度數」分為兩類：
- Heavy（重節點）：度數 $> T$
- Light（輕節點）：度數 $\le T$
其中 $T$ 可以大約設為 $\sqrt{m}$ 或一個定值，如 $600$ 。
定義 `adj[u]` 為節點 $u$ 的鄰居列表，並先對每個 $u$ 的 `adj[u]` 陣列排序好。
定義 `hb[h][v] = 1` 代表第 $h$ 個重節點與節點 $v$ 相鄰，用 bitset 存的話，只需要花 $\frac{n^2}{8T}$ 個 Byte 的記憶體。
接下來預處理所有重節點–重節點的共同朋友數量：
對任意 $(h_1,h_2)$，計算 `(hb[h1]&hb[h2]).count()` ，共需約 $\frac{H(H-1)}{2}\times\frac{n}{64}$ 次運算。
對查詢 $(a,b)$ 分情況處理：
- 重節點–重節點：直接查表，$O(1)$。
- 重節點–輕節點：枚舉輕節點相鄰的節點，看是否有在重節點裡面， 時間 $O(\min(\deg(a), \deg(b)))\le T$。
- 輕節點–輕節點：兩個 `adj` 陣列做雙指針，時間 $O(\deg(a)+\deg(b))\le2T$。
時間複雜度： $O((m+q) \sqrt{m} + \frac{n^2}{64})$
:::
:::spoiler 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int mx=200005,T=1000,HMAX=500;
vector<int>adj[mx],hv;
int d[mx],hid[mx],hc[HMAX][HMAX];
bitset<mx>hb[HMAX];
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m, q;
cin>>n>>m>>q;
for(int i=0;i<m;i++){
int u, v;
cin>>u>>v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=0;i<n;i++){
sort(adj[i].begin(),adj[i].end());
d[i]=adj[i].size();
}
int H=0;
memset(hid,-1,sizeof(hid));
for(int i=0;i<n;i++)if(d[i]>T)
hid[i]=H++,hv.push_back(i);
for(int i=0;i<H;i++){hb[i].reset();for(int v:adj[hv[i]])hb[i].set(v);}
for(int i=0;i<H;i++){
hc[i][i]=d[hv[i]];
for(int j=i+1;j<H;j++){
auto tmp=hb[i]&hb[j];
hc[i][j]=hc[j][i]=tmp.count();
}
}
while(q--){
int a,b,ans=0;
cin>>a>>b;
a--;b--;
if(hid[a]>=0&&hid[b]>=0)ans=hc[hid[a]][hid[b]];
else if(hid[a]<0&&hid[b]>=0){
for(int v:adj[a])if(hb[hid[b]][v])ans++;
} else if(hid[a]>=0&&hid[b]<0){
for(int v:adj[b])if(hb[hid[a]][v])ans++;
} else{
int i=0,j=0;
while(i<(int)adj[a].size()&&j<(int)adj[b].size()){
if(adj[a][i]<adj[b][j])i++;
else if(adj[a][i]>adj[b][j])j++;
else{ans++;i++;j++;}
}
}
cout<<ans<<"\n";
}
}
```
:::
:::spoiler Bonus
題解雖然時間複雜度是 $O((m+q) \sqrt{m} + \frac{n^2}{64})$ ，但這題其實有一個真正 $O((m+q) \sqrt{m})$ 的解法，你想得到嗎？
:::
## pK - DD 晚自習
### 子任務二（avg 且 $n \le 2000$）
:::spoiler 解題思路
使用兩個 for 迴圈，存目前的區間總和。
在模運算裡面相除需要用到費馬小定理。
```cpp
// 簡易程式碼
for(int i=0;i<n;i++){
ll x=0;
for(int j=i;j<n;j++){
x=(x+a[j])%mod;
ans=(ans+x*inv[j-i+1])%mod;
}
}
```
時間複雜度： $O(n^2)$
:::
### 子任務三（avg）
:::spoiler 解題思路
因為長度一樣的子陣列，求平均時都是除以相同的數字，因此可以把長度相同的子陣列合倂成一塊計算，最後一起除以長度：
$$\text{答案}=\sum_{i=1}^n \frac{\text{（所有長度為 }i\text{ 的子陣列總和的和）}}{i}$$
其中所有長度為 $i$ 的子陣列總和的和
$$=(a_1+a_2+\dots+a_i)+(a_2+a_3+\dots+a_{i+1})+\dots+(a_{n-i+1}+a_{n-i+2}+\dots+a_n)$$
為了優化計算相同長度的子陣列的方法，可以先求 $a$ 的前綴和陣列 $p$ ，變成：
$$(p_i-p_0)+(p_{i+1}-p_1)+\dots+(p_n-p_{n-i}).$$
可以簡化成：
$$(p_i+p_{i+1}+\dots+p_n)-(p_0+p_1+\dots+p_{n-i}).$$
因此再求 $p$ 的前綴和陣列 $q$ ，變成：
$$(q_n-q_{i-1})-(q_{n-i})$$
就能在 $O(1)$ 内求出。
時間複雜度： $O(n \log n)$
:::
### 子任務四（range 且 $n \le 2000$）
:::spoiler 解題思路
使用兩個 for 迴圈，存目前的區間最大值和最小值。
```cpp
// 簡易程式碼
for(int i=0;i<n;i++){
int mx=-1, mn=1e9;
for(int j=i;j<n;j++){
mx=max(mx, a[j]);
mn=min(mn, a[j]);
ans+=mx-mn;
}
}
```
時間複雜度： $O(n^2)$
:::
### 子任務五（range）
:::spoiler 解題思路
$$\sum_{i=0}^n\sum_{j=i}^nrange([a_i, a_{i+1}, \dots, a_j])$$
$$=\sum_{i=0}^n\sum_{j=i}^n\max([a_i, a_{i+1}, \dots, a_j])-\min([a_i, a_{i+1}, \dots, a_j])$$
$$=\sum_{i=0}^n\sum_{j=i}^n\max([a_i, a_{i+1}, \dots, a_j])-\sum_{i=0}^n\sum_{j=i}^n\min([a_i, a_{i+1}, \dots, a_j])$$
因此可以分開討論 max 跟 min 。以下用 max 作為例子，求 min 的方法也一樣。
假設整個陣列裡最大值的索引為 $i$ ，那可以發現只要包含索引 $i$ 的子陣列，那個子陣列的最大值必定就是 $a_i$ 。
滿足包含索引 $i$ 的子陣列為左界 $l$ 滿足 $1 \le l \le i$ ，且右界 $r$ 滿足 $i \le r \le n$ 。
這樣的子陣列一共有 $i \times (n-i+1)$ 個。
也就是説，答案需要被加上 $i \times (n-i+1) \times a_i$ 。
至於剩下的子陣列，可以發現它們都滿足 $1 \le l \le r < i$ 或 $i < l \le r \le n$ 。
所以可以遞迴下去，找 $[1, i-1]$ 和 $[i+1, n]$ 的最大值，數有幾個子陣列有包含最大值，以此類推。
找最大值的時候可以用一個線段樹，或是使用 Cartesian Tree 預處理。
時間複雜度： $O(n)$
:::
:::spoiler 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int mx=2e5+5;
ll exp(ll a, ll b){
ll ans=1;
while(b){
if(b%2) ans=ans*a%mod;
a=a*a%mod;
b/=2;
}
return ans;
}
void solve_avg(){
int n;
cin>>n;
vector<ll> a(n+1);
for(int i=1;i<=n;i++)cin>>a[i], a[i]=(a[i]+a[i-1])%mod;
for(int i=1;i<=n;i++)a[i]=(a[i]+a[i-1])%mod;
ll ans=0;
for(int i=1;i<=n;i++){
ll cur=(a[n]-a[i-1]-a[n-i]+mod+mod)%mod;
ans=(ans+cur*exp(i, mod-2))%mod;
}
cout<<ans<<'\n';
}
int l[mx], r[mx];
ll a[mx], ans;
int dfs(int u){
int ls=l[u]==-1?0:dfs(l[u]);
int rs=r[u]==-1?0:dfs(r[u]);
ans+=a[u]*(ls+1)*(rs+1);
return ls+rs+1;
}
ll cartesian(int n, int t) {
for(int i=0;i<n;i++)l[i]=-1, r[i]=-1;
ans=0;
vector<int> st;
for(int i=0;i<n;i++){
int lst=-1;
while(!st.empty()&&(t*a[st.back()]<=t*a[i])){
lst=st.back();
st.pop_back();
}
l[i]=lst;
if(!st.empty())r[st.back()]=i;
st.push_back(i);
}
dfs(st.front());
return ans;
}
void solve_range(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
cout<<cartesian(n, 1)-cartesian(n, -1)<<'\n';
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;
string op;
cin>>t>>op;
while(t--){
if(op=="avg") solve_avg();
else if(op=="range") solve_range();
}
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet