APCS 11011 實作題題解
==

## P1
- [link](https://zerojudge.tw/ShowProblem?problemid=g595)
#### 題意
給定一個陣列，有些位置為 0，將所有為 0 的位置填上左右相鄰值的 min，求填完後陣列總和。

#### 題解
基礎實作題，照題目規則填數字即可，遇到 0 填上左右的 min。

#### 需注意的點
- 此題為基礎語法題，考驗基礎語法
- 注意只有一個鄰居，也就是陣列頭尾為 0 的情況。
#### 範例解答

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int maxn = 100005;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int>v(n);
    int sum = 0;
    for (auto &i : v) {
        cin >> i;
    }
    if (v[0] == 0) {
        v[0] = v[1];
        sum += v[0];
    }
    if (v[n - 1] == 0) {
        v[n - 1] = v[n - 2];
        sum += v[n - 1];
    }
    for (int i = 1 ; i < n - 1 ; i++) {
        if (!v[i]) {
            v[i] = min(v[i - 1], v[i + 1]);
            sum += v[i];
        }
    }
    cout << sum << '\n';
}

## P2
- [link](https://zerojudge.tw/ShowProblem?problemid=g596)
#### 題意
題目給定 n×m 的矩形，使用木樁和線來排動線，有下列兩種操作

加入木樁 r c 0
加一木樁在 (r,c), 並且向他的上下左右盡量找離最近的木樁連線, 若 (r,c) 有線經過則先將線拆掉後再來連線
移除木樁 r c 1
把位於 (r,c) 的木樁拔掉, 並把與他相關線拔掉, 保證 (r,c) 上一定有木樁
總共有 h 次操作，輸出過程中有線和有木樁佔據空間的面積最大是多少, 以及 h 次操作後有線和有木樁佔據空間的面積

#### 題解
進階實作題，依然是照題目需求實作，但是此題的實作十分複雜，下列為一建議寫法。
分別用陣列紀錄此格是否有橫線, 直線, 木樁。
將直線橫線分開紀錄的原因，將通過某格的直線拆掉，該格可能還有橫線，如以下 case。
remove(4, 3)
_ _ @ _ _
@ * * * @
_ _ * _ _
_ _ @ _ _
可發現 (2, 3) 的直線被移除，但仍有橫線
- 加入木樁
- 將該點設為有木樁。
- 將該點的直線, 橫線移除。
- 找到上下鄰居, 路徑上加入直線。
- 找到左右鄰居, 路徑上加入橫線。
- 移除木樁
- 將該點設為無木樁。
- 將該點的直線, 橫線移除。
- 找到上下鄰居, 路徑上直線移除。
- 找到左右鄰居, 路徑上橫線移除。

#### 需注意的點
- 此題進階語法題，考點為進階的實作與語法，開始實作前務必熟讀題目了解題意並確實想清楚實作流程。
- 四個方向找鄰居的流程相似，可寫成迴圈精簡 code。
- 實作過程中有很多細節，如找鄰居超界，橫線直線的加入移除順序流程。
#### 範例解答

#include <bits/stdc++.h>
using namespace std;
int b[105][105];
int line[105][105][2];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, h;
    cin >> n >> m >> h;
    int maxv = 0;
    for (int i = 0 ; i < h ; i++) {
        int x, y, op;
        cin >> x >> y >> op;
        if (!op) {
            b[x][y] = 1;
            line[x][y][0] = line[x][y][1] = 0;
            for (int j = 0 ; j < 4 ; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                while (nx >= 0 && nx < n && ny >= 0 && ny < m && !b[nx][ny]) {
                    nx += dx[j];
                    ny += dy[j];
                }
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    int px = x + dx[j];
                    int py = y + dy[j];
                    while (px != nx || py != ny) {
                        line[px][py][j % 2] = 1;
                        px += dx[j];
                        py += dy[j];
                    }
                }
            }
        }
        else {
            b[x][y] = 0;
            for (int j = 0 ; j < 4 ; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                while (nx >= 0 && nx < n && ny >= 0 && ny < m && !b[nx][ny]) {
                    nx += dx[j];
                    ny += dy[j];
                }
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    int px = x + dx[j];
                    int py = y + dy[j];
                    while (px != nx || py != ny) {
                        line[px][py][j % 2] = 0;
                        px += dx[j];
                        py += dy[j];
                    }
                }
            }
        }


        int cur = 0;
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j < m ; j++) {
                if (b[i][j] || line[i][j][0] || line[i][j][1]) {
                    cur++;
                }
            }
        }
        maxv = max(maxv, cur);
    }
    int ans = 0;
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < m ; j++) {
            if (b[i][j] || line[i][j][0] || line[i][j][1]) {
                ans++;
            }
        }
    }
    cout << maxv << '\n' << ans << '\n';
}

## P3.生產線
- [link](https://zerojudge.tw/ShowProblem?problemid=g597)
#### 題意
n 台機器排成一直線, 每一個機器有 t[i], 代表該台機器要產出一單位的資料需要 t[i] 單位的時間
有 m 個工作要完成, 每一個工作都需要第 [l[i],r[i]] 的機器各生產出 w[i] 單位資料
可任意調換 n 台機器的順序, 目標是使得這 m 個工作做完的總時間要最小，輸出最小的總時間
#### 題解
#### 區間加值 :
- 方法一 : 暴力 for 迴圈填入
單次複雜度為 O(N)
可通過最小 30% 的測資
- 方法二 : 應用差分陣列
差分陣列第 i 項表示原陣列第 i 項與第 i - 1 項的差。
ex :
原陣列 : 1 2 5 -2 7
差分陣列 : 0 1 1 3 -7 9
可發現原陣列即為差分陣列的前綴和。

那當我們要將一段連續區間 (l, r) 都 +k 時，差分陣列僅會在 l, r + 1 兩個位置產生改變
ex : 2~4 +3
原陣列 : 0 3 3 3 0
差分陣列 : 0 0 3 0 0 -3
每次修改僅需更改差分陣列的兩個位置，最後再做前綴和即可得到每台機器需產出的資料量
單次複雜度為 O(1)
可得到此題滿分
#### 排序機器 :
直覺的 Greedy，需要資料量多的使用所需時間較少的機器，將機器所需時間從小到大排，所需資料由大到小排，一對一對應即可算出答案。
#### 需注意的點
- 注意 overflow，需使用 long long。
- 差分陣列通常使用 1-base，最後計算加總時須注意正確的位置對應。
#### 範例解答

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<long long>pre(n + 5);
    for (int i = 0 ; i < m ; i++) {
        int l, r, w;
        cin >> l >> r >> w;;
        pre[l] += w;
        pre[r + 1] -= w;
    }
    for (int i = 1 ; i <= n ; i++) {
        pre[i] += pre[i - 1];
    }
    vector<long long>num(pre.begin() + 1, pre.begin() + n + 1);
    sort(num.begin(), num.end());
    vector<long long>t;
    for (int i = 1 ; i <= n ; i++) {
        long long x;
        cin >> x;
        t.push_back(x);
    }
    sort(t.rbegin(), t.rend());
    long long ans = 0;
    for (int i = 0 ; i < n ; i++) {
        ans += t[i] * num[i];
    }
    cout << ans << '\n';
}

## P4
- [link](https://zerojudge.tw/ShowProblem?problemid=g598)
#### 題意
有 n 個人員, 將這些人分成 A 和 B 兩組, 初始有 m 個 pair 表示每個 pair 兩人之間屬於不同組, 接著有 p 個調查員, 每個調查員都會回傳恰好 k 個 pair 的資料回來，表示這些 pair 之間屬於不同組

有些調查員回傳的資料是錯誤的，表示他回傳的 k 個 pair 和初始 m 個 pair 會產生矛盾, 將回傳錯誤結果的調查員找出來, 至少一個至多三個。

輸入保證若調查員的 k 個 pair 和初始 m 個 pair 不會產生矛盾, 這些資料一定和原本分組吻合
#### 題解
#### 二分圖
為此題的先備知識，二分圖即為一張無向圖，可將點分成兩堆，使得同堆點間沒有邊，此也為著名的著色問題，，判斷一圖是否為二分圖為 O(n + m)，也就是可用 DFS, BFS 稍作修改求解，可參考以下程式碼。

include <bits/stdc++.h>
using namespace std;

vector<int>g[200000];
int c[200000];
void dfs(int now, int cc) {
    for (auto &i : g[now]) {
        if (~c[i]) {
            if (c[i] == c[now]) {
                cout << "NO" << '\n';
                exit(0);
            }
        }
        else {
            c[i] = cc ^ 1;
            bfs(i, c[i]);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    memset(c, -1, sizeof(c));
    for(int i= 0 ; i < m ; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    c[1] = 0;
    dfs(1, 1);
    cout << "YES\n";
}

#### 做法 1
暴力對 k 個觀察員分別求解，將每個觀察員的邊一一加入原圖，判斷圖是否為二分圖。
複雜度為 $O((n + m) * p)$
在有好的實作下，此做法有機會拿到滿分。
#### 做法 2
題目有兩個關鍵條件
- 輸入保證若調查員的 k 個 pair 和初始 m 個 pair 不會產生矛盾, 這些資料一定和原本分組吻合
- 錯誤的調查員至少一個至多三個

不會產生矛盾，表示若 x, y, z 為未發生矛盾的觀察員，將他們的邊同時加入也會為二分圖，只有當加入的邊有包含發生矛盾的觀察員，原圖才會變為非二分圖，可使用二分搜的技巧大量減少需要 DFS 判二分圖的次數，首次二分搜找到最小 index 的矛盾觀察員，找到一個矛盾觀察員僅需判二分圖 log n 次，參考以下 psuedo code。
複雜度為 $O((n + m) * \log n)$

vector<int>ans;
int L = 0;
for (int i = 0 ; i < 3 ; i++) {
    if (check(L, k - 1)) { // 加入這些觀察員是否為二分圖
        break;
    }
    int l = L - 1, r = k - 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (check(L, mid)) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    ans.push_back(r);
    L = r + 1;
}

#### 做法 3
可還原 disjoint set
#### 需注意的點
- 判二分圖須對每個連通塊皆做判斷
- 加入觀察員的邊後做完二分圖判斷需記得移除
- 此題二分搜邊界較為複雜，設定邊界時需注意
#### 範例解答

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20005;
vector<int>g[maxn];
vector<pair<int,int>>v[maxn];
int n, m, p, k;
int color[maxn];
bool dfs(int now) {
    int f = 1;
    for (auto &i : g[now]) {
        if (~color[i]) {
            if (color[i] == color[now]) {
                return 0;
            }
            continue;
        }
        color[i] = 1 - color[now];
        f &= dfs(i);
    }
    return f;
}
bool check(int l, int r) {
    int f = 1;
    for (int i = l ; i <= r; i++) {
        for (auto &j : v[i]) {
            g[j.first].push_back(j.second);
            g[j.second].push_back(j.first);
        }
    }
    fill(color, color + n, -1);
    for (int i = 0 ; i < n ; i++) { // 判二分圖
        if (color[i] == -1) {
            color[i] = 0;
            f &= dfs(i);
            if (!f) {
                break;
            }
        }
    }
    for (int i = l ; i <= r; i++) {
        for (auto &j : v[i]) {
            g[j.first].pop_back();
            g[j.second].pop_back();
        }
    }
    return f;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0 ; i < m ; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> p >> k;
    for (int i = 1 ; i <= p ; i++) {
        for (int j = 0 ; j < k ; j++) {
            int a, b;
            cin >> a >> b;
            v[i].push_back({a, b});
        }
    }
    int L = 1;
    for (int i = 0 ; i < 3 ; i++) {
        if (check(L, p)) { // 加入這些觀察員是否為二分圖
            break;
        }
        int l = L - 1, r = p ;
        while (r - l > 1) {
            int mid = (l + r) >> 1;
            if (check(L, mid)) {
                l = mid;
            }
            else {
                r = mid;
            }
        }
        cout << r << '\n';
        L = r + 1;
    }
}