# APCS 20251116 高級題解
> 作者：暴力又被TLE
## [1. 字母配對](https://zerojudge.tw/ShowProblem?problemid=r626)
### 題述
> 給 $n$ 個長度 $k_{1 \sim n}$ 的 stack，裡面的物品以字母表示，並各自有分數。
> 每次可以選 top 字母相同的兩個 stack pop，並獲得兩者分數總合。
> 求最大分數總和？
>
> $n \le 6$
> $k_i \le 12$
> 因為個人變數使用的習慣，$n$ 是 stack 數量，$k_i$ 是 stack 長度，與原題不同
### 解法
考慮**多維DP**。
因為只需要考慮 stack 的 top，所以可以用一個長度為 $n$ 的數列，表示「每個 stack pop 了幾個」，像是 $[0,0,0]$ 就會是初始狀態，而 $[1, 0, 1]$ 就會是第 $1$、$3$ 個 stack 執行一次操作後的狀態。
想到這樣設計狀態後，轉移應該很顯然，比較麻煩的是如何實作。
狀態總共 $\Pi_{i = 1}^n k_i$ 個，轉移則 $O(n ^ 2)$，總共 $O(n ^ 2 \ \Pi_{i = 1}^n k_i)$，其實有點炸，但實務上不太容易跑滿，應該。
先放程式碼：
```python=
def main():
from sys import stdin
from functools import lru_cache
read = iter(stdin.read().split()).__next__
@lru_cache
def dp(idx):
best = 0
for i in range(1, n):
if idx[i] == len(stacks[i]): continue
for j in range(i):
if idx[j] == len(stacks[j]): continue
ic, iv = stacks[i][idx[i]]
jc, jv = stacks[j][idx[j]]
if ic == jc:
new_idx = list(idx)
new_idx[i] += 1
new_idx[j] += 1
best = max(best, dp(tuple(new_idx)) + iv + jv)
return best
n = int(read())
stacks = [[(read(), int(read())) for _ in range(int(read()))] for _ in range(n)]
print(dp((0,) * n))
main()
```
首先，題目的輸入就不太 python-friendly，同一行內有數字、字元，以下提供一種特殊的輸入方法，變成類似 Cpp 的 `cin`，每次呼叫就讀入一個 token，`str.split` 預設會切割所有空白 ` ` 和換行 `\n`，因此可以這樣使用。
把所有 stack 讀入 `stacks`，並由初始狀態 `(0, 0, ..., 0)` 開始 Top-down DP，並用 `functools.lru_cache` 記憶化。
`lru_cache` 是一個「裝飾器」，就是「輸入是函數、輸出也是函數的一個函數」，他的主要邏輯大概像：
```python=
def cache(function: Callable) -> Callable:
memo = {}
def wrapper(*args):
if args not in memo:
memo[args] = function(*args)
return memo[args]
return wrapper
```
實際上他還實作了很多額外的東西，像是 LRU（Least Recent Used）就是會把 `memo` 中太久沒用到的 `key` 丟掉，進而節省空間，但平常不會設定 `maxsize`，所以沒有阿茲海默的問題，他有一個專門的 `maxsize=None` 版本 `functools.cache`，然而因為在 python 3.9 才加入，因此在 ZJ 用不了（目前 APCS 在 Python 3.10、ZJ 仍在 Python ）；除此之外，他也是 thread-safe 的，保證了安全性，但也意味著他的效率會比較低。
因為他是用 `dict` 做記憶化，輸入 function 的 argument **必須 hashable**，因此在遞迴地 call `dp` 時要將 `new_idx: list` 轉成 `tuple` 再傳入。
這個解寫起來十分簡單直覺，但常數太大被 ZJ TLE 了。
來看看第二個實作：
```python=
def main():
from sys import stdin
read = iter(stdin.read().split()).__next__
def encode(arr):
res = 0
b = 1
for v in arr:
res += v * b
b *= base
return res
def dp(idx):
key = encode(idx)
if ~(val := memo[key]): return val
best = 0
for i in range(1, n):
if idx[i] == len(l[i]): continue
ic, iv = l[i][idx[i]]
for j in range(i):
if idx[j] == len(l[j]): continue
jc, jv = l[j][idx[j]]
if ic == jc:
new_idx = list(idx)
new_idx[i] += 1
new_idx[j] += 1
best = max(best, dp(new_idx) + iv + jv)
memo[key] = best
return best
n = int(read())
l = [[(read(), int(read())) for _ in range(int(read()))] for _ in range(n)]
base = max(map(len, l)) + 1
memo = [-1] * (base ** n)
print(dp((0,) * n))
main()
```
主要改動是將 `lru_cache` 換成一個 `memo: list[int]`，並且用 `encode` 函數將**狀態數列**以 $k+1$ 進位轉換成**數字**作為 `memo` 的 index。這個就能過 ZJ 了。
進一步加速：
```python=
def main():
from sys import stdin
read = iter(stdin.read().split()).__next__
n = int(read())
l = []
lens = []
base = 1
bases = []
for i in range(n):
k = int(read())
lens.append(k)
bases.append(base)
base *= k + 1
l.append([(read(), int(read())) for _ in range(k)])
dp = [-1] * base
ans = dp[0] = 0
its = [0] * n
for idx in range(base):
v = dp[idx]
if v != -1:
if v > ans: ans = v
for i in range(1, n):
if its[i] == lens[i]: continue
ic, iv = l[i][its[i]]
iv += v
for j in range(i):
if its[j] == lens[j]: continue
jc, jv = l[j][its[j]]
if ic != jc: continue
new_idx = idx + bases[i] + bases[j]
nv = iv + jv
if nv > dp[new_idx]:
dp[new_idx] = nv
for i in range(n):
its[i] += 1
if its[i] <= lens[i]: break
its[i] = 0
print(ans)
main()
```
改成 Bottom-up 省去遞迴的大開銷，並且用 `its` 手刻加法進位器，**均攤來說**該迴圈的時間複雜度是 $O(1)$。
然而實際上這個解沒有快很多，因為有很多狀態無法到達，可以直接跳過，但維護 `its` 卻創造了固定開銷。
### 推類題
（夾帶私貨）
- [TIOJ 2371. E. 迷宮鑰匙圈 (Maze)](https://tioj.ck.tp.edu.tw/problems/2371) - 多維 DP
- [APCSS. 太簡單的石板（Easy-peasy Puzzel）](https://apcs-simulation.com/problem/apcs1103) - 多維 DP（極難）
- [APCSS. 暴力又被TLE 想讓人滅台](https://apcs-simulation.com/problem/apcs1703) - 進位制轉換(?)
## [2. 列印工廠](https://zerojudge.tw/ShowProblem?problemid=r627)
### 題述
> 給 $n$ 個工作的 最早開始時間、最晚結束時間、所需時間。
> 排列出一個順序，使工作互不重疊，並最大化「工作之間的最短間隔」。
>
> $n \le 8$
> $0 \le \text{時刻} \le 1000$
### 解法
看到 $n \le 8$ 應該可以大膽猜測時間複雜度帶 $n!$ 項；又看到「最大化最小值」，有 95% 以上是在考「對答案二分搜」。分析完考點，這題就做完了。
實際上，這屬於「單機排程」（single-machine scheduling）問題，這類問題通常都是 NP-hard，這題應該也能歸約到 NPC。
對於一個固定的排列，最大化的「最短間隔」可以在 $O(n \log R)$ 內對答案二分搜求得，因此枚舉 $n!$ 種排列，並且取最大即為答案。
「最大化」的二分搜，我自己很容易寫錯邊界條件的 +1-1（一般的二分搜模板都是最小化），因此我現在都習慣把一個反向的 `range` 當成新的值域，在上面二分搜，從此沒寫錯過。
枚舉全排列的部分，請善用 `itertools`、善待自己。`itertools` 裡面有無數寶藏，等著你挖掘。
```python=
def main():
from sys import stdin
from itertools import permutations
from bisect import bisect_left
e = stdin.readline
n = int(e())
s = [0] * n
d = [0] * n
t = [0] * n
for i in range(n):
s[i], d[i], t[i] = map(int, e().split())
lim = max(d)
# check if gap can be >= x
def check(x: int) -> bool:
end = -x
for i in p:
end = max(end + x, s[i]) + t[i]
if end > d[i]: return False
return True
ans = 0
r = range(lim, 0, -1)
for p in permutations(range(n)):
x = bisect_left(r, True, key=check)
if x < lim and r[x] > ans:
ans = r[x]
print(ans)
main()
```
令人肝腸寸斷的是，`bisect` 在 python 3.10 才加入 `key` 這個 argument，所以上面的程式碼在 ZJ 上會直接 RE，但是在 APCS 還是能用的！
如果你在考場上忽然發現這個悲劇的事實，然而平常被 `bisect` 寵壞了忘記怎麼二分搜，可以進 Python IDLE $\to$ File $\to$ Module Browser，輸入 `bisect`，就會跳出原始碼，就可以複製貼上啦！
<img src="https://hackmd.io/_uploads/rydMqa_ebe.png" alt="Image" width="80%"/>
下面我們好好寫二分搜：
```python=
def main():
from sys import stdin
from itertools import permutations
e = stdin.readline
n = int(e())
s = [0] * n
d = [0] * n
t = [0] * n
for i in range(n):
s[i], d[i], t[i] = map(int, e().split())
lim = max(d)
def check(x):
end = -x
for i in p:
end = max(end + x, s[i]) + t[i]
if end > d[i]: return False
return True
ans = 0
for p in permutations(range(n)):
if not check(ans): continue
lo, hi = ans, lim
while lo < hi:
mid = lo + hi >> 1
if check(mid):
lo = mid + 1
else:
hi = mid
if lo > ans:
ans = lo - 1
print(ans)
main()
```
### 推類題
- [LC 3710. Maximum Partition Factor](https://leetcode.com/problems/maximum-partition-factor/description/) - 對答案二分搜
- [APCSS. 卡拉 OK（Karaoke）](https://apcs-simulation.com/problem/apcs2104_ex_py) - 對答案二分搜
- [APCSS. 分數密碼 (Fraction)](https://apcs-simulation.com/problem/apcs1303) - 枚舉排列
- [LC 2081. Sum of k-Mirror Numbers](https://leetcode.com/problems/sum-of-k-mirror-numbers/description/) - 枚舉排列
## [3. 翻來覆去](https://zerojudge.tw/ShowProblem?problemid=r628)
### 題述
> 給定一個 $1 \sim n$ 的排列，表示一個 Stack，還有另一個空的 Stack。
> 每次操作可以：
> 1\. `pop` 其中一個 Stack 並輸出
> 2\. `pop` 並 `push` 到另一個 Stack
> 求輸出 $1 \sim n$ 至少需要幾次操作？
>
> $n \le 1e5$
### 解法
由小到大枚舉 $i = 1 \sim n$，每次找到 $i$ 的位置，並把它前面的全部「倒」到另一個 Stack，再輸出。
令 $pos_i$ 為數字 $i$ 在輸入的數列 $a_{1 \sim n}$ 中的位置。
我們可以發現，所求就等於：
$$
\sum_{i=1}^{n} \bigl| { j\in[i,n]\ :\ pos_j\in[\min(pos_{i-1},pos_i),\max(pos_{i-1},pos_i)] }\bigr|
$$
也就是對於每個 $i$ 計數 $j \ge i$ 且 $j$ 在 $i-1, i$ 之間的數量。
這其實跟經典的「逆序數對」問題非常像，他是計數 $i \lt j$ 且 $a_i \gt a_j$ 的數量，而這題有分治的解法（一邊 merge sort 一邊計數），然而分治常數大又難寫，因此大部分人都會直接使用可以「單點加值、查詢區間和」的資料結構，最適合、最簡單的資結是「樹狀數組 BIT（Binary Indexed Tree）」，可以先看 [這篇文章](https://cp.wiwiho.me/fenwick-tree/) 學習。
先看不使用資結的 naive $O(n ^ 2)$ 解法：
首先輸入並算出 `pos`。因為 BIT 是 1-based，所以這邊將 `pos` 也用 1-based 存，並定義 `pos[0] = 0`。
接著就是由大到小遍歷 `v`，這樣才能依序將值加入 BIT，每次加入前先將 `sum(bit[s:t])` 加入答案。
但這樣其實算的是 $\gt v$ 的數量而不是 $\ge v$，所以將 `ans` 初始化為 $n$。
```python=
def main():
from sys import stdin
e = stdin.readline
n = int(e())
l = list(map(int, e().split()))
pos = [0] * (n + 1)
for i, v in enumerate(l, 1):
pos[v] = i
ans = n
bit = [0] * (n + 1)
i = pos[n]
for v in range(n - 1, -1, -1):
ni = pos[v]
s, t = i, ni
if s > t: s, t = t, s
ans += sum(bit[s:t])
bit[i] += 1
i = ni
print(ans)
main()
```
接下來加上 BIT 的維護：
`18 ~ 23` 行的兩個 `while`，這是區間查詢 BIT 的特殊寫法（我在洛谷上學到的：[浅谈树状数组的优化及扩展](https://www.luogu.com.cn/article/790vjft4)），稍微快也比較好寫。
```python=
def main():
from sys import stdin
e = stdin.readline
n = int(e())
l = list(map(int, e().split()))
pos = [0] * (n + 1)
for i, v in enumerate(l, 1):
pos[v] = i
ans = n
bit = [0] * (n + 1)
i = pos[n]
for v in range(n - 1, -1, -1):
ni = pos[v]
s, t = i, ni
if s > t: s, t = t, s
while t > s:
ans += bit[t]
t &= t - 1
while s > t:
ans -= bit[s]
s &= s - 1
x = i
while x <= n:
bit[x] += 1
x += x & -x
i = ni
print(ans)
main()
```
於是就這樣 AC 了！
---
能不能再更快？
觀察到：因為題目給定的數列是排列，即保證沒有重複數字，因此 BIT 維護的那個數列中只有 $0, 1$，最適合維護 $0, 1$ 的資料結構就是 `bitset` 了！
簡單來講，使用分塊法，塊長 $64$，每次區間查詢時，第一塊和最後一塊可能不完整，因此使用 `bitset` 查詢，而中間的塊則用 BIT 維護；需要特判查詢區間在同一塊內的情況。
時間複雜度 $O(n \log \frac{n}{64})$，空間從原本 $2e5$ 個 `int` 降到 $1e5 + 2 \times \frac{1e5}{64}$ 個 `int`。
```cpp=
#include <iostream>
using namespace std;
#define pcc __builtin_popcountll
char num[20], *p1 = num;
int pos[100001], bit[1564];
unsigned long long bitset[1564];
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
int m = (n >> 6) + 1;
long long ans = n;
for (int i = 1, v; i <= n; ++i) cin >> v, pos[n - v] = i;
for (int i = pos[0], v = 1; v <= n; ++v) {
int ni = pos[v], s, t;
if (i < ni) s = i, t = ni;
else s = ni, t = i;
if (s >> 6 == t >> 6) {
ans += pcc(bitset[s >> 6] & (-1ull << (s & 63)) & (-1ull >> (63 ^ (t & 63))));
} else {
ans += pcc(bitset[s >> 6] >> (s & 63))
+ pcc(bitset[t >> 6] << (63 ^ (t & 63)));
++(s >>= 6); t >>= 6;
for (; t > s; t &= t - 1) ans += bit[t];
for (; s > t; s &= s - 1) ans -= bit[s];
}
bitset[i >> 6] |= 1ull << (i & 63);
for (++(i >>= 6); i <= m; i += i & -i) ++bit[i];
i = ni;
}
cout << ans << '\n';
return 0;
}
```
### 推類題
海苔裡面是考點爆雷，建議不要開。
- [CSES. Josephus Problem II](https://cses.fi/problemset/task/2163) - BIT ||上二分搜（請不要用平衡樹吃毒）||
- [CSES. Nested Ranges Count](https://cses.fi/problemset/task/2169) - BIT ||+ 離散化||
- [CSES. Increasing Subsequence II](https://cses.fi/problemset/task/1748) - BIT ||優化 DP 轉移||
- [CSES. Distinct Values Queries](https://cses.fi/problemset/task/1734) - BIT ||+ 離線 + 掃描線||
- [CSES. Increasing Array Queries](https://cses.fi/problemset/task/2416) - BIT ||+ 差分 + 離線 + 掃描線||
- [CSES. Polynomial Queries](https://cses.fi/problemset/task/1736) - BIT ||+ 數學（開三棵分別維護 $ax^2 + bx + c$ 的 $a, b, c$）||
- [CSES. Sliding Window Mex](https://cses.fi/problemset/task/3219) - BIT ||上二分搜||
- [CSES. Pyramid Array](https://cses.fi/problemset/task/1747) - BIT ||+ 有趣思考||
### 延伸閱讀：線段樹
[線段樹全面剖析](https://hackmd.io/@ericshen19555/segment_tree_weaker_treap_better)（雖然仍 WIP 但基礎的都完成了）
Sign in with Wallet
Connect another wallet