# 算法模競2--題解 by yungyao

難度錯估ㄉ部分我很抱歉，我低估題目難度ㄌ

## A Apples
就國小數學啦
主要是浮點數的應用

Subtask 1只要用`long long`儲存$a,b$，然後相除輸出就好

Subtask 2則要用`double`儲存，一樣相除輸出就好
由於我精度只要求到$10^{-4}$，所以不需要特別處理，輸出就好

不過還是小補充一下怎麼輸出高精度的浮點數
以C++來說，你會需要先引入標頭檔`iomanip`，然後利用`setprecision()`和`fixed`
大概像下面這樣

using namepace std;
#include <iostream>
#include <iomanip>

...

int main(){
    cout << fixed << setprecision(n);//放入你需要小數點下幾位
    double a;
    
    ...
    
    cout << a;
    
    return 0;
}

## B Map
裸的dsu題，就跟你們說會考ㄅ
反正就是好好做就好

### Subtask 1
這個Subtask應該很水
只要對每個query都dfs一次就好了

#### 賽後補充 by yungyao
DFS要好好寫QQ

### Subtask 2
這個Subtask則是可以在邊都增完後，跑一輪DFS
就可以知道每個點是否屬於同一個連通塊，然後就好好做

### Subtask 3
額，就DSU，好好做就好

::: spoiler AC code

using namespace std;

//IO
#include <iostream>
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);

//workspace

int dsu[200200];

int query(int k){
    if (k == dsu[k])
        return k;
    return dsu[k] = query(dsu[k]);
}

inline void merge(int i,int j){
    dsu[query(i)] = dsu[query(j)];
}

int main(){
    theyRSOOOOOOOOODIAN
    int n,q;

    cin >> n;
    for (int i=1;i<=n;++i)
        dsu[i] = i;

    for (cin >> q;q--;){
        char c;
        int u,v;

        cin >> c >> u >> v;
        if (c == '1')
            merge(u,v);
        else
            cout << (query(u) == query(v) ? "yes\n" : "no\n");
    }

    return 0;
}

:::

#### 賽後補充 by youou
我明明跟鄭永堯講過測資有錯，然後他沒改= =

#### 賽後補充的補充 by yungyao
我有改辣，只是漏改了一個Subtask，我很抱歉

## C Investments
沒那麼裸的背包，這題原本是要出在考幹的，但後來換別題ㄌ，開ㄅ開心

一樣分Subtask講
### Subtask 1
$n \leq 10$，應該滿明顯的是枚舉就能過，然後你就發現常見的枚舉方式好像不太能做
直接標示取或不取好像不太行，因為取的順序有差

然而此時你可以融合兩個常見的枚舉方式：$2^n$表示狀態加上 $n!$ 表示順序(其實這叫做searching tree)
再對所有順序算出答案

不過直接乘起來好像又太大了，感覺不太可做，但其實不會，因為複雜度雖然是 $O(2^nn!)$
但實際上計算運算次數會是

$\sum\limits^{n}_{i=1}C^i_n \times i! \times i = \sum\limits^n_{i=1}\frac{n!}{(n-i)!}i$

在 $n = 10$ 時，這個神奇的算式會得到 $88776910$，大約小於 $10^8$，其實是一個不差的運算次數
不過你在賽中大概也懶得算那麼多啦，反正會過XD(其實我沒測就是ㄌ，但我猜不會有人刻著東西)

打那麼多，重點只是有時候演算法的常數可以小到不可思議，還有其他類似例子(譬如$O(n^3)$區間DP $n = 1000$經常可過)

### Subtask 2
這個Subtask你觀察一下就可以發現，他其實是裸的01背包問題
就...這樣吧，沒寫出來ㄉ再讀一下背包的slides

### Subtask 3
這個就比較有趣ㄌ，你會發現一般的背包問題我們基本上不考慮放置順序，可是這題似乎順序會影響答案
我們還是一樣可以把背包的思路放進這題，只要進行一些小修正就好了

首先我們只要先考慮$r_i - c_i > 0$的情況(Trivial)
接著也知道$dp[i][j] \geq dp[i-1][j]$
也就是說答案只會變大，因此我們只要對$c_i$由小到大排序
而只對 $dp[i-1][j- (r_i-c_i)] \geq c_i$ 的情況做事就好
剩下的部分就跟普通背包一樣ㄌ
100分get

:::spoiler AC code

using namespace std;
#include <algorithm>

//IO
#include <iostream>
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);

//workspace

struct node{
    int p;
    int w,rq;
};

int main(){
    theyRSOOOOOOOOODIAN
    int n,k,h;
    int dp[10010]{};
    node stuffs[10010];

    cin >> n >> k >> h;
    for (int i=0;i<=k;++i)
        dp[i] = h;

    for (int i=0;i<n;++i){
        int p,c,r;

        cin >> p >> c >> r;
        stuffs[i] = {p,r-c,c};
    }
    sort (stuffs,stuffs+n,[](node a,node b){return a.rq < b.rq;});

    for (int i=0;i<n;++i){
        for (int j=k;j>=stuffs[i].p && dp[j-stuffs[i].p] >= stuffs[i].rq;--j){
            dp[j] = max(dp[j],dp[j-stuffs[i].p] + stuffs[i].w);
        }
    }

    cout << dp[k];

    return 0;
}

:::

比較可惜的部分是開$10000 \times 10000$的二維陣列會爆炸
所以必須要滾動，但我可能沒有講好滾動的部分，所以有些人就這樣MLE的不明不白，非常ㄅ歉

#### ㄛ其實
這題是抄來ㄉ，原題是 [TIOJ 1675](https://tioj.ck.tp.edu.tw/problems/1675)

## D Love
#### Subtask 1
痾，線段樹砸下去。

#### Subtask 2
痾，單點修改砸下去。

#### Subtask 3
痾，暴力的單點修改砸下去。20只是常數。欸不是這樣有90分欸。

#### Subtask 4
可能大家都不想寫這題(?)，我就直接暴雷好了。

首先，gcd有個神奇的性質: $\gcd(a, b) = \gcd(a-b, b)$，

我們可以把它推廣到 $\gcd(a_l, a_{l+1}, ..., a_r) = \gcd(\gcd(a_{l+1} - a_l, a_{l+2} - a_{l+1}, ..., a_r - a_{r-1}), a_r)$

還記得差分嗎? 對於後面那項 $a_r$，我們可以用差分做區間修改、單點查詢的BIT，
前面那項就用單點修改、區間查詢gcd的線段樹就好了。

複雜度 $\mathcal{O}(q \log n)$。

btw 這題是[TIOJ 1282](https://tioj.ck.tp.edu.tw/problems/1282)。

## E Knapsack
當你以為這是背包問題ㄉ時候，你就錯ㄌ，其實是裸的MST
阿跟DSU那題一樣，好好做就好

:::spoiler AC code

using namespace std;
#include <algorithm>

//IO
#include <iostream>
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);

//workspace

struct Node{
    int u,v;
    int w;
}edge[200200];

int dsu[100100];

int query(int k){
    return dsu[k] == k ? dsu[k] : dsu[k] = query(dsu[k]);
}

void modify(int i,int j){
    dsu[query(i)] = query(j);
}

int maxEdge[100100];

int main(){
    theyRSOOOOOOOOODIAN
    int n,m;

    cin >> n >> m;
    for (int i=1;i<=n;++i)
        dsu[i] = i;
    for (int i=0;i<m;++i)
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    
    sort (edge,edge+m,[](Node a,Node b){return a.w < b.w;});
    int e = 0;
    for (int i=0;i<m&&e<n-1;++e){
        while (i < m && query(edge[i].u) == query(edge[i].v))
            ++i;
        if (i < m){
            modify (edge[i].u,edge[i].v);
            maxEdge[edge[i].u] = max(maxEdge[edge[i].u],edge[i].w);
            maxEdge[edge[i].v] = max(maxEdge[edge[i].v],edge[i].w);
        }
    }
    for (int i=1;i<=n;++i)
        cout << maxEdge[i] << ' ';
    
    return 0;
}

:::

### Subtask 1
特別講一下這個Subtask，你會發現既然 $m = n - 1$，又保證圖連通
代表這張圖一定是一棵樹
而樹的最小生成樹就是整棵樹
所以輸出每個點最大的邊就好ㄌ

## F Answers

本次預期跟D並列第二大難題
不過理論上這題會再難一點
需要多一點競賽經驗比較做的出來，所以你們現階段想不到我滿可以理解的

### Subtask 1
這個Subtask理論上超級好做的，沒有人去寫實在很可惜
在左界都是1的情況下，你只需要對右界做前綴和就好了

而查詢都在修改後面表示你只需要存每個 $r$ 有多少答案
然後再做前綴和，查詢時只要回答 $r$ 的前綴和是多少就好了

### Subtask 2
跟上一個Subtask類似，但修改跟查詢輪替的情況下
你就得用BIT去做(或線段樹)
也是實作題而已，只有一個人寫也是偏可惜

:::spoiler 80 points get

using namespace std;

//IO
#include <iostream>
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);

//workspace

int bit[3030];

void modify(int k,int val){
    for (;k<=3000;k+=k&-k)
        bit[k] += val;
}

int query(int k){
    int r = 0;
    for (;k;k-=k&-k)
        r += bit[k];
    return r;
}

int main(){
    theyRSOOOOOOOOODIAN
    int q;

    for (cin >> q;q--;){
        char o;

        cin >> o;
        if (o == '1'){
            int u,v,w;

            cin >> u >> v >> w;
            modify (v,w);
        }
        else{
            int l,r;

            cin >> l >> r;
            cout << query(r) << '\n';
        }
    }

    return 0;
}

:::

### Subtask 3
這個Subtask跟pD的最後一個一樣，寫不出來正常啦
簡單來說我們可以畫一張表格，把左右界分別映射到x/y平面上
下面以縱軸為左界，橫軸為右界

那我們假設在 $[3,5]$ 有了一組解 (v 的位置)

那會讓用x劃記的都可以用到這組解(也就是所有左界$\leq l$，右界$\geq r$的區間)
那如果換個角度想查詢的狀態
假設要查詢 $[4,6]$ 這個區間 (v 的位置)

那所有被x標記的區間都必須被算到 (X標記的區間則是不合法的區間，因為 $l > r$)
也就是X軸前綴、Y軸後綴和，你就可以發現，我們可以用一個二維BIT去維護這個東西ㄌ
但要注意一個維度是前綴，另一個是後綴，所以小心不要混淆

:::spoiler AC code

using namespace std;

//IO
#include <iostream>
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);

//workspace

int bit[3001][3001];

inline int query(int x,int y){
    int val = 0;
    for (int i=x;i<=3000;i+=i&-i)
        for (int j=y;j;j-=j&-j)
            val += bit[i][j];
    return val;
}

inline void modify(int x,int y,int val){
    for (int i=x;i;i-=i&-i)
        for (int j=y;j<=3000;j+=j&-j)
            bit[i][j] += val;
}

int main(){
    theyRSOOOOOOOOODIAN
    int q;

    cin >> q;
    while (q--){
        char c;
        int l,r,w;

        cin >> c;
        if (c == '1'){
            cin >> l >> r >> w;
            modify(l,r,w);
        }
        else{
            cin >> l >> r;
            cout << query(l,r) << '\n';
        }
    }

    return 0;
}

:::

---

整體來說，大家都很棒辣
接下來上機考加油ㄛ~~~