---
# System prepended metadata

title: 延平中學 114-1 高中部程式設計競賽題解

---

# 延平中學 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$ ，這其實就是一個旋轉過後的二維座標平面。

![cross](https://hackmd.io/_uploads/SJizlPsIex.jpg)

因此把原本的座標轉換成新的座標 $(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;
}
```
:::
