# APCS 20250615 題解
> 作者：沈宗叡（暴力又被TLE）
## [1. 小心陷阱](https://zerojudge.tw/ShowProblem?problemid=q836)
### 簡易題述
- 給定初始生命值 $k$，數線上從 $0$ 開始每次右跳「剩餘生命值」格。
- 若是落點在 $x_1$ 的倍數，生命值減少 $y_1$；落在 $x_2$ 的倍數減少 $y_2$。兩者可疊加。
- 生命值 $\le 0$ 時，結束並輸出停止位置。
### 解法
模擬即可。
$Time: O(?), Space: O(1)$
```python=
def main():
from sys import stdin
e = stdin.readline
k = int(e())
x1, y1 = map(int, e().split())
x2, y2 = map(int, e().split())
pos = 0 # 初始位置 0
while k > 0:
pos += k
if pos % x1 == 0: k -= y1
if pos % x2 == 0: k -= y2
print(pos) # 結束位置
main()
```
## [2. 轉盤得分](https://zerojudge.tw/ShowProblem?problemid=q837)
### 簡易題述
- $m$ 個輪盤上各有長度 $n$ 的小寫字母字串，逆時針成環狀。
- $k$ 個回合，每次輸入 $m$ 個旋轉格數，依照指定次數旋轉每一個輪盤。
- 對每個位置計算同字母最高頻率，最後輸出 $k$ 輪的總和。
### 解法
也是模擬即可。
旋轉的部分，可以用 string slicing 暴力、`collections.deque.rotate(x)` 硬轉，也可以記錄每個字串的旋轉值，取值時再算出旋轉後的 index。
C 或 C++ 要考慮餘數可能是負的問題，但 Python 不必，Py 又贏 :D
計數部分，可以善用 Python 的 `collections.Counter`，直接省去字串計數的實作。
至於旋轉是要用扣的還是用加的，可以隨便選一個再跑範測看對不對ww
$Time: O(k \cdot m \cdot n), Space: O(m \cdot n)$
```python=
def main():
from sys import stdin
from collections import Counter
sub = int.__sub__
e = stdin.readline
m, n, k = map(int, e().split())
l = [e().rstrip() for _ in range(m)] # 所有字串
shift = (0,) * m # 初始化旋轉量
ans = 0
for _ in range(k):
# 累加每個位置的旋轉量
shift = tuple(map(sub, shift, map(int, e().split())))
# 計算每個位置的答案
ans += sum(max(Counter(s[(i + j) % n]
for s, j in zip(l, shift)).values())
for i in range(n))
print(ans)
main()
```
## [3. 貪心闖關](https://zerojudge.tw/ShowProblem?problemid=q838)
### 簡易題述
- 給一個陣列表示 $1 \sim n$ 各位置的沙包數量，以及耐重上限 $t$
- 每回合：
- 找出沙包數最少的位置，多個則找最左的
- 沙包數超過 $t$ 則結束
- 否則，搬到右邊第一個仍有沙包的位置，並將當前位置歸零
- 當前搬了 $w$ 個沙包就得 $w$ 分
- 統計總得分
### 解法
一堆人砸 C++ 的 `set`（約等於 `sortedcontainers.SortedList`，只是底層是 RBT 紅黑樹），有的還砸兩個，真的有夠毒瘤。甚至有人要在兩顆線段樹上二分搜？
我們是善良的 Py 人，當然好好(?)地用 heap 和 雙頭ㄌㄌ（doubly linked list）模擬。
「找沙包數最少的位置」可以用 min-heap 輕鬆做到，「右邊第一個仍有沙包的位置」則也可用雙頭ㄌㄌ輕鬆找到。
但要怎麼把沙包搬過去？
理論上正確的做法是實作 increase-key，但普通的 heap 辦不到，要實作成樹狀，而且很難寫。
所以我們可以「懶惰」一點，如果要更新某個值，直接把新值丟進 heap，在 `heappop` 的時候額外判斷「這個沙包數量是不是對的」，如果錯就代表那是舊的值，跳過他。這種 lazy update 的概念在競賽中很常用。
$Time: O(n \log_2 n), Space: O(n)$
```python=
def main():
from sys import stdin
from heapq import heapify, heappop, heappush
e = stdin.readline
n, k = map(int, e().split())
l = list(map(int, e().split()))
# 用來找最少沙包的 min-heap
q = list(zip(l, range(n)))
heapify(q)
# 雙頭ㄌㄌ
le, ri = list(range(-1, n)), list(range(1, n + 2))
ri[-1] = n # sentinel
ans = 0
while q:
v, i = heappop(q)
if v > k: break
if l[i] != v: continue
l[i] = 0
ans += v
# ㄌㄌ上刪掉這點
ri[le[i]] = ri[i]
le[ri[i]] = le[i]
# 搬過去
r = ri[i]
if r < n: # 右邊還有沙包
l[r] += v
heappush(q, (l[r], r))
print(ans)
main()
```
其實瞪著範測稍微遍歷一下可以發現線性解：
考慮某個位置 $i$ 的沙包，他要被搬去哪？如果 $a_i \gt k$ 則搬不動跳過；否則找右邊第一個 $a_j \ge a_i$ 的位置 $j$，因為若是 $a_j \lt a_i$ 則 $j$ 應該會較 $i$ 先被搬空。
而「找右邊第一個 $\ge$ 自己的」是單調棧裸題。
以下實作中，用 `top` 變數快取 `stk[-1]` 以加快 access 速度。`17` 行則是將 `top` 寫回 `stk`，取代 `stk[0]` 中的 $\inf$。
`top` 初始化為 $\inf$，則維護單調棧的 `while` 不用多判斷 `stk` 是否為空。
最後別忘了將 `stk` 內剩餘的沙包的加總（就是不用往右邊搬的沙包）。
$Time: O(n), Space: O(n)$
```python=
def main():
from sys import stdin
e = stdin.readline
n, k = map(int, e().split())
ans = 0
stk = [] # 嚴格遞減 stack
top = float("INF") # > k 即可
for v in map(int, e().split()):
while top <= v:
ans += top
v += top
top = stk.pop()
if v <= k:
stk.append(top)
top = v
if stk: stk[0] = top
print(ans + sum(stk))
main()
```
C++ 版本（僅主要邏輯）：
```cpp=
const int N = 3e5;
ll stk[N];
void solve() {
int n, k;
cin >> n >> k;
ll ans = 0;
stk[0] = 0x3f3f3f3f'3f3f3f3f; // inf 作為 sentinel
int t = 0; // stack top
for (;n--;) {
ll v;
cin >> v;
for (; stk[t] <= v; --t) ans += stk[t], v += stk[t];
if (v <= k) stk[++t] = v;
}
for (;t;) ans += stk[t--];
cout << ans << '\n';
}
```
再說回那些砸線段樹的，不管怎樣，砸兩棵線段樹真的太毒了！
因此以下我實作了一個 zkw 線段樹 + BIT 上二分搜的解法（實作量 $10 \sim 20$ 分鐘），兩者的功用分別等價於第一個解的 heap 和 雙頭ㄌㄌ。
因為最小值是要全局查詢，所以我將 zkw 開滿到完美二元樹，這樣可以 $O(1)$ 全局查詢最小值 index。
~~常數巨大，不負眾望地暴力又被TLE。~~
$Time: O(n \log_2 n), Space: O(n)$
```python=
def main():
from sys import stdin
from itertools import repeat
inf = float("INF")
e = stdin.readline
n, k = map(int, e().split())
m = 1 << n.bit_length() # 開滿到完美二元樹 >n的最小2冪
l = list(map(int, e().split())) + [inf] # 多開的節點全都指向 inf
zkw = [0] * m
zkw += range(n) # 葉子指向自己所代表的位置
zkw += repeat(n, m - n) # 多開的節點全都指向 inf
for i in range(m - 1, 0, -1): # O(n) bottom-up 建樹
zkw[i] = min(zkw[i << 1], zkw[i << 1 | 1], key=l.__getitem__)
bit = [i & -i for i in range(n + 1)] # 初始化全 1 的 BIT
ans = 0 # 所求
while l[zkw[1]] <= k: # 沙包最少的位置要能搬
i = zkw[1] # 找到沙包最少的位置 (全局查詢最小值index)
v = l[i]
ans += v
l[i] = inf # 改成inf 不可能再搬這邊
# 修改完 l[i] O(log n)更新 zkw
ii = (i + m) >> 1
while ii:
zkw[ii] = min(zkw[ii << 1], zkw[ii << 1 | 1], key=l.__getitem__)
ii >>= 1
# O(log n) 將 BIT 上此點刪除
ii = i + 1 # 1-based
while ii <= n:
bit[ii] -= 1
ii += ii & -ii
# O(log n) BIT 查詢到此點的前綴和
pre = 0
ii = i
while ii:
pre += bit[ii]
ii &= ii - 1
# O(log n) BIT 上二分搜找下一個 1 (有沙包的位置)
# 即為找 left most BIT前綴和 > pre
cur = 0
ii = 0
b = 1 << n.bit_length() - 1 # 由高位往下二分搜
while b:
if ii + b <= n and cur + bit[ii + b] <= pre:
ii += b
cur += bit[ii]
b >>= 1
# 實際上搜到的 left most BIT前綴和 <= pre
# ii 需要+1 但要從1-based改回0-based 所以扣回來
# ii += 1; ii -= 1
if ii < n: # 如果右邊有沙包
l[ii] += v # 搬過去
# 修改完 l[ii] O(log n) 更新 zkw
ii = (ii + m) >> 1
while ii:
zkw[ii] = min(zkw[ii << 1], zkw[ii << 1 | 1], key=l.__getitem__)
ii >>= 1
print(ans)
main()
```
C++ 版本（葬送可讀性）：
```cpp=
#define REP(i, s, t) for (int i = (s); i < (t); ++i)
const int N = 3e5;
const ll inf = 0x3f3f3f3f'3f3f3f3f;
int bit[N + 1];
ll l[N + 1], zkw[1 << 20];
void solve() {
int n, k;
cin >> n >> k;
int m = 1 << (32 - __builtin_clz(n)); // 1 << n.bit_length()
REP(i, 0, n) cin >> l[i];
l[n] = inf;
REP(i, 0, n) zkw[i + m] = i;
REP(i, m + n, m << 1) zkw[i] = n;
for (int i = m; --i; ) zkw[i] = l[zkw[i << 1]] <= l[zkw[i << 1 | 1]] ? zkw[i << 1] : zkw[i << 1 | 1];
REP(i, 1, n + 1) bit[i] = i & -i;
ll ans = 0, v;
for (int i;(v = l[i = zkw[1]]) <= k;) {
ans += v;
l[i] = inf;
for (int ii = i + m; ii >>= 1; ) zkw[ii] = l[zkw[ii << 1]] <= l[zkw[ii << 1 | 1]] ? zkw[ii << 1] : zkw[ii << 1 | 1];
for (int ii = i + 1; ii <= n; ii += ii & -ii) --bit[ii];
int pre = 0, cur = 0, j = 0;
for (int ii = i; ii; ii &= ii - 1) pre += bit[ii];
for (int b = m; b >>= 1;) if (j + b <= n and cur + bit[j + b] <= pre) cur += bit[j += b];
if (j < n) {
l[j] += v;
for (j += m; j >>= 1; ) zkw[j] = l[zkw[j << 1]] <= l[zkw[j << 1 | 1]] ? zkw[j << 1] : zkw[j << 1 | 1];
}
}
cout << ans << '\n';
}
```
> 說實在這題非常不公平，C++ 使用者可以直接用 `multiset` $O(n \log_2 n)$ 水過這題，Python 卻沒有內建 SortedList 類型的資料結構。
> APCS simulation 出題團隊會避免這種語言間存在明顯優劣勢的題目，所以**大家都該寫 APCS 模擬測驗！**
## [4. 最遠分組](https://zerojudge.tw/ShowProblem?problemid=q839)
### 簡易題述
- 給定完全圖的距離鄰接矩陣，要將 $n$ 個點劃分為 $k$ 個非空組
- 最大化所有組對之間最短距離的最小值
### 解法
**這題跟 APCS 模擬測驗的 [顯卡爭霸戰](https://apcs-simulation.com/problem/apcs0404-Java-Python) 概念上很像，所以大家都該寫 APCS 模擬測驗！**
先說 APCS 考點內的解法。
為了要讓組組之間的最短距離盡量大，就應該讓短距離的邊都在組內，所以先對邊依照邊權排序，由小到大連邊，但規定要分成 $k$ 組，所以也不能全加。
觀察到：「是否能分成 $k$ 組」對「選了多少邊」有單調性，加更多邊必越不可能分 $k$ 組，可以用這個單調性對「要選多少邊」二分搜，並判斷當前選擇的邊數「是否能分成 $k$ 組」。
計算連通塊數量可以用 BFS/DFS 輕鬆 $O(n)$ 辦到。
輸入距離鄰接矩陣的時候，可以只存半邊就好，因為邊是無向邊。以下用 `itertools` 的 `islice` 取前半部分、`chain.from_iterable` 把每一行 `islice` 完後接起來。
$Time: O(n ^ 2 \log_2 n), Space: O(n ^ 2)$
```python=
def main():
from sys import stdin
from itertools import islice, chain
from operator import itemgetter
e = stdin.readline
def check(x: int) -> bool: # 連通塊數量 >= k？
vis = [False] * n # 記錄每一點是否遍歷過
# 建鄰接串列
G = [[] for _ in range(n)]
for _, i, j in islice(l, x):
G[i].append(j)
G[j].append(i)
count = 0 # 計算連通塊數量
for i in range(n):
if vis[i]: continue
vis[i] = True
count += 1
if count >= k: # 至少有 k 個連通塊
return True
# 遍歷並標記一整個連通塊
cur = [i]
while cur:
nxt = []
for i in cur:
for j in G[i]:
if vis[j]: continue
vis[j] = True
nxt.append(j)
cur = nxt
return False # 不足 k 個連通塊
n, k = map(int, e().split())
l = sorted(chain.from_iterable(
islice(((v, i, j) for j, v in enumerate(map(int, e().split()))), i)
for i in range(n)), key=itemgetter(0)) # 依照邊權升冪排序
# 二分搜答案
le, ri = 1, n * (n - 1) >> 1
while le < ri:
mid = (le + ri) >> 1
if check(mid):
le = mid + 1 # 不足 k 個連通塊
else:
ri = mid # 至少有 k 個連通塊
# 加入 l[le-1] 就會不足 k 個連通塊
print(l[le - 1][0]) # 輸出 l[le-1] 的邊權
main()
```
實際上「加邊、判斷連通塊數量」的部分是 MST 最小生成樹 的裸題，所以砸一個 DSU 下去就解決了。
DSU 的實作上，我會用負數代表 rank，越負表示 rank 越大，正數則表示父節點 index。
我以前會寫迭代式的 `find`，但最近我發現遞迴式更快...（信仰破滅 QAQ）
以下是 Kruskal 演算法的實作，瓶頸在於對邊權排序。
$Time: O(n ^ 2 \cdot (\log_2 n + \alpha(n))), Space: O(n ^ 2)$
```python=
def main():
from sys import stdin
from itertools import islice, chain
from operator import itemgetter
e = stdin.readline
def find(x): # DSU 找根節點
p = dsu[x]
if p < 0: return x
dsu[x] = p = find(p) # 路徑壓縮
return p
n, k = map(int, e().split())
dsu = [-1] * n # 初始化為 rank 1
for v, a, b in sorted(chain.from_iterable(
islice(((v, i, j) for j, v in enumerate(map(int, e().split()))), i)
for i in range(n)
), key=itemgetter(0)): # 按照邊權升冪排序
a, b = find(a), find(b)
if a == b: continue # 已經在同一組 不用再合併
# 合併
n -= 1 # 連通塊數量-1
if n < k: break # 不足k組 當前邊權為答案
# 按秩合併
if dsu[a] == dsu[b]: dsu[a] -= 1
elif dsu[a] > dsu[b]: a, b = b, a
# 合併
dsu[b] = a
print(v)
main()
```
~~雖然說 $\log$ 是常數~~，有沒有辦法可以 $O(n ^ 2)$？
再仔細想想，如果 MST 將自己身上最大的 $k-1$ 條邊都刪掉，就會變成 $1 + (k-1) = k$ 個連通塊，因此最後一條被刪掉的邊（就是 MST 上第 $k-1$ 大的邊）即為所求。
因為輸入是完全圖，使用 Prim 演算法 可以在 $O(n ^ 2)$ 內找出 MST，更適合此題。
有了 MST 後，找出第 $k-1$ 大的邊的部分可以用選擇演算法 $O(n)$（像是 C++ 中的 `nth_element`），而 python 只有內建基於 heap 的 `heapq.nlargest` $O(n \log_2 k)$。
$Time: O(n ^ 2 + n \log_2 k), Space: O(n ^ 2)$
```python=
def main():
from sys import stdin
from itertools import filterfalse
from heapq import nlargest
inf = float("INF")
e = stdin.readline
n, k = map(int, e().split())
G = [list(map(int, e().split())) for _ in range(n)]
mst = [False] * n
dis = [inf] * n
dis[0] = 0 # 從 0 開始建 MST
for _ in range(n): # n 次加點找出 MST
# 找出不在MST中 邊權最小的點
i = min(filterfalse(mst.__getitem__, range(n)), key=dis.__getitem__)
mst[i] = True # 連線 加入MST
# 由新的點往外擴張 更新邊權
row = G[i]
for j in filterfalse(mst.__getitem__, range(n)):
dis[j] = min(dis[j], row[j])
print(nlargest(k - 1, dis)[-1]) # 找第k-1大邊
main()
```
再砸一下「實務上最快的選擇演算法」Floyd–Rivest algorithm（但這題 $n \le 500$，~~常數比效果大~~）：
$Time: O(n ^ 2 + n), Space: O(n ^ 2)$
```python=
def main():
from sys import stdin
from itertools import filterfalse
inf = float("INF")
e = stdin.readline
n, k = map(int, e().split())
G = [list(map(int, e().split())) for _ in range(n)]
mst = [False] * n
dis = [inf] * n
dis[0] = 0 # 從 0 開始建 MST
for _ in range(n): # n 次加點找出 MST
# 找出不在MST中 邊權最小的點
i = min(filterfalse(mst.__getitem__, range(n)), key=dis.__getitem__)
mst[i] = True # 連線 加入MST
# 由新的點往外擴張 更新邊權
row = G[i]
for j in filterfalse(mst.__getitem__, range(n)):
dis[j] = min(dis[j], row[j])
from math import log, exp, copysign
# Floyd–Rivest algorithm from WIKIPEDIA
def select(le, ri):
while ri > le:
if ri - le > 300:
r = ri - le + 1
i = rk - le + 1
z = log(r)
s = 0.5 * exp(2 * z / 3)
sd = copysign(0.5 * (z * s * (r - s) / r) ** 0.5, i - r / 2)
_le = max(le, int(rk - i * s / r + sd))
_ri = min(ri, int(rk + (r - i) * s / r + sd))
select(_le, _ri)
t = dis[rk]
i, j = le, ri
dis[le], dis[rk] = dis[rk], dis[le]
if dis[ri] > t:
dis[ri], dis[le] = dis[le], dis[ri]
while i < j:
dis[j], dis[i] = dis[i], dis[j]
i, j = i + 1, j - 1
while dis[i] < t:
i += 1
while dis[j] > t:
j -= 1
if dis[le] == t:
dis[le], dis[j] = dis[j], dis[le]
else:
j += 1
dis[j], dis[ri] = dis[ri], dis[j]
if j <= rk:
le = j + 1
if j >= rk:
ri = j - 1
rk = len(dis) - k + 1
select(1, len(dis) - 1)
print(dis[-k+1]) # 找第k-1大邊
main()
```
再附上個用 `nth_element` 的 C++ 版本（僅主要邏輯）
```cpp=
#define REP(i, s, t) for (int i = (s); i < (t); ++i)
const int N = 500, inf = 0x3f3f3f3f;
int G[N][N], dis[N + 1]; // dis[N] = inf 作為 sentinel
bool mst[N];
void solve() {
memset(dis, 0x3f, sizeof(dis)); // dis 初始化為 inf
int n, k;
cin >> n >> k;
REP(i, 0, n) REP(j, 0, n) cin >> G[i][j]; // 輸入鄰接矩陣
dis[0] = 0; // 從 0 開始建 MST
REP(_, 0, n) {
// 找出不在MST中 邊權最小的點
int i = n;
REP(j, 0, n) if (not mst[j] and dis[j] < dis[i]) i = j;
mst[i] = 1; // 連線 加入MST
// 由新的點往外擴張 更新邊權
REP(j, 0, n) if (not mst[j] and G[i][j] < dis[j]) dis[j] = G[i][j];
}
nth_element(dis + 1, dis + n - k + 1, dis + n); // O(n) 找第k-1大邊
cout << dis[n - k + 1] << '\n';
}
```
## 吐槽
總之，這次的 p1, p2 挺無聊的。
至於 p3, p4，都需要稍微感性的觀察（淺淺通靈），但僅需要稍微超綱的知識，就能用毒瘤作法輕鬆砸過。
Sign in with Wallet
Connect another wallet