# 114 學年上學期資讀
## APCS 模考題解
----
成績分布
----
預期難度：
初級 C < B < A
中高級 B < C < A
----
實際難度 (按照 AC 數排)：
初級 C(5) < A(2) < B(0)
中高級 A(1) < B(0) = C(0)
---
# 初A. 到底熟了沒？
----
有三種操作
1. 增加 $C$ 的值
2. 加一片值為 $H$ 的肉片入鍋
3. 問目前的 $C$ 是否都超過鍋內所有肉的 $H$
----
subtask 1(50%): 操作不包含第二種操作。
----
因為不會增加 $C$ 的值，所以只要檢查有沒有加入過 $H >= C$ 的肉片即可。
----
```cpp
bool ok = 1;
for(int i = 0; i < q; i++){
int type;
cin >> type;
if(type == 1){
int H;
cin >> H;
if(H >= C){
ok = 0;
}
}
else if(type == 2){
//no type 2
}
else{
cout << (ok ? "Yes\n" : "No\n");
}
}
```
----
subtask 2(50%): 無額外限制。
----
發現到其實不用檢查 $C$ 是否超過鍋內所有的肉，只要維護鍋內 $H$ 最大的值 $H_{max}$，檢查目前的 $C$ 是否超過 $H_{max}$ 即可。
----
```cpp
int mx = 0;
while(q--){
int ty;
cin >> ty;
if(ty == 1){
int x;
cin >> x;
mx = max(x, mx);
}
else if(ty == 2){
int x;
cin >> x;
C += x;
}
else{
cout << (C > mx ? "Yes\n" : "No\n");
if(C > mx) mx = 0;
}
}
```
----
當然也可以用陣列，但很沒必要。
---
# 初B. 不想再成為第二名
----
有 $n$ 個人與 $m$ 道題，給你第 $i$ 個人在第 $j$ 道題的分數 $S_{i,\ j}$，問按照總分排名過後的第二名編號為何？
若同分則編號較低的排名較前面。
----
subtask 1(50%): $n = 2$
----
只有兩個人，所以比較兩個人的總分就好。
----
```cpp!
int a = 0, b = 0;
for(int i = 0; i < m; i++){
int x;
cin >> x;
a += x;
}
for(int i = 0; i < m; i++){
int x;
cin >> x;
b += x;
}
if(a >= b){//1 為第一名
cout << 2 << '\n';
}
else{//b > a, 2 為第一名
cout << 1 << '\n';
}
```
----
subtask 2(50%): 無額外限制。
----
用四個變數維護目前資訊，維護目前第一、二名的分數，另一個維護目前第一、二名的編號。
----
```cpp!
int mxsum = -1, secsum = -1, mxid = 0, secid = 0;
for(int i = 1; i <= n; i++){
int sum = 0;
for(int j = 1; j <= m; j++){
int x;
cin >> x;
sum += x;
}
if(sum > mxsum){
secsum = mxsum;
secid = mxid;
mxsum = sum;
mxid = i;
}
else if(sum > secsum){
secsum = sum;
secid = i;
}
}
```
---
初C. 煙火大會
----
有 $n$ 次施放煙火，每次施放煙火第一、二會場都會有得分，算出第一會場和第二會場總共贏了幾次。
----
subtask 1(50%): $n = 1$
----
輸入然後檢查就好了。
只有三種輸出情況
1. ```0 0```
2. ```0 1```
3. ```1 0```
----
```cpp!
int a, b;
cin >> a >> b;
if(a > b){
cout << "1 0\n";
}
if(b > a){
cout << "0 1\n";
}
if(a == b){
cout << "0 0\n";
}
```
----
subtask 2(50%): 無額外限制。
----
用迴圈計算每次得分即可。
----
```cpp!
int a = 0, b = 0;
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
a += (x > y), b += (y > x);
}
cout << a << ' ' << b << '\n';
```
---
中高A. 道路建設
----
題目等價於要在一張圖上找到一個大小為 $k$ 的連通塊，並且要求此連通塊中最大邊要盡可能小。
----
subtask 1(30%): $n,\ m,\ w_i \le 300$
----
暴力枚舉使用的邊權最大為何，接著只要對著刪除 $w_i > x$ 的子圖做 flood fill 查詢是否有大小大於等於 $k$ 的連通塊即可。
時間複雜度 $O(w_{max}(n + m))$
----
subtask 2(70%): 無額外限制。
----
不難從 subtask 1 發現，若使用邊權小於等於 $x$ 的子圖做 flood fill 查是否有大小大於等於 $k$ 的連通塊的結果為 $f(x)$，則 $f(x)$ 具有單調性，所以可以對 $f(x)$ 去二分搜。
時間複雜度 $O((n + m)log(w_{max}))$
----
另解：
此題可以在使用 DSU 找最小生成樹的過程中用 DSU 去查過程中是否有大於等於 $k$ 的連通塊，則當下的邊權就是答案。
----
如果要求總和最小要怎麼辦？
目前是沒有多項式解的，而且要用到很難的知識 (APCS 不考)。
有興趣可以去查斯坦那樹
---
中高B. 三角初華的陰謀
----
給一個序列，問能用這個序列有多少 $(i,\ j,\ k)$ 使得 $a_i,\ a_j,\ a_k$ 滿足三角不等式。
----
subtask 1(30%): $n \le 100$
----
暴力枚舉 $i,\ j,\ k$。
時間複雜度 $O(n^3)$
----
subtask 2(70%): 無額外限制。
----
三角不等式要滿足任兩邊之和大於第三邊，所以會有三個不等式，這樣好麻煩。
不妨先將序列排序，這樣就只要判斷編號較小的兩個總和是否大於編號最高的值。
----
將序列排序之後問題變成
假設 $i < j < k$，要找到有多少 $a_i + a_j > a_k$，
可以先枚舉 $i, j$ 使得 $a_i + a_j$ 成為定值 $x$，
這樣問題就變成有多少 $k$ 滿足 $x > a_k$，
就可以二分搜求解了。
時間複雜度 $O(n^2log(n))$
----
有辦法用雙指針把時間複雜度壓到 $O(n^2)$。
但以往 APCS 考雙指針的題非常少而且一考出來就放在高級題目的定位，所以就不卡了。
----
中高C. 魔法密碼
----
給一棵以 $1$ 為根的樹，每個節點上都有一個值 $val_i$，有 $p$ 個特殊節點，求字典序第 $k$ 小從根節點到特殊節點上 $val_i$ 組成的序列。
----
subtask 1(30%): $n \le 100$
----
暴力求從 $1$ DFS 到特殊節點組成的序列，並且 sort 過後看第 $k$ 個序列是哪個。
----
subtask 2(70%): 無額外限制。
----
此題有個特殊條件：
對於所有節點的子節點的 $val_i$ 皆不相同。
換句話說，我們可以直接把每個節點的子節點按照 $val_i$ 去排序，DFS 遇到的第 $k$ 個特殊節點所構造出的序列即為答案。
----
bounus:
如果沒有保證所有節點的子節點的 $val_i$ 皆不相同要怎麼做？
我們會需要把 $val_i$ 相同的節點都合併成一個節點。
聽起來好難做？
----
可以直接套一個資料結構叫做 Trie，他可以做到這樣的事情。
當然，這也遠遠超出 APCS 的範圍。
{"title":"114 學年上學期程式設計讀書會 - APCS 模擬考題解","contributors":"[{\"id\":\"bf35a5b2-27fc-4d14-bb9a-9b95ff08effa\",\"add\":4216,\"del\":268,\"latestUpdatedAt\":1767542122937}]"}