---
tags: tutorial
---

# 2022 校內資訊學科能力競賽初選初賽 題解

## p1. GT 教社交

`tags: sorting`

### Subtask 1: (10%)

開個長度為 $L$ 的陣列，並且對於 $N$ 個人花 $O(L)$ 的時間維護好陣列即可

時間複雜度: $O(NL)$

### Subtask 2: (20%)

可以發現子題一的複雜度很糟糕，這時候就需要知道[差分](https://oi-wiki.org/basic/prefix-sum/#%E5%B7%AE%E5%88%86)的技巧。

時間複雜度: $O(N + L)$

### Subtask 3: (70%)

想一下能知道我們其實不需用開長度 $O(L)$ 的陣列，因為最多只會有 $O(N)$ 個需要被記錄的值，我們能開一個 `vector<pair<int, int>>`，裡面存 `pair<要更改的位子, 要更改的值>`，排序 `vec` 後，好好判斷哪些元素是要同時處理，就能知道該位子的值是多少。

需要注意的細節是 Benson 只能在 [1, L] ， 有看清楚題敘應該就能輕鬆 AC 此題。

## p2. Benson 打排球

`tags: dp`

背包問題變化

### Subtask 1: (10%)

因為 $K=L$ 代表不管那天增加了多少疲勞度，只要不肌肉拉傷都會歸零，而 $a_i$ 為正整數，所以這個 Subtask 可以直接 greedy 對於每個位置求當前位置 $a_i$ 加上前綴不爆疲勞度的總和，最後取 max 就會通過這筆測資。

### Subtask 2: (20%)

$b_i<L$ 其實沒什麼意義，但 $K=0$ 代表 dp 前不用平移，除了可以超出 capacity 一次之外就是一個標準的背包問題，只要額外記錄當前不爆上限的最大值 + 當前值就會通過。

### Subtask 3: (70%)

滿分解轉移式:

$dp[i][j]$ 為考慮前 $i$ 天的練習及疲勞度為 $j$ 時候的最大社交度，其中 $j=L$ 代表所有爆疲勞度的情況，因此注意不會轉移到其他疲勞度的情況。

$\forall j<L$

選擇該天的練習
$dp[i+1][\max(0,j-K)]=\max(dp[i+1][\max(0,j-K)],dp[i][j])$

選擇該天不練習
$dp[i+1][\min(L,b[i]+\max(0,j-K))]=\max(dp[i+1][\min(L,b[i]+\max(0,j-K))],dp[i][j]+a[i])$

滿分解要注意的是， $K>0$ 的時候不是 1 對 1 的轉移，所以像一般背包問題一樣壓成一個一維 array 比較困難。這時候可以開兩個 array 交替使用。

:::spoiler **code** by *konchin.shih*

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
template<typename T> using V=vector<T>;
using ll=long long;
constexpr ll infll=0x3f3f3f3f3f3f3f3f;
inline void solve(){
	int n,k,l;cin>>n>>k>>l;
	V<ll> a(n),b(n);
	for(auto& i:a) cin>>i;
	for(auto& i:b) cin>>i;
	V<V<ll>> dp(2,V<ll>(l+1,-infll));
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		fill(dp[~i&1].begin(),dp[~i&1].end(),-infll);
		dp[~i&1][l]=dp[i&1][l];
		for(int j=0;j<l;j++){
			auto from=dp[i&1][j];
			if(from==-infll) continue;
			auto& to1=dp[~i&1][max(0,j-k)];
			auto& to2=dp[~i&1][min(max(0,j-k)+b[i],(ll)l)];
			to1=max(to1,from);
			to2=max(to2,a[i]+from);
		}
	}
	cout<<*max_element(dp[n&1].begin(),dp[n&1].end())<<endl;
}
int main(){
	solve();
	return 0;
}

:::

## p3. 青椒小徑

`tags: bfs`

這題就是非常裸的 bfs 題，只要好好判能走到的格子、是否走訪過，或是會不會超出邊界、採到障礙物，就能AC了。

實作細節因人而異，大部分人走相鄰的格子會這樣寫

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int curX, curY;
for(int i = 0; i < 4; ++i) {
    int nextX = curX + dx[i];
    int nextY = curY + dy[i];
    if(isvalid(nextX, nextY)) {
        ....
    }
}

走小徑(其他的邊)就是

// pair<int, int> -> X, Y

vector<pair<int, int>> G[/*X*/][/*Y*/];

void add_edge(int x, int y, int tox, int toy) {
    // undirected edge
    G[x][y].emplace_back(tox, toy);
    G[tox][toy].emplace_back(x, y);
}

void bfs() {
    //...
    //...
    for(auto& nxt : G[curX][curY]) {
        // nxt.first is nxtX
        // nxt.second is nxtY
        if(isvaild(nxt.first, nxt.second)) {
            // ...
        }
    }
}

再次強調實作細節因人而異，找到自己習慣且穩定的寫法就好。

## p4. 樹上最大值

`tags: tree, dp`
換根 dp 經典題(其實出題前我根本不知道QQ)。

### Subtask 1: (20%)
對每一個點做一次 dfs，算 max 即可，時間複雜度為 $O(n^2)$。

### Subtask 2: (80%)
以範例測資舉例：
仔細觀察即可發現，令原本的答案為 $ans$，若從編號為 $u$ 為根節點轉移到 $v$ 時，更新的答案為 $ans'=ans-\sum a_i\in subtree\{v\}+\sum a_i\in subtree\{u\}$。好好對任意一點做一次 dfs 紀錄答案，再從該點去對每一個鄰近的點做 dfs 轉移答案，即可在 $O(n)$ 的時間複雜度完成。

## p5. GT 教遊戲

`tags: binary_search`

### Greedy的想法 (?)

假設我們在第 $i - 1$ 回合選取某玩家後，可以獲得目前最大的$\frac{X_0}{Y_0}$，那麼是否能運用算出來的 $\frac{X_0}{Y_0}$ 去檢查在第 $i$ 回合，該選取誰作為代表呢 ?

我們可以令在第 $i$ 回合我們將要選取的玩家，手上的兩張牌為$a, b\; (a \geq b)$，並且在第 $i - 1$ 回合我們在選取某個玩家後能得到 $\frac{X_1}{Y_1} \lt \frac{X_0}{Y_0}$ 的結果，那麼在第 $i$ 回合，可能會有 $\frac{X_0 + a}{Y_0 + b}$ 及 $\frac{X_1 + a}{Y_1 + b}$ 這兩個結果。

可以發現 $\frac{X_0 + a}{Y_0 + b}$ 不一定會大於 $\frac{X_1 + a}{Y_1 + b}$。

(e.g. $\frac{X_0}{Y_0} = \frac{10}{1}$, $\frac{X_1}{Y_1} = \frac{30}{5}$, $\frac{a}{b} = \frac{11}{10}$)

因此沒辦法透過記錄最大值來進行 greedy QQ

### Subtask 1: (10%)

> $N \leq 10,\; C \leq 10$

暴力搜尋每回合選三個不同玩家作為代表的可能，假設被選取作為代表的玩家，手上的兩張牌為$a, b\; (a \geq b)$，把 $a$ 加進 $X$ ， $b$ 加進 $Y$ 即可。

時間複雜度: $O(3^N)$

### Subtask 2: (20%)

> $N \leq 20,\; C \leq 50$
> 賽中題敘: $N \leq 100,\; C \leq 100$ (忘記修正題敘真的很抱歉 QQ)

因為 $\frac{X}{Y} \leq N \times C$，並且精度只要求到小數後 4 位，所以對於子題二而言，可以從 1000.0000 枚舉到 0.0000 ( $N \times C \times 10^4 = 10^7$ 次)，檢查 $\frac{X}{Y}$ 是否有可能出現。

假設有一個長 $N$ 的陣列 $choose$，$choose[i]$ 代表在第 $i$ 回合選擇了哪位玩家作為代表，那麼依據陣列 $choose$ 所得出的最後 $\frac{X}{Y}$

$$\frac{X}{Y} = \frac{ \sum{choose[i]_{i1}} }{ \sum{choose[i]_{i2}}}$$

也就是說如果要檢查一個浮點數 $K$ 是否有可能出現，只要找到一個陣列 $choose$，滿足
$$K \leq \frac{ \sum{choose[i]_{i1}} }{ \sum{choose[i]_{i2}}}$$ 移項後可得
$$0 \leq \sum{choose[i]_{i1}} - \sum{choose[i]_{i2}} \times K$$
透過式子可以知道每個回合的選擇是分開的，假設目前是第 $i$ 回合，那我們的目標就是最大化 $choose[i]_{i1} - choose[i]_{i2} \times K$，因此只要計算完所有玩家的點數，代入算式後的結果後，就能知道要選誰了。

時間複雜度: $O(N^2 \cdot C \cdot 10^4)$

### Subtask 3: (70%)

> $N \leq 10^5,\; C \leq 10^8$

如果會做子題二的話，不難發現我們要檢查的浮點數 $K$ 是具有單調性的。

好好計算要浮點數二分搜的次數後 (或是檢查 r - l < eps)，即可AC

時間複雜度: $O(\; N \; log( N \cdot C \cdot 10^4)\;)$