# APCS 2021.11.07
###### tags: `APCS`
> [name=peienwu]
> [name=thanksone]
> [time=Sun, Nov 7, 2021 8:06 PM]

---

## 原文網址：https://peienwu.com/apcs2111/

---

## P1 修補圍籬
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g595)

### 題解

如果在兩端就直接取旁邊的高度，否則取跟左右邊高度的最小值。

### 時間複雜度
$O(n)$
### AC程式碼

#include <bits/stdc++.h>
#define int long long
#define N 105
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,A[N];

signed main(){
    IOS;
    cin>>n;
    for(int i=0;i<n;i++)cin>>A[i];
    int ans = 0;
    if(A[0] == 0)ans += A[1];
    if(A[n-1] == 0)ans += A[n-2];
    for(int i=1;i<n-1;i++){
        if(A[i] == 0)ans += min(A[i-1],A[i+1]);
    }
    cout<<ans<<endl;
}

>[name=peienwu]

## P2 動線安排(魔王題)

[題目連結](https://zerojudge.tw/ShowProblem?problemid=g596)

### 題解
把線分成橫的跟直的就可以好好處理交叉了!
### 時間複雜度
$O(h(n + m))$
### AC程式碼

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0, ans = 0;
array<array<int, 104>, 104> R, C, I;
void add(int r, int c){
    bool ok;
    I[r][c] = 1;
    cnt++;
    if(C[r][c] || R[r][c]) cnt--;
    C[r][c] = R[r][c] = 0;
    ok = 0;     //直下情況
    for(int i = r + 1; i < n; i++){
        if(I[i][c]) ok = 1;
    }
    if(ok){
        for(int i = r + 1; i < n; i++){
            if(I[i][c] || R[i][c]) break;
            R[i][c]++;
            cnt += C[i][c] == 0;
        }
    }
    ok = 0;     //直上情況
    for(int i = r - 1; i >= 0; i--){
        if(I[i][c]) ok = 1;
    }
    if(ok){
        for(int i = r - 1; i >= 0; i--){
            if(I[i][c] || R[i][c]) break;
            R[i][c]++;
            cnt += C[i][c] == 0;
        }
    }
    ok = 0;     //橫右情況
    for(int i = c + 1; i < m; i++){
        if(I[r][i]) ok = 1;
    }
    if(ok){
        for(int i = c + 1; i < m; i++){
            if(I[r][i] || C[r][i]) break;
            C[r][i]++;
            cnt += R[r][i] == 0;
        }
    }
    ok = 0;     //橫左情況
    for(int i = c - 1; i >= 0; i--){
        if(I[r][i]) ok = 1;
    }
    if(ok){
        for(int i = c - 1; i >= 0; i--){
            if(I[r][i] || C[r][i]) break;
            C[r][i]++;
            cnt += R[r][i] == 0;
        }
    }
}
void pull(int r, int c){
    I[r][c] = 0;
    cnt--;
    for(int i = r + 1; i < n; i++){     //直下情況
        if(!R[i][c]) break;
        R[i][c]--;
        cnt -= C[i][c] == 0;
    }
    for(int i = r - 1; i >= 0; i--){    //直上情況
        if(!R[i][c]) break;
        R[i][c]--;
        cnt -= C[i][c] == 0;
    }
    for(int i = c + 1; i < m; i++){     //橫右情況
        if(!C[r][i]) break;
        C[r][i]--;
        cnt -= R[r][i] == 0;
    }
    for(int i = c - 1; i >= 0; i--){    //橫左情況
        if(!C[r][i]) break;
        C[r][i]--;
        cnt -= R[r][i] == 0;
    }
}
signed main(){
    int h, r, c, t;
    cin >> n >> m >> h;
    while(h--){
        cin >> r >> c >> t;
        if(t){
            pull(r, c);
        }else{
            add(r, c);
        }
        ans = max(ans, cnt);
    }
    cout << ans << "\n" << cnt;
    return 0;
}

> [name=thanksone]

## P3 生產線

[題目連結](https://zerojudge.tw/ShowProblem?problemid=g597)

### 差分作法

#### 題解
用差分的想法加值，再用前綴還原，最後再排序。最後利用Greedy的想法，將每一項最小的工作量乘上最大的時間，總和即為答案。

:::info
**差分**

差分是前綴和的逆運算，也就是說，把兩項的差算出來就是差分。定義如下：
$$b_i = \begin{cases}a_i-a_{i-1}, &\text{if }i\gt 1 \\a_1, & \text{if } i = 1\end{cases}$$

差分的使用時機是區間加值，一個區間內的數字都加上一個定值，這時候就可以使用到差分的技巧。使用方式如下，當我要在區間 $[l,r]$ 的每一個數字都加上一個值$v$，以下步驟：
1. 定義一個新的陣列 $b_i$ 表示每一項差分
2. 設 $b_l = b_l+v$，$b_{r+1} = b_{r+1}-v$
3. 將差分的每一項加上前一項（做前綴和 $b_i = b_i+b_{i-1}$），即為原數列

第二步驟可以重複好幾次做，這樣複雜度從原本的$O(n)$就變成了$O(1)$了！
:::

#### 時間複雜度
差分：$O(m)$ 、排序 $O(n\log n)$

總時間複雜度：$O(n\log n + m)$

#### AC程式碼

#include <bits/stdc++.h>
#define int long long
#define N 200005
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,m,A[N],B[N];

signed main(){
    IOS;
    memset(A,0,sizeof(A));
    cin>>n>>m;
    while(m--){
        int x,y,w;cin>>x>>y>>w;
        A[x] += w;
        A[y+1] -= w;
    }
    for(int i=1;i<=n;i++)cin>>B[i];
    for(int i=1;i<=n;i++)A[i] = A[i] + A[i-1];
    sort(A+1,A+n+1);
    sort(B+1,B+n+1);
    int ans = 0;
    for(int i=1;i<=n;i++){
        ans += A[i] * B[n-i+1];
    }
    cout<<ans<<endl;
}

> [name=peienwu]

### 線段樹作法


很奇怪，最近兩次的APCS第三題都有人想要砸資結，特別是線段樹，可能有些人特別偏愛線段樹吧！

#### 題解

線段樹最原本的應該是區間詢問、單點修改，如果要區間修改的話就會用到[懶標](https://peienwu.com/seg1)，所以實作上相對上比較複雜一點。這一題用線段樹的目的是區間加值，加值完過後的排序以及Greedy跟差分的作法是一樣的，用線段樹真的是多此兩舉（實作較複雜、較耗時）！

當然，這一題比較特別只有最後一起做單點查詢，因此不用懶標，最侯直接計算一路去經過的答案也行！下面的程式碼就是把完全包含區間的節點加值，不用使用到懶標，最後一次查詢。

#### 時間複雜度

區間加值 $O(m\log n)$，n個點的詢問 $O(n\log n)$，排序 $O(n\log n)$

總時間複雜度：$O((n+m)\log n)$

#### AC程式碼

#include <bits/stdc++.h>
#define int long long
#define N 200005
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,m,t,A[N],B[N],ans = 0;

struct node{
    int val = 0,sz;
}seg[4*N];

void build(int id,int l,int r){
    seg[id].sz = r - l;
    if(r - l <= 1)return;
    int mid = (l + r) / 2;
    build(id*2,l,mid);
    build(id*2+1,mid,r);
}
void modify(int id,int l,int r,int ql,int qr,int val){
    if(r <= l || r <= ql || l >= qr)return;
    if(ql <= l && qr >= r){
        seg[id].val += val;
        return;
    }
    int mid = (l + r) / 2;
    modify(id*2,l,mid,ql,qr,val);
    modify(id*2+1,mid,r,ql,qr,val);
}
void query(int id,int l,int r,int val){
    if(r <= l)return;
    ans += seg[id].val;
    if(r - l == 1)return;
    int mid = (l + r) / 2;
    if(val < mid)return query(id*2,l,mid,val);
    else return query(id*2+1,mid,r,val);
}

signed main(){
    IOS;
    cin>>n>>m;
    build(1,1,n+1);
    while(m--){
        int x,y,w;cin>>x>>y>>w;
        y++;
        modify(1,1,n+1,x,y,w);
    }
    for(int i=1;i<=n;i++){
        ans = 0;query(1,1,n+1,i);
        A[i] = ans;
    }
    for(int i=1;i<=n;i++)cin>>B[i];
    
    sort(A+1,A + n + 1);
    sort(B+1,B + n + 1);
    int ans = 0;
    for(int i=1;i<=n;i++)ans += A[i] * B[n-i+1];
    cout<<ans<<endl;
}

## P4 真假子圖

[題目連結](https://zerojudge.tw/ShowProblem?problemid=g598)

### 二分搜尋+DFS作法

#### 題解

一開始看到這題，應該很難通靈出二分搜這個作法（我覺得光把題目看懂就有點難度了）。這題有一個條件要特別注意：

> 保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合
>
這一題每一個觀察員並可看成不是獨立的（假如一個觀察員不產生矛盾，則他回傳的那一些邊都會被沿用），所以題目 $p$ 筆詢問可以聯集一起處理。

將情報員當成點，合作關係當成邊，那麼合法的圖就會有兩個點集，點集中的點互不相鄰，也就是二分圖。

二分搜第一個使得圖變得不二分的人，把它消失，**最多重複3次**就做完了。

:::info
**為什麼可以二分搜？**
二分搜是用來找一串01字串的分界點，並且必須具有單調性才能二分搜。這一題之所以會有單調性是因為，當我查詢觀察員 $P_i$ 的回傳資料是否正確時，會將前面 $P_1$ 到 $P_{i-1}$ 觀察員回傳的所有邊納入考慮。

假設有一個觀察員 $P_j (1\le j < i)$ 回傳的資料是錯誤的，這些邊會導致整張圖變成非二分圖，對於 $j$ 後面的所有點來說，都是非二分圖。這樣就有了以 $j$ 為分界點的單調性，即可二分搜。

:::

二分圖判斷可以用 $dfs$ 做，$dfs$ 的時候把每個點塗上顏色，如果相鄰的點跟自己顏色一樣就表示這不是一張二分圖。

#### 時間複雜度

$O((n + m + pk)\log p)$

#### AC程式碼

#include <bits/stdc++.h>
#define pb push_back
#define mid (l + r) / 2
using namespace std;
struct e{
    int u, v;
};
int n;
array<bool, 10004> WA;          //不可行的觀察員編號
array<int, 20004> vis;          //DFS是否走訪、二分圖顏色
array<vector<e>, 10004> E;      //每一個觀察員的回傳邊
array<vector<int>, 20004> G;    //存進行DFS的圖

bool dfs(int u, int t){         //用DFS塗色、判斷二分圖
    if(vis[u]) return 1;
    bool ans = 1;
    vis[u] = t;
    for(int v : G[u]){
        if(vis[v] == t) return 0;
        ans &= dfs(v, 3 - t);
    }
    return ans;
}

bool check(int p){               //檢查第p個觀察員回傳是否正確
    bool ans = 1;
    for(int i = 0; i < n; i++){
        G[i].clear();
        vis[i] = 0;
    }
    for(int i = 0; i <= p; i++){
        for(auto [u, v] : E[i]){ //將觀察員的邊推入G
            G[u].pb(v);
            G[v].pb(u);
        }
    }
    for(int i = 0; i < n; i++){
        ans &= dfs(i, 1);        //將每一個連通塊
    }
    return ans;
}
void BS(int l, int r){           //二分搜觀察員
    if(check(r)) return;         //當邊的連集不會讓圖有問題，則回傳
    while(l != r){
        if(check(mid)) l = mid + 1;
        else r = mid;
    }
    WA[l] = 1;
    E[l].clear();                //剔除一錯誤觀察員
}
signed main(){
    int m, p, k, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        E[0].pb({a, b});
    }
    cin >> p >> k;
    for(int i = 1; i <= p; i++){
        for(int j = 0; j < k; j++){
            cin >> a >> b;
            E[i].pb({a, b});
        }
    }
    for(int i = 0; i < 3; i++){     //至多三個觀察員
        BS(0, p);
    }
    for(int i = 1; i <= p; i++){
        if(WA[i]) cout << i << "\n";
    }
    return 0;
}

> [name=thanksone]

### DSU作法

> Idea From [name=Kennyfs]

#### 題解

這一題的題目限制有說最多3個錯誤的情報員，因此我們可以用上面二分搜的方式做三次找到答案。如果題目**不限制錯誤調查員的數量**，也就是用二分搜時間會超時，但是用DSU可以在線性時間內完成！

DSU的目的在處理集合問題，根據下面這個關鍵條件：

> 保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合

我們只要對每一筆詢問看會不會與組長手中的pair矛盾即可。如果每一次都做DFS，會發現時間複雜度是 $O(pn)$，必然超時。

DSU的想法是，我們將組長手中的圖中上每一個連通塊都分別塗上兩種顏色（必為二分圖，因此將兩邊各塗上不同顏色）。接著，把每個顏色當作初始的並查集中的集合，將每一筆觀察員回傳的邊的兩端指向的集合合併起來，過程中如果發生邊的兩端同屬一個集合，表示這是一個錯誤的觀察員。做完每一個觀察員之後，把所有變更過的還原成初始狀態（組長手中的圖）即可。

:::info
**舉例**
> 8 5
> 0 2 1 3 1 2 4 6 5 6
> 1 2
> 1 4 0 6

整個過程就是下面這張GIF：

步驟：
1. 利用DFS為組長手中的圖上色，每一個連通塊兩色（以編號1,2,3...）
2. 將每一個顏色當作並查集元素
3. 觀察員輸入的邊兩端（u,v）非同色，表示不發生矛盾，則將u所在集合與v所在集合的對方（連通塊兩色的另一色）合併
4. 重複 3. 共k次，如果發生（u,v）為同一色，則觀察員錯誤。
:::

#### 時間複雜度

$O(n + pk\alpha)$

#### AC程式碼

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define int long long
#define N 20005
#define M 10005
using namespace std;
int n,m,p,k;
int color[N],boss[N],num[N];
bool WA[M],f;
int other(int s){return (s%2)?s+1:s-1;} //other為同一連通塊另外一種顏色
vector<int> edge[N],change;

void init(){                            //初始化
    memset(color,0,sizeof(color));
    memset(WA,0,sizeof(WA));
}
void dfs(int id,int col){           //對所有點上色
    color[id] = col;
    for(auto i:edge[id]){
        if(!color[i])dfs(i,other(col));
    }
}
int find_boss(int id){              //尋找祖先、及路徑壓縮
    if(boss[id] == id)return id;
    change.push_back(id);
    return boss[id] = find_boss(boss[id]);
}

signed main(){
    IOS;
    init();
    cin>>n>>m;
    while(m--){
        int x,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    int now = 1;
    for(int i=0;i<n;i++){           //對所有點上色
        if(!color[i]){
            dfs(i,now);now += 2;
        }
    }
    for(int i=1;i<=now;i++){boss[i] = i;num[i] = 1;}
    cin>>p>>k;
    for(int i=1;i<=p;i++){
        change.clear();                                  //儲存待更改的點集
        f = 0;
        for(int j=0;j<k;j++){
            int x,y;cin>>x>>y;
            if(f)continue;
            x = color[x],y = color[y];                   //尋找邊兩端點的顏色所處的集合
            int bx =  find_boss(x),by = find_boss(y);
            int ox = find_boss(other(y)),oy = find_boss(other(x));
            if(bx == by){WA[i] = 1;f = 1;continue;}     //位於同一集合，此觀察員是錯的
            //以下是啟發式合併（小的集合並到大的集合）
            if(num[bx] < num[ox]){
                boss[bx] = ox;num[ox] += num[bx];
                change.push_back(bx);
            }
            else{
                boss[ox] = bx;num[bx] += num[ox];
                change.push_back(ox);
            }
            if(num[by] < num[oy]){
                boss[by] = oy;num[oy] += num[by];
                change.push_back(by);
            }
            else{
                boss[oy] = by;num[by] += num[oy];
                change.push_back(oy);
            }
        }
        for(auto i : change){boss[i] = i;num[i] = 1;}   //觀察員的邊結束，看完後復原
    }
    for(int i=1;i<=p;i++)if(WA[i])cout<<i<<endl;        //輸出最後錯誤觀察員答案
}

>[name=peienwu]