SCIST 110 演算法季後賽題解
===

## A. 背包問題（knapsack）

### 子任務 1

> $k=1$

洽選一個蘋果，則檢查 $s$ 是否在 $1, 2, \dots, n$。

### 子任務 ２

> $n \le 15$

$O(2^n)$ 枚舉每個蘋果選或不選，再檢查是否符合題目要求。

### 子任務 3

> $n \le 100$

直接做背包。以 $dp[i][j][x]$ 代表在蘋果 $1 \dots i$ 中選 $j$ 個，是否有可能花 $x$ 元。

最後一維可以用 bitset 壓掉，$O(\frac{n^4}{32})$

### 子任務 4

> 題目範圍限制

在 $1 \dots n$ 中選 $k$ 個，最小的可能是選 $1, 2, \dots, k$，總價為 $m = (1+k)\frac{k}{2}$；最大的可能是選 $n-k+1, \dots, n-1, n$，總價為 $M = (2n-k+1)\frac{k}{2}$。

可以證明，$m, m+1, \dots, M$ 的每個價格，都可以組合出來。

:::info
不嚴謹的證明：

先採用最小選法，也就是 $1, 2, \dots, k$ ，當 $s$ 比現在的選法大，我們可以將最大、右邊一格沒被選中的數字，改選擇右邊一格。

例如 $n=8, k=4$，現在的選法為：$[1, 2, 5, 8]$。我們可以將 $5$ 改成 $6$，也就是 $[1, 2, 6, 8]$，總和就會加一。

我們可以一直做這件事情直到我們選擇了 $n-k+1, \dots, n-1, n$。

因此若 $m \le s \le M$，我們總是有存在至少一種方法使得總和為 $s$。
:::

#### 參考程式碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int n, s, k;
 
signed main()
{
    cin >> n >> s >> k;
    cout << (((1+k)*k/2)<=s && s<=((n+(n-k+1))*k/2)? "Frank":"Jonason") << '\n';
}

## B. 選手指派 (Player Assignment)

### 子任務 1

> $N \le 20$

以 $O(2^n)$ 枚舉該場比賽是由 Colten 或是 Gino 出賽。

### 子任務 2

> 題目範圍限制

先假設全部由 Colten 出賽，此時表現度為 $a_1, a_2, \dots, a_n$。

若第 $i$ 場比賽改由 Gino 出賽，則表現度會增加 $b_i - a_i$。

求出 $b_1-a_1, b_2-a_2, \dots, b_n-a_n$，從中取出前 $N-K$ 個改由 Gino 出賽即可。

複雜度為排序的 $O(nlogn)$

## C. 王警官已介入調查（cming）

### 子任務 1

> 不存在迴路

無向簡單圖不存在迴路則 $n$ 個節點是一個連通塊當且僅當 $m = n-1$。

### 子任務 2

> $n \le 100$

將邊依照時間做排序，依序加進圖並 dfs 檢查是否為只有一個連通塊。每次檢查 $O(n+m)$，時間 $O(m(n+m))$。

### 子任務 3

> $w = 1$

所有邊都是在同時間建成的，則直接 $O(n＋m)$ 檢查是否只有一個連通塊即可。

### 子任務 4

子任務 2 的作法每次花 $O(n+m)$ 檢查是否為一個連通塊。我們改用「並查集」維護目前所有的連通塊，每次使用接近 $O(1)$ 的時間就可以插入邊。

最一開始共有 $n$ 個連通塊。若該次插入邊 $u, v$ 本屬不同連通塊，則連通塊數量少一，因此我們可以知道每次插入後還有多少連通塊。

#### 參考程式碼

#include <bits/stdc++.h>
#define rep(i,j,k) for (int i=j; i<=k; i++)
#define ff first
#define ss second
#define mothersrosario ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
typedef pair<int,int> pii;

const int N = 2000, M = N*N;

int n, m;

pair<int,pii> edgs[M];

int p[N];

int find(int x) { return p[x]==x? x:p[x]=find(p[x]); }

signed main()
{
    cin >> n >> m;
    rep(i,1,m) cin >> edgs[i].ss.ff >> edgs[i].ss.ss >> edgs[i].ff;

    sort(edgs+1, edgs+1+m);
    rep(i,1,n) p[i] = i;
    
    int cnt = n;
    rep(i,1,m)
    {
        if (find(edgs[i].ss.ff) == find(edgs[i].ss.ss))
            continue;
        else
            p[find(edgs[i].ss.ff)] = find(edgs[i].ss.ss), cnt--;
        if (cnt == 1)
        {
            cout << edgs[i].ff << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
}

## D. Gino 種竹子 (Planting Bamboo)

`tags: DFS, Brute Force`

### 子任務 1

> $1 \le n \le 2$, 不會有格子已經種植作物了

可以直接手算所有的可能性，會發現答案其實可以直接使用 if-else 簡單的計算完畢

#### Case 1: $n=1$

只有在 $k=1$ 時有答案，答案為 $1$，否則皆為 $0$

#### Case 2: $n=2, k \le 3$

答案皆為 $4$

#### Case 3: $n=2, k=4$

答案為 $1$

### 子任務 2

> 不會有格子已經種植作物了

本子題是留給寫不出能在時限內跑完的滿分解，或者不會障礙物的 Case 時可以撈的子任務

#### 預設解法:

暴力生成所有 $n \times n$ 且放置了 $k$ 個竹子的盤面，接著檢查是否滿足竹子皆連通

#### 總共有幾種不同狀態?

在 $n = 8$ 且 $k = 8$，如果直接暴力 DFS 找所有放置了 $8$ 個竹子的盤面，再去檢查答案

一共會有 $C^{64}_8 = 4426165368 \approx 4 \times 10^9$ 種答案

無法在時限內跑完!

#### 本機建表

既然狀態數量這個多，但實際上會詢問的可能性只有 $8 \times 8 = 64$ 種

那我們直接在本機使用這個做法，跑過所有 $n \le 8, \ k \le 8$ 的答案並記錄下來

接著我們遇到詢問，就可以直接回答了!

### 滿分解

#### 目前的困難點

所有 $n \times n$ 且放置 $k$ 個竹子的盤面太多了?

#### 解決方式

事實上，如果在 DFS 的過程，我們就只維護所有竹子都相連的情況

則總方案數並不會太大，是能夠在 $1$ 秒內跑完的

#### 實作細節

可以另外使用一個 set 等等的 STL，幫忙維護已經走過的盤面

在 DFS 時，很多人的方式是從 $(0,0) \sim (0,n-1) \sim (1,0) \sim (7,7)$ 這樣枚舉

而這樣的枚舉方式，不見得能使放下去的竹子相連 (可能要額外進行判斷

#### 參考程式碼

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 10;
set<vector<string>> used;
vector<string> grid;
int n, k, ans;

void dfs(int num){
    if(used.find(grid)!=used.end()){
        return;
    }
    used.insert(grid);

    if(num==0){
        ans++;
        return;
    }

    vector<pair<int,int>> nxt;

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(grid[i][j]=='.'){
                bool ok = false;
                for(auto dx : {-1,0,1}){
                    for(auto dy : {-1,0,1}){
                        if(abs(dx)==abs(dy)) continue;
                        if(i+dx < 0 || i+dx >= n || j+dy < 0 || j+dy >= n) continue;
                        if(grid[i+dx][j+dy]=='*'){
                            ok = true;
                        }
                    }
                }
                if(ok){
                    nxt.push_back({i,j});
                }
            }
        }
    }

    for(auto [nx,ny] : nxt){
        grid[nx][ny] = '*';
        dfs(num-1);
        grid[nx][ny] = '.';
    }
}

signed main(){
    fastio
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;
        grid.push_back(str);
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(grid[i][j]=='.'){
                grid[i][j] = '*';
                dfs(k-1);
                grid[i][j] = '.';
            }
        }
    }
    cout << ans << "\n";
}

## E. 企鵝回家記 (Go home)

### 子任務 1：$n \le 10, m = 1$

直接搜哪一格不會被打就好

### 子任務 2：$n \le 800, m \le 500$

我們可以設 $dp[i][j]$ 為第 $j$ 個時間點時更改 $i$ 次的最少被打次數，look(t) 代表第 $t$ 個時間點 Zhu 會不會看訊息
那麼就可以推出轉移式：$dp[i][j] = \min(\min_{l < j}(dp[i][l]), \min_{l \le j-k}(dp[i - 1][k]) + look(j))$

共有 $nm$ 個狀態，每次轉移 $\mathcal{O}(n)$，時間複雜度 $\mathcal{O}(n^2m)$

### 子任務 3：$n \le 10^4, m \le 1000$

將狀態改為 $dp[i][j]$ 為時間點 $1 \sim j$ 更改 $i$ 次的最少被打次數
轉移式變為：$dp[i][j] = \min(dp[i - 1][j - k] + look(j), dp[i][j - 1])$

時間複雜度：$\mathcal{O}(nm)$

#### 參考程式：

#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
#define MAXN 50000
#define MAXM 5000
 
int n, m, k, q;
int a[MAXN], pre[MAXN], b;
int dp[MAXM + 1][MAXN + 1];
 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m >> k >> q;
 
    for (int i = 0; i < q; i++)
        cin >> a[i];
    cin >> b;
 
    for (int i = 0; i < q; i++) {
        pre[a[i]]++;
        pre[a[i] + b]--;
    }
 
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + pre[i];
 
 
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= n - k; j++) {
            dp[(i + 1)][j + k] = dp[i][j] + pre[j + k];
            dp[(i + 1)][j + k] = min(dp[(i + 1)][j + k], dp[(i + 1)][j + k - 1]);
 
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
        }
    }
 
    cout << dp[m][n] << endl;
 
    return 0;
}

### 子任務 4：$n \le 5 \times 10^4, m \le 5000$

用子任務 3 的方法會 MLE，將 dp 陣列換成滾動，開 dp[2][n]，對於每個 i 用 dp[i % 2] 做

空間複雜度：$\mathcal{O}(n)$

### 參考程式：

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

#define MAXN 50000
#define MAXM 5000

int n, m, k, q;
int a[MAXN], pre[MAXN], b;
int dp[2][MAXN + 1];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k >> q;

    for (int i = 0; i < q; i++)
        cin >> a[i];
    cin >> b;

    for (int i = 0; i < q; i++) {
        pre[a[i]]++;
        pre[a[i] + b]--;
    }

    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + pre[i];

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= n - k; j++) {
            dp[(i + 1) % 2][j + k] = dp[i % 2][j] + pre[j + k];
            dp[(i + 1) % 2][j + k] = min(dp[(i + 1) % 2][j + k], dp[(i + 1) % 2][j + k - 1]);
			
            dp[i % 2][j + 1] = min(dp[i % 2][j + 1], dp[i % 2][j]);
        }

        for (int j = 0; j <= n; j++)
            dp[i % 2][j] = 1e9;
    }

    cout << dp[m % 2][n] << endl;

    return 0;
}