Day 3 上機題解
===

###### tags:`IONCAMP2019`

[同溫層](https://pc2.tfcis.org/dev/index.php/problem/view/49)
---
+ Disjoint Set ( 互斥集 )
1. 建立 Disjoint Set
2. 若 $u, v$ 相連, 則 $\operatorname{Union}(u,v)$
3. 輸出 "與 $k$ 點相同 Set 的點的數量"

#include <bits/stdc++.h>

using namespace std;

struct Disjoint_Set{
    // 參照講義
};

int main(){
    int n, m, k;
    cin >> n >> m >> k;

    Disjoint_Set ds;
    ds.init(n);
    for (int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        ds.Union(x, y);
    }

    int ans = 0;
    for (int i = 0; i < n; i++){
        ans += ds.same(k, i);
    }
    cout << ans << '\n';

    return 0;
}

[連通圖](https://pc2.tfcis.org/dev/index.php/problem/view/48)
---
+ DFS / BFS ( 深/廣度搜尋 )
1. 由 Input 建立 Graph ( Adjacency Lists / Matrix )
2. 隨便挑個點為中心 DFS / BFS
3. 檢查是否所有的點都被走過 ( 全部被走過 $\iff$ 連通 )

#include<iostream>
#include<vector>
using namespace std;

vector<int> G[10000];
bool vis[10000];
void dfs( int u ){
    vis[u] = true;
    for( size_t i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if( vis[v] == false ){
            dfs(v);
        }
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(0);
    for(int i=0; i<n; i++){
        if( vis[i] == false ){
            cout << "No\n"; 
            return 0;
        }
    }
    
    cout << "Yes\n";
    return 0;
}

[新阿姆斯特朗炫風噴射阿姆斯特朗棧](https://pc2.tfcis.org/dev/index.php/problem/view/88)
---

面試經典題(兼清大大一程設二期末考考題)
這題解法很多種，只要能做到每筆$O(\log n)$就給AC
註：棧=stack

大概念：用幾個資料結構組合出阿姆斯特朗炫風噴射阿姆斯特朗棧(以下簡稱棧)
- 用一個 stack 維護 FILO (`top`查詢)
- 用一個 max heap 維護最大值 (`maxElement`查詢)
- 用一個 min heap 維護最小值 (`minElement`查詢)
- 當有多個最大值/最小值，pop掉最晚放的那一個：用`(值,被push的時間)`來表示每一個元素，然後實做`operator ()`

Q: `push` 相關指令怎麼維護？
把`(值,被push的時間)`放進 stack, max heap, min heap 裡面

Q: `pop` 相關指令怎麼維護？
另外開一個`vector<bool>`或`map<int,bool>`紀錄某一個時刻$t$被放進棧的元素有沒有被移出去
- e.g. `vector<bool> inStack`;
- 在 `push` 的時候 `inStack[t] = true`
- 在 `pop`, `popMax`, `popMin` 的時候把他設成 `inStack[t] = false`
- `top`/`maxElement`/`minElement` 的時候，如果 stack/max heap/min heap的`top()`是個已經被丟出的元素(i.e. `inStack[xxx.top()] == false`)，就`pop()`掉，直到遇到第一個還在棧裡面的元素

時間複雜度：每個元素只會被放進棧一次，拿出棧一次，均攤時間複雜度$O(\log n)$

[負環判斷](https://pc2.tfcis.org/dev/index.php/problem/view/81)
---

裸判斷負環

使用一般的 Bellmon-Ford 檢查第 $n$ 次循環時，是否有更新，如果有更新就有負環，SPFA 則判斷是否有一點更新超過 $n$ 次。注意用 Floyd 會不小心判到所有點為出發點的狀況。上述演算法可抄講義。

要注意一些更新的細節，像是這個 case

3 1
1 2 -100

很多人會用一個很大的數字當無限大，這樣的敘述很可能產生這樣的判斷

if( INF - 100 < INF )

這一個敘述永遠成立，但沒處理會讓不是負環的 case 判斷成負環，要小心。

[睡熊盲醒](https://pc2.tfcis.org/dev/index.php/problem/view/74)
---

給出一棵含有$n(1\le n\le 10^5)$個節點的樹，每個頂點只有兩種顏色：黑色和白色。
一開始所有的點都是黑色，下面有兩種共$m(1\le n\le 10^5)$次操作：

* 0 u
表示查詢$u$所在的連通塊的大小，相鄰兩個點顏色相同則屬於一個連通塊。
* 1 u
表示翻轉$u$的顏色，即黑點變白點，白點變黑點。

先將無根樹轉成有根樹。樹上的每個節點$x$維護$W[x]$表示當$x$是白色的時候以$x$為根的子樹中和$x$連通的白色點個數；另外維護$B[x]$表示當$x$是黑色的時候以$x$為根的子樹中和$x$連通的黑色點個數。另外維護$pa[x]$表示$x$的parent。

* 對於查詢操作 `0 u` ，我們從$u$往上走，走到深度最小與$u$同色的點$x$，如果$u$是白色$W[x]$就是答案，反之$B[x]$就是答案。
* 對於修改操作 `1 u` ，假設是將$u$從白點變成黑點。首先設$x$是從$pa[u]$往上走遇到的第一個黑點，我們將$\operatorname{path}(pa[u], x)$中所有點的$W$減掉$W[u]$；類似的設$y$是從$pa[u]$往上走遇到的第一個白點，我們將$\operatorname{path}(pa[u], y)$中所有點的$B$加上$B[u]$。

修改操作可以利用樹鏈剖分後用區間修改的線段樹維護。利用線段樹維護每個區間從左往右遇到的第一個白點和黑點的位置可以解決以下兩個操作：
* 找出走到深度最小與$u$同色的點
* 找出從$u$往上走遇到的第一個黑/白點

[好多盤子喔~!](https://pc2.tfcis.org/dev/index.php/problem/view/62)
---
- 子任務一($5\%$)：$N,Q\leq 500$
每筆詢問枚舉m，並暴力計算盤子切割值，時間複雜度$O(QN^2)$

- 子任務二($15\%$)：$N,Q\leq 3000$
每筆詢問枚舉m，線段樹計算盤子切割值，時間複雜度$O(QN\log N)$

- 子任務三($15\%$)：任意時刻所有人的預估花費金額非嚴格遞減，即 $P_i\geq P_{i+1}$
詢問解必為$P[l]-P[r]$，陣列直接做，時間複雜度$O(Q+N)$

- 子任務四($27\%$)：所有人的預估花費金額皆不會改變
？自由發揮

- 子任務五($38\%$)：無限制
考慮線段樹維護。
區間$[l,r]$透過合併兩個子區間$[l,mid]$與$[mid+1,r]$獲得其盤子度；
令切割後，左部分最大值位置為$a$，右部分最小值位置為$b$；顯然$a<b$。
而$a,b$有三種可能：
1. $b\leq mid$
2. $mid<a$
3. $a\leq mid$且$mid<b$

前兩種可能可以透過查詢$[l,mid]$與$[mid+1,r]$的盤子度求得。
第三種可能即為 序列$[l,mid]$最大值 - 序列$[mid+1,r]$最小值。
區間合併的時間複雜度為$O(1)$，總時間複雜度$O((N+Q)\log N)$。

另外一個作法：原問題可轉為尋找一組二元組$(i,j) (l\leq i<j\leq r)$，最大化$P_i-P_j$；將原序列差分後，詢問等價於區間最小連續和乘負號。

[烏鴉坐飛機](https://pc2.tfcis.org/dev/index.php/problem/view/75)
---

給你一張無向圖，你要在圖上加一些邊，使得存在一種方法將這張圖每條邊都改成有向邊之後，整張圖會形成一個強連通分量。

仔細思考會發現任何一個橋連通分量都存在一種方法滿足題目條件。因此先將整張圖找出所有橋連通分量然後縮點，形成橋連通分量樹。接著就可以用進階班在講橋連通分量時的公式計算就行了。但要注意因為有可能不會連通的關係公式變成：

$$度數0的節點數+\lceil 葉節點數量/2 \rceil$$

[動態規劃](https://pc2.tfcis.org/dev/index.php/problem/view/97)
---
- 子任務一($5\%$)：$E=V-1$、$V,Q\leq 500$、相鄰編號的城市之間必有高鐵且車票費用皆為$1$元、熊頭洞穴只有一個且位於城市$1$裡。
(暴力)為一個序列，暴力即可。

- 子任務二($10\%$)：$E=V-1$、相鄰編號的城市之間必有高鐵且車票費用皆為$1$元、熊頭洞穴只有一個、城市舉牌能帶來的溫暖度不會改變。
(資料結構)以與起點的距離弄成序列，相同距離取溫暖度較大的；花費隨著編號遞增，使用前綴和直接查詢最大溫暖度，時間複雜度$O(V+Q)$。

- 子任務三($20\%$)：$E=V-1$、相鄰編號的城市之間必有高鐵、熊頭洞穴只有一個。
(資料結構)以與起點的距離弄成序列，相同距離取溫暖度較大的；花費隨著編號遞增，使用線段樹維護最大溫暖度，詢問時透過二分搜找到最大合法前綴區間，時間複雜度$O((V+Q)\log~V)$。

- 子任務四($10\%$)：$Q\leq 50$且熊頭洞穴只有一個。
(圖論)每次都從熊頭洞穴做最短路並找解，時間複雜度$O(Q(V+E)\log~E)$。

- 子任務五($20\%$)：$Q\leq 50$。
(圖論)設所有熊頭洞穴為起點後(距離0)，做最短路，時間複雜度$O(Q(V+E)\log~E)$。

- 子任務六($35\%$)：無限制
設所有熊頭洞穴為起點後(距離0)，做最短路，並將各點依照到最近熊頭洞穴的距離排序，依照該序用線段樹(或BIT)維護最大溫暖度。
詢問時，二分搜滿足條件的最大前綴區間，並線段樹查詢最大溫暖度；
修改時，反查點在線段樹的位置，直接修改。
時間複雜度為$O((V+E)\log~E+Q\log~V)$。

實作需注意不連通的情況。
---
[動物朋友.exe](https://pc2.tfcis.org/dev/index.php/problem/view/73)
---
遊戲很好玩喔，大家趕快去玩。

**請在windows上執行**

如果不會動請安裝這個軟體 https://www.microsoft.com/en-US/download/details.aspx?id=35

下載點：http://inatsuka.com/extra/kemonofriends.exe/

下載之後會是一個 `kemonofriends.exe.zip` ，先解壓縮一次，會看到一個叫做 `kemonofriends.exe` 的資料夾。

資料夾裡面有一個 `kemonofriends.exe` 的執行檔，將檔案改成 `kemonofriends.zip` 後再解壓縮一次就可以得到真正的執行檔了

動物朋友.exe是一款溫馨感人的遊戲，人類最喜歡♥動物了！

給一張無向圖，我們說$a,b,c$三個點之間有邊互相連接就稱其為一個三角形。問你圖中總共有幾組不同的三角形，$|V| \le 10^5,\; |E| \le 2\times 10^5$。

顯然用$O(|V|^3)$或是$O(|V|\times|E|)$會TLE，這題需要做到$O(|E|\sqrt{|E|})$。

我們將點分成degree大於$\sqrt{|E|}$和小於$\sqrt{|E|}$的，假設大於的部分有$k$個點，而且$k \le \sqrt{|E|}$，我們可以構造一個$k \times |V|$的 01表格紀錄 這些點和其他點是否有邊相連，這樣可以O(1)查詢

接著枚舉每一條邊$(a,b)$，找出$a$相連的點和$b$相連的點的交集，這裡如果$a,b$的degree都小於$\sqrt{|E|}$那我們可以用$O(\deg(a)+\deg(b))=O(\sqrt{|E|})$的方法算出答案，反之利用剛剛建立的表格暴力$O(|V|)$計算，這樣複雜度是$O(E\times \sqrt{|E|} + k\times |V|)$。

講義裡寫的經典題。

:::danger
營長補充個贛話：排序&搜尋的時候我說營隊有彩蛋，如果你找到了，營隊不負任何責任
不要在家裡玩，~~被發現了不要說是營隊教你的~~
:::