# 2024/9/28 APCS 第九場模擬賽 題解
# Chung 的 GPA (Chung's GPA)
> 出題者：Chung
> 難度：p1
> 考點：迴圈、條件判斷
### Statement
Chung 最近也成為了大學生，每天為了拚 GPA 而努力著，但是等第積分與等第成績的轉換搞得 Chung 眼花撩亂，所以他將成績單積分與級分的轉換表提供給你如下，希望你可以幫忙將等第成績計算成等第積分。
Chung 的成績單會有以下資訊：
- 課程代號 $x\ (1 \le x \le 100)$
- 等第 $s$ (保證 $s$ 不會出現不在表格內的等第)
但 Chung 的成績單有個小問題，因為同個課程可能會被更改分數，但成績單不會將過去的成績移除，所以可能會出現相同的課程代號但有不同的成績發生，遇到這類狀況請以最後出現的為主。
### Input
輸入將有一個整數 $n\ (1 \le n \le 100)$，代表 Chung 修的課程數量。
接著將有 $n$ 行，每行有兩個資訊：課程代號 $x$ 和等第成績 $s$。
### Output
請輸出等第成績轉換到等第積分的加總。
### Testcase
- Input 1
```
4
1 A+
2 A
3 B
4 C
```
- Output 1
```
13.3
```
- Input 2
```
5
1 A+
2 A
3 B
4 C
1 A
```
- Output 2
```
13.0
```
### Subtask
- Subtask 1 (50%) - 保證課程代號不會重複
- Subtask 2 (50%) - 無其他限制
### Solution
- Subtask 1
- 將題目給定的轉換表用任何方式打進程式裡 (陣列、vector、dict、map ...)
- 對於每個輸入，用迴圈找到對應的分數，加進答案
- 最後輸出答案到小數點後一位即可
- Subtask 2
- 因為有可能成績最後會被刷掉，所以要先儲存每個課程代號對應的分數，最後再一起統計
- 小技巧 (官解的做法)：可以先把所有分數乘上 $10$ 變成整數，最後輸出的時候再拆分，可以保證沒有小數點誤差 (雖然這題用 float / double 都會過)
### Code
- Subtask 1
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,x;
string s;
vector<string> grade {"A+", "A", "A-", "B+", "B", "B-", "C+", "C", "C-", "D", "E", "X"};
int GPA[12] = {43, 40, 37, 33, 30, 27, 23, 20, 17, 10, 0, 0};
int main(){
cin>>n;
int ans = 0;
for(int i=0;i<n;i++){
cin>>x>>s;
for(int j=0;j<grade.size();j++){
if(grade[j] == s){
ans += GPA[j];
break;
}
}
}
cout<<ans/10<<'.'<<ans%10<<"\n";
return 0;
}
```
- Subtask 2
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,x;
string s;
int score[105];
vector<string> grade {"A+", "A", "A-", "B+", "B", "B-", "C+", "C", "C-", "D", "E", "X"};
int GPA[12] = {43, 40, 37, 33, 30, 27, 23, 20, 17, 10, 0, 0};
int main(){
cin>>n;
memset(score, -1, sizeof(score));
for(int i=0;i<n;i++){
cin>>x>>s;
for(int j=0;j<grade.size();j++){
if(grade[j] == s){
score[x] = GPA[j];
break;
}
}
}
int ans = 0;
for(int i=1;i<=100;i++){
if(score[i] == -1) continue;
ans += score[i];
}
cout<<ans/10<<'.'<<ans%10<<"\n";
return 0;
}
```
- Python
```python=
mp = {
"A+": 4.3,
"A": 4.0,
"A-": 3.7,
"B+": 3.3,
"B": 3.0,
"B-": 2.7,
"C+": 2.3,
"C": 2.0,
"C-": 1.7,
"D": 1.0,
"E": 0.0,
"X": 0.0
}
scs = {}
n = int(input())
for i in range(n):
s, c = input().split()
scs[s] = mp[c]
print(round(sum(scs.values()), 1))
```
# 飛鏢 (Dart)
> 出題者：折蚌太郎
> 難度：p2
> 考點：迴圈、陣列
### Statement
由於 Chung 教授實在是太會丟飛鏢了，現有的飛鏢盤面已經完全攻略，毫無挑戰性可言，因此，Chung 教授決定自己研發一款飛鏢盤面與規則。
盤面變成一個 $N$ 列 $M$ 行，總共 $N \times M$ 格的矩形。第 $i$ 列的第 $j$ 格的座標是 $(i, j)$，上面有一個整數 $S_{i, j}$，表示飛鏢射中這格能得到的分數。為了增加遊戲的趣味性，Chung 教授又想出了特殊的計分方法：
1. 當同個格子被**連續**丟到 $x$ 次，該格的分數會乘以 $1 + 2 + \cdots + x$ 倍 $(x \ge 1)$
2. 當飛鏢丟出界，會把現有的所有倍數加成全部清空，並且總分扣掉**飛鏢座標與盤面的曼哈頓距離**分
3. 分數計算是最後才一起算，所以並不是每輪丟完就會加分
現在，給你 Chung 教授的試玩紀錄，首先會給一個數字 $v$
$v = 1$ 表示接下來要輸入飛鏢的座標
$v = 2$ 表示 Chung 教授在詢問分數
Chung 教授總共丟了 $K$ 枚飛鏢，每個飛鏢丟到的座標為 $(R_k, C_k)$ (注意 k 的大小寫)。Chung 教授在遊玩過程中會詢問目前有幾分，總共會詢問 $Q$ 次，當 Chung 教授詢問時，請你輸出按照目前盤面所計算出來的分數。(輸入的順序當然是依照 Chung 教授丟飛鏢和問問題的順序)
再講清楚：
列是橫的，行是直的
如果連續丟到同一格，中途丟到別格，後來又丟到這格，倍數會重算(ex: 連續三次丟到 $S_{1, 1}$，會有 $1 + 2 + 3 = 6$ 倍的加成，中斷後會維持 6 倍，但是當再丟到一次 $S_{1, 1}$，倍數就變回 $1$ 了)
$1 + 2 + \cdots + x = \frac{x(x+1)}2$
「飛鏢座標與盤面的曼哈頓距離」的意思是：假設飛鏢的座標是 $(a_1, b_1)$，盤面上與 $(a_1, b_1)$ 最近的格子的座標是 $(a_2, b_2)$，曼哈頓距離就是 $|a_1 - a_2| + |b_1 - b_2|$
「分數計算是最後才一起算」的意思是：每個格子的分數到最後會是一個確定的數字，再去計算每個格子被射中幾次，才把那格所得的分數加進總分中。
### Input
第一列有 $2$ 個數字 $N, M\ (1 \le N \le 17, 1 \le M \le 19)$
接下來有 $N$ 列，每列 $M$ 個數字，第 $i$ 列的第 $j$ 個數字表示 $S_{i, j}\ (1 \le S_{i, j} \le 100)$
第 $N + 2$ 列(接續上面的)有 $2$ 個數字 $K, Q\ (1 \le K \le 47, 1 \le Q \le 13)$
接下來有 $K + Q$ 列，每列的第一個數字是 $v\ (1 \text{ 或 } 2)$
「1」後面有兩個整數代表 $(R_k, C_k)\ (-23 \le R_k, C_k \le 29)$；
「2」代表詢問
保證只有 $Q$ 個「2」，其餘都是 $(R_k, C_k)$，並且最後一列一定是「2」
### Output
請在「2」的時候輸出盤面的分數
### Input Format
$N\ M$
$S_{1,1} \ \ S_{1,2} \ \dots \ S_{1,M}$
$S_{2,1} \ \ S_{2,2} \ \dots \ S_{2,M}$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots$
$S_{N,1} \ \ S_{N,2} \ \dots \ S_{N,M}$
$K\ Q$
$\vdots$
$2$
$1\ R_k\ C_k$
$\vdots$
$1\ R_K\ C_K$
$2$
### Output Format
$score_1$
$score_2$
$\ \ \ \ \vdots$
$score_Q$
### Testcase
- Input 1
```
3 3
1 2 3
4 5 6
7 8 9
3 2
1 1 2
1 2 2
2
1 2 2
2
```
- Output 1
```
7
32
```
- Input 2
```
1 1
7
4 3
1 1 1
1 1 1
2
1 2 3
2
1 1 1
2
```
- Output 2
```
42
11
18
```
- Input 3
```
2 3
2 3 5
1 4 6
7 4
1 3 -1
1 3 -1
2
1 1 2
1 1 2
2
1 1 2
2
1 3 -1
1 1 2
2
```
- Output 3
```
-6
12
48
3
```
### Subtask
- Subtask 1 (50%) - 飛鏢不會出界
- Subtask 2 (50%) - 無特殊限制
### Note
範例測資一說明：
第一鏢丟到 $(1, 1)$，$S_{1, 1} = 2$
第二鏢丟到 $(2, 1)$，$S_{2, 1} = 5$
詢問現在分數，所以輸出 $S_{1, 1} + S_{2, 1} = 7$ 分
第三鏢丟到 $(2, 1)$，因為連續兩次，所以 $S_{2, 1}$ 變為 $5 \times (1 + 2) = 15$
詢問現在分數，所以輸出 $S_{1, 1} + S_{2, 1} + S_{2, 1} = 32$
範例測資二說明：
第一鏢丟到 $(1, 1)$，$S_{1, 1} = 7$
第二鏢丟到 $(1, 1)$ 使得 $S_{1, 1}$ 變成 $21$
詢問現在分數，所以輸出 $S_{1, 1} + S_{1, 1} = 42$ 分
第三鏢丟到 $(2, 3)$，與盤面的曼哈頓距離是 $3$，要扣 $3$ 分，並清空所有倍數，$S_{1, 1}$ 變回 $7$
詢問現在分數，所以輸出 $S_{1, 1} + S_{1, 1} - 3 = 11$ 分
第四鏢丟到 $S_{1, 1} = 7$
詢問現在分數，所以輸出 $S_{1, 1} + S_{1, 1} - 3 + S_{1, 1} = 18$ 分
### Solution
- Subtask 1
開三個陣列，一個代表初始的 $S_{i, j}$，一個代表 $S_{i, j}$ 的倍數，一個代表 $(i, j)$ 上有幾個飛鏢。由於要記錄連續丟到同一格幾次，需要一個變數紀錄上一個飛鏢丟到的座標，即可判斷是否與前一個相同，如果相同，則把連續次數 + 1；否則，先把現有的連續次數利用公式計算完後更新到倍數陣列中，再把連續次數改為 1 (注意不是 0 哦)。最後記得把現在的飛鏢丟到的座標上的飛鏢數量 + 1。
- Subtask 2
所有要更新到陣列的操作前，都要先判斷是否在界內。計算曼哈頓距離，如果不想動腦，可以直接枚舉所有格子，一一計算個別的距離再取最小值(因為是 p2，學會如何暴力枚舉也是很重要的)。聰明一點的做法是：分為橫向和縱向兩部分處理，假設飛鏢的座標是 $(R, C)$，若 $R < 1$，則是 $1 - R$；若 $1 \le R \le N$，則是 $0$；若 $R > N$，則是 $R - N$，$C$ 同理。但實際上不會那麼複雜，這只是為了講解才看起來很繁瑣，總之，可能成為答案的就是 $1 - R$ 或 $R - N$，會發現上面切的三段，恰好會使這兩個式子的正負呈現 $\{+, -\}, \{-, -\}, \{-, +\}$ 的規律，所以只需要寫一個函數，正的時候回傳自己，負的時候回傳 $0$，兩式代入此函式後相加即為曼哈頓距離。
理解/解讀這個式子的方式，可能有點數學。
在數線上，大家應該都學過 $|a - b|$ 的意思其實是 $a$ 與 $b$ 的距離，那麼 $a - b$ 呢？其實就是「$a$ 在 $b$ 的右邊多少」，負值代表在左邊，或「$b$ 在 $a$ 的左邊多少」$\big(-(b - a) = a - b\big)$。
回到題目，我們要求的是「$1$ 在 $R$ 的右邊多少」與「$R$ 在 $N$ 的右邊多少」。這裡的右，是真的要往右，也就是計算出來的值的**正的部分**，所以才會需要寫那個函式。
### Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, m, s[18][20], x[18][20], dart[18][20], foul;
void reset_x() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
x[i][j] = 1;
}
int pos(int v) {
return (v > 0)*v;
}
int manhattan(int a1, int b1) {
return pos(a1 - n) + pos(1 - a1) +
pos(b1 - m) + pos(1 - b1);
}
void Chung() {
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans += s[i][j]*x[i][j]*dart[i][j];
cout << ans - foul << '\n';
}
int main() {
cin >> n >> m;
reset_x();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> s[i][j];
int k, q; cin >> k >> q;
int v, pr = -100, pc = -100, combo = 0;
while (k + q) {
cin >> v;
if (v == 1) {
k--;
int r, c; cin >> r >> c;
if (r == pr && c == pc)
combo++;
else {
if (!manhattan(pr, pc))
x[pr][pc] = combo*(combo + 1) >> 1;
combo = 1;
}
int dist = manhattan(r, c);
if (dist) {
reset_x();
foul += dist;
}
else dart[r][c]++;
pr = r;
pc = c;
}
else {
q--;
if (!manhattan(pr, pc))
x[pr][pc] = combo*(combo + 1) >> 1;
Chung();
}
}
return 0;
}
```
- Python
```python=
from collections import defaultdict
n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(n)]
k,q = map(int,input().split())
cnt = defaultdict(int)
mul = defaultdict(int)
pre = ()
bad = 0
for _ in range(k+q):
o = list(map(int,input().split()))
if o[0]==1:
x,y = p = tuple(o[1:])
if x<1 or x>n or y<1 or y>m:
for k in mul:
mul[k] = 0
bad += max(1-x,x-n,0)+max(1-y,y-m,0)
else:
cnt[p]+=1
if pre==p:
mul[p]+=1
else:
mul[p] = 1
pre = p
else:
ans = 0
for k,v in cnt.items():
mu = max(1,mul[k])
x = s[k[0]-1][k[1]-1]
ans += v*x*mu*(mu+1)//2
print(ans-bad)
```
# 變異賓果 (Bingo)
> 出題者：Howard & wym
> 難度：3
> 考點：樹
### Statement
台灣有一個非常有名的學院，名為大智慧學苑，裡面總共有 $n$ 個學員，今天學苑院長 Chung 想要舉辦一個賓果大賽，但這場比賽和以往的不一樣，為了增加比賽的難度，每一輪比較的方法也大有不同。賓果的大小為 $3\times 3$，且有兩種比較方式，第一種為由左上往右下比較，第二種為右下往左上比較，一場比賽可能會有多個學員，比較方式也都相同。
如下圖，若是使用第一種比較方法，則左邊比較順序的數字為157253123，右邊比較順序的數字為158252123，所以右邊的比較大。
若是使用第二種比較方法，則左邊比較順序的數字為321352751，右邊比較順序的數字為321252851，所以左邊的比較大。
深度：在此定義為根節點深度為 1 ，根節點的子節點深度為 2 ，以此類推。
在此我們定義在什麼情況下的比賽方式為何，若此節點為比賽節點且深度為奇數時 (如下圖節點 1 ) ，則比較方式採用第二種比較方式，若此比賽節點深度為偶數時 (如下圖 2, 3 這些節點) ，則採用第一種比較方式。
而由於 Chung 特別喜歡某些學員，於是會自己先排定好對他們有利的賽程，所以賽程表可以變成一張類似樹的結構 (保證編號 1 為根) ，最後想要求出獲勝的學員以及他賓果上面的數字。
以下為一個例子，編號 4、5、6、7 分別為一個學員，編號 1、2、3 分別代表一場比賽，在編號 2 和編號 3 的比賽中，是使用第一種比較方法 (2, 3 節點深度為 2 ) ，編號 1 則為第二種比較方法 (1 節點深度為 1 ) 。在此注意由於編號 3 的這場比較只有一個人，故他會直接晉級下一輪，編號 2 則是 4、7 這兩個學員互相比較，在編號 1 的比賽中則是編號 5 學員、贏得編號 2 比賽的學員以及編號 7 學員三者互相比較，最後要找的答案就是贏得編號 1 這場比賽的選手以及他的賓果號碼。
### Input
第1行有兩個數字 $n, m$ 為總共有幾場比賽和總共有幾位學員
第2行到 $n + m$ 每行有兩個數字 $u、v$ 代表在賽程樹狀圖中， $u、v$ 相連
接下來為每個學員的編號和賓果出的數字。第一行為在樹狀圖的編號 $k$ (保證是葉子) ，接下來會有 $3\times 3$ 個數字，代表學員編號 $k$他賓果上面的數字，保證任兩個人賓果不可能一樣。
$1 \leq \text{賓果的編號} \leq 10^9$
$1 \leq n + m \leq 2\times 10^5$
$1 \leq u, v \leq n + m,u \neq v$
### Output
輸出最後贏家編號和賓果上面的數字
### Input Format
$n\space m$
$u_1 \space v_1$
$u_2 \space v_2$
$u_3 \space v_3$
$.$
$.$
$.$
$u_{m-1} \space v_{m-1}$
$k_1$
$k_{1_{1,1}} \space k_{1_{1,2}} \space k_{1_{1,3}}$
$k_{1_{2,1}} \space k_{1_{2,2}} \space k_{1_{2,3}}$
$k_{1_{3,1}} \space k_{1_{3,2}} \space k_{1_{3,3}}$
$k_2$
$k_{2_{1,1}} \space k_{2_{1,2}} \space k_{2_{1,3}}$
$k_{2_{2,1}} \space k_{2_{2,2}} \space k_{2_{2,3}}$
$k_{2_{3,1}} \space k_{2_{3,2}} \space k_{2_{3,3}}$
$k_3$
$k_{3_{1,1}} \space k_{3_{1,2}} \space k_{3_{1,3}}$
$k_{3_{2,1}} \space k_{3_{2,2}} \space k_{3_{2,3}}$
$k_{3_{3,1}} \space k_{3_{3,2}} \space k_{3_{3,3}}$
$.$
$.$
$.$
$k_m$
$k_{m_{1,1}} \space k_{m_{1,2}} \space k_{m_{1,3}}$
$k_{m_{2,1}} \space k_{m_{2,2}} \space k_{m_{2,3}}$
$k_{m_{3,1}} \space k_{m_{3,2}} \space k_{m_{3,3}}$
### Output Format
$k$
$k_{1,1} \space k_{1,2} \space k_{1,3}$
$k_{2,1} \space k_{2,2} \space k_{2,3}$
$k_{3,1} \space k_{3,2} \space k_{3,3}$
### Testcase
- Input 1
```
3 4
1 2
1 3
1 5
2 6
2 4
3 7
4
1 5 7
2 5 3
1 2 3
5
7 8 9
3 5 2
1 2 3
6
1 5 8
2 5 2
1 2 3
7
5 2 10
3 5 2
1 2 3
```
- Output 1
```
7
5 2 10
3 5 2
1 2 3
```
### Subtask
- Subtask 1 (40%) - 必定是完全二元樹&給邊的時候 $u$ 一定是 $v$ 的父節點
- Subtask 1 (60%) - 無特別限制
### Solution
- Subtask 1 by horzward
- 可以好好利用二元樹的性質，在寫樹的遍歷時可以更簡單，首先先用 BFS 去將所有節點的深度定義好，接下來使用一個陣列 `arr` 第一維度代表節點，若此節點維葉子，則為那位同學的賓果，若為一場比賽，則為這個比賽贏家的賓果，為了方便後續實作，在輸入時就直接比較最底層比較完成，接下來再跑一次 BFS 模擬所有比賽情況，最後在 `arr[1]` 的賓果就是贏家
- Subtask 2 by horzward
- 使用 DFS 模擬樹的遍歷，在寫DFS時， `arr` 陣列定義和上方相同，若目前節點為葉子，則直接回傳賓果，否則，就開始對此點的所有兒子進行比較，最後再 return 比較最大者就是答案。
### Code
- Subtask 1
```cpp=
#include <iostream>
#include <array>
#include <queue>
using namespace std;
using ai = array<int, 9>;
const int N = 1e5+5, K = 9;
int L[N], R[N], P[N], lvl[N];
bool leaf[N];
ai arr[N];
queue<int> q;
ai cmp(ai x, ai y, bool bck)
{
if(!bck)
return (x>y? x: y);
for(int i=K-1; i>=0; i--)
{
if(x[i] > y[i])
return x;
else if(y[i] > x[i])
return y;
}
return x;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=0, x, y; i<n+m-1; i++)
{
cin >> x >> y;
if(L[x]) R[x] = y;
else L[x] = y;
P[y] = x;
}
q.push(1);
lvl[1] = 1;
while(q.size())
{
int now = q.front();
q.pop();
if(!L[now] && !R[now]) continue;
lvl[L[now]] = lvl[R[now]] = lvl[now] + 1;
q.push(L[now]), q.push(R[now]);
}
q = queue<int>();
for(int i=0, x; i<m; i++)
{
cin >> x;
leaf[x] = 1;
for(int j=0; j<K; j++)
cin >> arr[x][j];
if(!arr[P[x]][0]) arr[P[x]] = arr[x];
else arr[P[x]] = cmp(arr[P[x]], arr[x], lvl[P[x]] & 1), q.push(P[x]);
}
while(q.size())
{
int now = q.front();
q.pop();
if(now == 1)
break;
if(!arr[P[now]][0]) arr[P[now]] = arr[now];
else arr[P[now]] = cmp(arr[P[now]], arr[now], lvl[P[now]] & 1), q.push(P[now]);
}
ai ans = arr[1];
for(int i=1; i<=n+m; i++)
if(leaf[i] && ans == arr[i])
cout << i << "\n";
for(int i=0, j=0; j<3; j++)
{
for(int k=0; k<3; k++)
cout << ans[i++] << " \n"[k==2];
}
}
```
- Subtask 2
```cpp=
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int N = 1e5+5, K = 9;
vi a[N];
vi s[N];
vi cmp(vi x, vi y, bool bck)
{
if(!bck)
return (x>y? x: y);
for(int i=K-1; i>=0; i--)
{
if(x[i] > y[i])
return x;
else if(y[i] > x[i])
return y;
}
return x;
}
vi dfs_ans(int x, int p, int p_len)
{
int len = p_len + 1;
if(s[x].size())
return s[x];
vi ret(K, -1);
for(int i: a[x])
{
if(i == p)
continue;
dfs_ans(i, x, len);
ret = cmp(ret, s[i], len & 1);
}
return s[x] = ret;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=0, x, y; i<n+m-1; i++)
{
cin >> x >> y;
a[x].push_back(y), a[y].push_back(x);
}
for(int tt=0; tt<m; tt++)
{
int x;
cin >> x;
for(int i=0, y; i<K; i++)
{
cin >> y;
s[x].push_back(y);
}
}
vi ans = dfs_ans(1, 0, 0);
for(int i=n+1; i<=n+m; i++)
if(ans == s[i])
cout << i << "\n";
for(int i=0, j=0; j<3; j++)
{
for(int k=0; k<3; k++)
cout << ans[i++] << " \n"[k==2];
}
}
```
- Python
```python=
import sys
sys.setrecursionlimit(100000)
n, m = map(int, input().split())
con: list[list[int]] = [[] for _ in range(n + m)]
a: list[None | tuple[list[list[int]],int]] = [None] * (n + m)
vis = [False] * (n + m)
for _ in range(n + m - 1):
u, v = map(int, input().split())
con[u - 1].append(v - 1)
con[v - 1].append(u - 1)
for _ in range(m):
k = int(input())
o = [list(map(int, input().split())) for _ in range(3)]
a[k - 1] = (o, k)
def cmp1(x, y):
if [x[0][i][j] for i in range(3) for j in range(3)] > [y[0][i][j] for i in range(3) for j in range(3)]:
return x
else:
return y
def cmp2(x, y):
if [x[0][2 - i][2 - j] for i in range(3) for j in range(3)] > [y[0][2 - i][2 - j] for i in range(3) for j in
range(3)]:
return x
else:
return y
cmp = [cmp2, cmp1]
def dfs(i, t=0):
vis[i] = True
if a[i] is not None:
return
cur = []
for j in con[i]:
if not vis[j]:
dfs(j, t ^ 1)
cur.append(a[j])
while len(cur) > 1:
cur.append(cmp[t](cur.pop(), cur.pop()))
a[i] = cur[0]
dfs(0)
print(a[0][1])
for o in a[0][0]:
print(*o)
```
# 小綠搭公車 (Bus)
> 出題者：Mingyee
> 難度：p4
> 考點：DP
>
### Statement
中秋節要到了，**小綠**決定搭公車去各個朋友家烤肉。
**小綠**十分有錢，包下了整整三台專車，故他可以隨意更改司機的行駛路徑。
**小綠**所居住的城市中，公車站可以表示為一個數線，這些公車站由左而右編號為 $1$ 到 $m$。
已知第 $i$ 公車站的位置位於 $p_i$。
現在小綠包下的三台車的起始位置都在 $1$ 號站，而**小綠**有$n$個朋友要拜訪，
所以聰明的**小綠**將他的行程列為 $s_i, d_i$ $( i \in [1, n])$，表示要拜訪第 $i$ 個朋友時，**小綠**會在 $s_i$ 站上車，$d_i$ 站下車。
**小綠**會依序從第一個朋友拜訪到第 $n$ 個朋友。
為了小綠的交通安全，請你寫個程式規劃路線，使三位專車司機的駕駛總里程數達到最小值。
### Input
第一行輸入兩個正整數 $n$、$m$，其中 $n$ 表示要拜訪的朋友數量，$m$ 表示公車站的數量 $(1\le n \le 1000, 1 \le m \le 10)$
接下來有 $n$ 行，第 $i+1$ 行輸入兩個正整數 $s_i,d_i$ $( i \in [1, n])$，表示**小綠**要拜訪第 $i$ 個朋友時，**小綠**會在 $s_i$ 站上車，$d_i$ 站下車。$(1 \le s_i, d_i \le 10)$
最後一行輸入 $m$ 個正整數，其中第 $i$ 個數字表示第 $i$ 個公車站的位置 $p_i$，$(1\le p_i \le 10^9)$，且保證 $\forall a<b: p_a \lt p_b$
### Output
輸出一個正整數，代表三台專車行駛的總里程數之最小值
### Testcase
- Input 1
```
3 4
1 2
2 4
1 2
1 2 3 4
```
- Output 1
```
4
```
- Input 2
```
3 5
1 5
3 2
1 4
1 2 4 10 11
```
- Output 2
```
24
```
### Subtask
- Subtask 1 (40%)：$n \le 20$
- Subtask 2 (60%)：無其他限制
### Solution
- Subtask 1
- 因為三台車一定至少要動一台，所以可以嘗試各種可能的移動，對於每個要求，都分別嘗試使用第 $1,2,3$ 台車，最後當所有要求結束後，取最小的移動距離就是花費
- Subtask 2
- 發現到其實每台車所在位置的排列組合非常小 ($m \times m \times m$)，所以可以直接用陣列把答案存起來，就變成了 DP
- 定義 $dp_{i,x,y,z}$ 代表在拜訪第 $i$ 個朋友時，第一台車在 $x$、第二台車在 $y$、第三台車在 $z$ 的最小移動
- 會發現到因為三台車至少要動一台，所以假設第 $i$ 個要求的終點是 $to$，則可以枚舉三個公車的位置 $x,y,z$，拿 $dp_{i-1,x,y,z}$ 去更新 $dp_{i,to,y,z}, dp_{i,x,to,z}, dp_{i,x,y,to}$ 的答案
- 因為 $dp_i$ 的答案只跟 $dp_{i-1}$ 有關，所以可以使用兩個 $dp$ 陣列做滾動優化
### Note
如果公車沒有照預期的方式走會發生甚麼事呢？
### Code
- Subtask 1 by binghua
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
int n,m,q[20],ans=1e18;
pii p[1010];
void f(int a,int b,int c,int dis,int x){
if(x==n){
ans=min(ans,dis);
return;
}
f(p[x].s,b,c,dis+abs(q[p[x].f]-q[a])+abs(q[p[x].s]-q[p[x].f]),x+1);
f(a,p[x].s,c,dis+abs(q[p[x].f]-q[b])+abs(q[p[x].s]-q[p[x].f]),x+1);
f(a,b,p[x].s,dis+abs(q[p[x].f]-q[c])+abs(q[p[x].s]-q[p[x].f]),x+1);
}
signed main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>p[i].f>>p[i].s;
}
for(int i=1;i<=m;i++)cin>>q[i];
f(1,1,1,0,0);
cout<<ans;
}
```
- Subtask 2 by Mingyee
```cpp=
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
int dp[10][10][10], last[10][10][10];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
pair<int, int> p[n];
for(int x=0; x<n; x++){
cin >> p[x].first >> p[x].second;
}
vector<int> v(m);
for(auto &a : v) cin >> a;
for(int a=0; a<10; a++){
for(int b=0; b<10; b++){
for(int c=0; c<10; c++){
dp[a][b][c] = LLONG_MAX;
last[a][b][c] = LLONG_MAX;
}
}
}
last[0][0][0] = 0;
int res;
for(int x=0; x<n; x++){
int from = p[x].first-1, to = p[x].second-1, length=abs(v[from] - v[to]);
for(int a=0; a<10; a++){
for(int b=0; b<10; b++){
for(int c=0; c<10; c++){
if(last[a][b][c] == LLONG_MAX) continue;
dp[to][b][c] = min(last[a][b][c] + abs(v[from]-v[a]) + length, dp[to][b][c]);
dp[a][to][c] = min(last[a][b][c] + abs(v[from]-v[b]) + length, dp[a][to][c]);
dp[a][b][to] = min(last[a][b][c] + abs(v[from]-v[c]) + length, dp[a][b][to]);
res = min({dp[to][b][c], dp[a][to][c], dp[a][b][to]});
}
}
}
for(int a=0; a<10; a++){
for(int b=0; b<10; b++){
for(int c=0; c<10; c++){
last[a][b][c] = dp[a][b][c];
dp[a][b][c] = LLONG_MAX;
}
}
}
}
cout << res;
return 0;
}
```
- Python
```python=
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
p = list(map(int, input().split()))
dp = [[[10 ** 10] * m for _ in range(m)] for _ in range(m)]
dp[0][0][0] = 0
for i in range(n):
old = dp
dp = [[[10 ** 10] * m for _ in range(m)] for _ in range(m)]
x, y = a[i]
x -= 1
y -= 1
dis = abs(p[x] - p[y])
for j in range(m):
for k in range(m):
for l in range(m):
dp[y][k][l] = min(dp[y][k][l], old[j][k][l] + abs(p[j] - p[x]) + dis)
dp[j][y][l] = min(dp[j][y][l], old[j][k][l] + abs(p[k] - p[x]) + dis)
dp[j][k][y] = min(dp[j][k][y], old[j][k][l] + abs(p[l] - p[x]) + dis)
print(min(k for i in dp for j in i for k in j))
```
Sign in with Wallet
Connect another wallet