## 成為行人 (Walking)
> 出題者：橘子
> 難度：p1
> 考點：迴圈、陣列、if else
### Statement
小橘喵寫不出TLE的實作題，感覺要不行了，好傷心
這時，他碰到了Chung教授
小橘喵：可能是累了吧，也可能是逐漸發現自己完全寫不出「暴力又被TLE」的實作題，想退坑了，已經沒有閒情逸致實作了。仔細想了想，大概是需要一些短暫的休息，到了暫時退坑的時候。題目都寫不出來的我，已經不行在這出題團隊待下去了。謝謝大家陪我那麼久，跟你們在一起的日子很開心。
Chung教授：為什麼？不是約好了要大家一起組一輩子的APCS模擬測驗團隊嗎？
Chung教授：不行了？沒關係，來一起成為行人吧！
Chung教授：來參加APCSS健走大會吧
APCSS健走大會在一條又長又直的道路上，有$n$個標記點，依序編號 $1\sim n$
小橘喵從第$t_0$個標記點出發，依序有$q$個任務，要到第$t_i$個標記點，請告訴小橘喵完成所有任務要走多遠吧！這樣他就會知道他有多行了！
### Input
第一行有三個整數$n,q,t_0$
表示 數量、行動次數和起始位置
第二行有$n-1$個整數$a_i$，表示第$i$個標記點與第$i+1$個標記點的距離
第三行有$q$個整數$t_i$，表示$q$個關卡的目標點編號
- $2\le n \le 100$
- $1\le q \le 100$
- $1\le a_i\le 1000$
- $1\le t_i,x\le n$
- $t_i \ne t_{i-1}\ \ \forall i\in[1,q]$
### Output
輸出小橘喵健走的總距離
### Sample
- Input 1
```
7 5 6
9 2 1 1 2 6
1 6 2 7 6
```
- Output 1
```
54
```
說明：
- Input 2
```
3 10 2
1 10
3 1 2 1 2 1 2 3 1 3
```
- Output 2
```
58
```
說明：
### Subtask
- Subtask 1 (50%) - $|t_i-t_{i+1}|=1$
- Subtask 2 (50%) - 無其他限制
### Solution
- C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,q,x;
cin >> n >> q >> x;
int a[105];
for(int i = 1;i<n;i++) cin >> a[i];
int ans = 0;
while(q--){
int y;
cin >> y;
if(y>x){
for(int i = x;i<y;i++) ans += a[i];
}else{
for(int i = y;i<x;i++) ans += a[i];
}
x = y;
}
cout << ans << "\n";
}
```
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,q,x;
cin >> n >> q >> x;
int a[105];
for(int i = 1;i<n;i++) cin >> a[i];
int ans = 0;
while(q--){
int y;
cin >> y;
ans += accumulate(a+min(x,y),a+max(x,y),0);
x = y;
}
cout << ans << "\n";
}
```
- Python
```python=
n,q,x = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 0
for y in b:
ans += sum(a[min(x,y)-1:max(x,y)-1])
x = y
print(ans)
```
加上前綴和優化：
```python=
def main():
from sys import stdin
from itertools import accumulate
e = stdin.readline
n, q, a = map(int, e().split())
# 建前綴和 -> O(1) 取區間和
# 補 None -> 1-based, 補 0 -> 區間和 edge case
get = (None, 0, *accumulate(map(int, e().split()))).__getitem__
ans = 0
u = get(a)
for v in map(get, map(int, e().split())):
# 避免討論方向 加上絕對值
ans += abs(v - u)
u = v
print(ans)
main()
```
## 模擬退火 (Simulated Annealing)
> 出題者：唐狗針
> 難度：p2
> 考點：枚舉、模擬、實作
### Statement
山羊最近學習了模擬退火這個演算法，想找點題目練習，於是他找到了***費馬點***。
費馬點定義如下：
>三角形 $\Delta ABC$ 中的一點 $P$，滿足距離三頂點的距離和最小，也就是 $\overline{PA}+\overline{PB}+\overline{PC}$ 最小。
不過強大的模擬退火提出抗議，表示它的能力遠不止於此，於是他設計了一個大小為 $N\times M$ 的網格，最左上角為 $(1,1)$，第 $i$ 行第 $j$ 列為$(i,j)$，他在這個網格上放上了 $K$ 個點 $(X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)$，希望求出以下問題：
>任意選擇一個點 $P$，使得 $\text{dis}(P, (X_1, Y_1)) + \text{dis}(P, (X_2, Y_2)) + \dots + \text{dis}(P, (X_K, Y_K))$ 最小。
模擬退火對他出的題目很滿意，但APCS模擬團隊則相反，於是他們在沒經過模擬退火的同意擅自增加以下規則 :
1. 定義 $dis((x,y),(a,b))$ 為曼哈頓距離，也就是 $|x-a|+|y-b|$
2. 只需求出最小距離和，不需要構造滿足條件的 $P$ 點座標。
3. $P$ 點位於任意 $(x,y)$ 其中 $x,y \in \mathbb{N}$ 且 $1\le x\le N,1\le y \le M$（$P$ 為網格範圍內的整數點）
突然，某人跳了出來，說出一句：
> 這樣太簡單了吧，好無聊的題目
APCS 模擬團隊仔細思考和深深**檢討**後，經歷數次**高峰會**後決定，加入以下規則增加挑戰性：
- 每個點有一個長度為 $T$ 的字串 $op_i$，由``L``,``R``,``U``,``D`` 組成，表示點的移動方向。
- 在第 $j$ 秒 ($1 \leq j \leq T$) 時，每個點根據 $op_i[j-1]$ 移動：
- 若 $op_i[j-1]$ 為 L，點向左移動一格，即從 $(x_i, y_i)$ 移到 $(x_i, y_i - 1)$。
- 若 $op_i[j-1]$ 為 R，點向右移動一格，即從 $(x_i, y_i)$ 移到 $(x_i, y_i + 1)$。
- 若 $op_i[j-1]$ 為 U，點向上移動一格，即從 $(x_i, y_i)$ 移到 $(x_i - 1, y_i)$。
- 若 $op_i[j-1]$ 為 D，點向下移動一格，即從 $(x_i, y_i)$ 移到 $(x_i + 1, y_i)$。
- 若移動超出網格範圍，該點保持不動。
對於第 $i$ 秒 $(0\le i \le T)$，輸出該時間任意選擇一個點 $P$，最小的 $dis(P,(X_1,Y_1))+dis(P,(X_2,Y_2))+\dots+dis(P,(X_K,Y_K))$。
小提醒
>第 $0$ 秒是指所有點處於初始位置時。
若點的移動超出網格範圍 ($x > N$、$x < 1$、$y > M$、$y < 1$)，則不進行移動。
兩個點可以重疊。
$P$ 可以與某點重疊。
### Input
第一行輸入四個整數 $N, M, K, T$：
- $N, M$ 表示網格的大小。
- $K$ 表示點的數量。
- $T$ 表示每個點的操作序列長度。
接下來有 $K$ 組點的資訊，每組點的資訊包含兩行：
1. 第一行包含兩個整數 $X_i, Y_i$，表示第 $i$ 個點的初始位置。
2. 第二行是一個字串 $op_i$，表示第 $i$ 個點的操作序列。
限制條件 :
- $1\le N,M,K \le 30,0\le T \le 30$
- $1\le X_i \le N,1 \le Y_i \le M$
- $|op_i| = T$
- $op_i$中只包含 ``L``, ``R``, ``U``, ``D`` 四種字元
### Output
輸出 $T+1$ 行。第 $i$ 行 ($1 \leq i \leq T+1$) 表示在第 $i-1$ 秒時，任意一點 $P$ 與所有點的最小距離總和。
### Input Format
$N\quad M\quad K\quad T$
$X_1\quad Y_1$
$op_1$
$X_2\quad Y_2$
$op_2$
$\vdots$
$op_K$
$X_K\quad Y_K$
### Output Format
$ans_1$
$ans_2$
$\vdots$
$ans_{T+1}$
#### Sample Input 1
```
5 5 2 3
1 1
RDD
5 5
LLU
```
#### Sample Output 1
```
8
6
4
2
```
第 $0$ 秒時，點 $1$ 位於 $(1,1)$，點 $2$ 位於 $(5,5)$，取 $P(3,3)$ 時距離合為 $(|1-3|+|1-3|)+(|5-3|+|5-3|) = 8$，找不到更小的距離和。
第 $1$ 秒時，點 $1$ 位於 $(1,2)$，點 $2$ 位於 $(5,4)$。
第 $2$ 秒時，點 $1$ 位於 $(2,2)$，點 $2$ 位於 $(5,3)$。
第 $3$ 秒時，點 $1$ 位於 $(3,2)$，點 $2$ 位於 $(4,3)$。
#### Sample Input 2
```
3 7 6 5
2 2
ULUUD
3 2
DUUDL
2 7
ULDLL
1 6
DDDRL
1 2
LRLRR
1 2
URRLU
```
#### Sample Output 2
```
13
13
13
15
14
11
```
#### Sample Input 3
```
4 3 6 0
1 2
4 1
1 3
2 2
4 1
2 3
```
#### Sample Output 3
```
12
```
注意 $T=0$ 時 $op_i$ 字串為空
### Subtask
| 分數 | 條件限制 | 附加條件 |
|:-:|:-:|:-:|
| 20% | $K=1$ | |
| 20% | $T=0$ | |
| 60% | 無其他限制 | |
### Solution
子任務 1：觀察到 $P$ 跟著唯一的點，答案恆為 $0$
子任務 2：不須處理點的移動
子任務 3：每次移動後枚舉所有點，時間複雜度 $O(NMKT)$
Extra：觀察到 $P$ 為中位點時有最小距離，不過點會移動導致中位數改變，需要動態維護，可以每次移動完都重新排序，時間複雜度 $O(T \times K \log k )$。或者如果你觀察力特別好，可以再觀察到點每次移動的距離只有 $1$，因此中位點的 x, y 也各自最多移動 $1$，時間複雜度 $O(K \log K + K \times T)$，前面的 $K \log K$ 是排序以後找中位點，當然也可以用 Median of medians 達到 $O(K)$，但常數大就算了。
以下 C++ 解是使用二分搜維護，時間複雜度 $O(K \log K + T \times KlogK)$；python 解則是用後者解法，時間複雜度 $O(K \log K + T \times K)$。
### Code
- Subtask 1
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,k,t;
int x[31],y[31];
string op[31];
signed main(){
cin>>n>>m>>k>>t;
for(int i=1;i<=n;i++) {
cin>>x[i]>>y[i];
if(t) cin>>op[i];
}
for(int i=0;i<=t;i++) cout<<0<<'\n';
}
```
- Subtask 1
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,k,t;
int x[31],y[31];
int dis(int x1,int y1,int x2,int y2){
return abs(x1-x2)+abs(y1-y2);
}
void solve(){
int ans=0x3f3f3f,tmp;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
tmp=0;
for(int l=1;l<=k;l++){
tmp+=dis(i,j,x[l],y[l]);
}
ans=min(ans,tmp);
}
}
cout<<ans<<'\n';
}
signed main(){
cin>>n>>m>>k>>t;
for(int i=1;i<=n;i++) {
cin>>x[i]>>y[i];
}
solve();
}
```
- AC
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,k,t;
int x[31],y[31];
string op[31];
//是否在網格內
bool inRange(int x1,int y1){
return x1>=1&&x1<=n&&y1>=1&&y1<=m;
}
//計算曼哈頓距離
int dis(int x1,int y1,int x2,int y2){
return abs(x1-x2)+abs(y1-y2);
}
void solve(){
//0x3f3f3f3f是個不錯的最大值，約是1e9不會超過int範圍
int ans=0x3f3f3f3f,tmp;
//枚舉每個網格點取距離總和最小
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
tmp=0;
//枚舉每個點計算距離和
for(int l=1;l<=k;l++){
tmp+=dis(i,j,x[l],y[l]);
}
//取總和最小
ans=min(ans,tmp);
}
}
cout<<ans<<'\n';
}
signed main(){
cin>>n>>m>>k>>t;
for(int i=1;i<=k;i++) {
cin>>x[i]>>y[i];
//若t為0字串為空 不須輸入
if(t) cin>>op[i];
}
//輸出初始位置的答案
solve();
for(int i=0;i<t;i++){
//每個點移動
for(int j=1;j<=k;j++){
int nx,ny;
if(op[j][i]=='L') nx=x[j],ny=y[j]-1;
else if(op[j][i]=='R') nx=x[j],ny=y[j]+1;
else if(op[j][i]=='U') nx=x[j]-1,ny=y[j];
else nx=x[j]+1,ny=y[j];
//移動後仍在範圍內才移動
if(inRange(nx,ny)) x[j]=nx,y[j]=ny;
}
//移動完輸出答案
solve();
}
}
```
- $O(K \log K + T \times KlogK)$
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,k,t;
int x[31],rlx[31];
int y[31],rly[31];
int mxx=0,mxy=0,mnx=0,mny=0;
string op[31];
bool inRange(int x1,int y1){
return x1>=1&&x1<=n&&y1>=1&&y1<=m;
}
signed main(){
cin>>n>>m>>k>>t;
for(int i=1;i<=k;i++) {
cin>>x[i]>>y[i],rlx[i]=x[i],rly[i]=y[i];
if(t) cin>>op[i];
}
sort(x+1,x+1+k);
sort(y+1,y+1+k);
for(int i=1;i<=k;i++){
if((k&1)&&i==k/2+1) continue;
if(i<=k/2) mnx+=x[i],mny+=y[i];
else mxx+=x[i],mxy+=y[i];
}
cout<<(mxx-mnx)+(mxy-mny)<<'\n';
for(int i=0;i<t;i++){
for(int j=1;j<=k;j++){
int nx,ny;
if(op[j][i]=='L') nx=rlx[j],ny=rly[j]-1;
else if(op[j][i]=='R') nx=rlx[j],ny=rly[j]+1;
else if(op[j][i]=='U') nx=rlx[j]-1,ny=rly[j];
else nx=rlx[j]+1,ny=rly[j];
if(!inRange(nx,ny)) continue;
if(op[j][i]=='L') {
int pos=lower_bound(y+1,y+k+1,rly[j])-y;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mny-=y[pos];
else mxy-=y[pos];
}
rly[j]--;
y[pos]--;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mny+=y[pos];
else mxy+=y[pos];
}
}
else if(op[j][i]=='R') {
int pos=upper_bound(y+1,y+k+1,rly[j])-y-1;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mny-=y[pos];
else mxy-=y[pos];
}
rly[j]++;
y[pos]++;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mny+=y[pos];
else mxy+=y[pos];
}
}
else if(op[j][i]=='U') {
int pos=lower_bound(x+1,x+k+1,rlx[j])-x;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mnx-=x[pos];
else mxx-=x[pos];
}
rlx[j]--;
x[pos]--;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mnx+=x[pos];
else mxx+=x[pos];
}
}
else {
int pos=upper_bound(x+1,x+k+1,rlx[j])-x-1;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mnx-=x[pos];
else mxx-=x[pos];
}
rlx[j]++;
x[pos]++;
if(!((k&1)&&pos==k/2+1)) {
if(pos<=k/2) mnx+=x[pos];
else mxx+=x[pos];
}
}
}
cout<<(mxx-mnx)+(mxy-mny)<<'\n';
}
}
```
- Python $O(MNKT)$
```python=
def main():
from sys import stdin
e = stdin.readline
# 點移動方向
d = {"L": (0, -1), "R": (0, 1), "U": (-1, 0), "D": (1, 0)}.__getitem__
m, n, k, t = map(int, e().split())
# 每個點的資料 list[tuple[int, int, callable[[], tuple[int, int]]]]
l = [(*map(int, e().split()), map(d, e()).__next__) for _ in range(k)]
# 窮舉所有點 算距離總和
dis = min(sum(abs(x - xm) + abs(y - ym) for x, y, _ in l)
for xm in range(1, m + 1) for ym in range(1, n + 1))
ans = [dis] # 儲存每一輪答案
for _ in range(t): # O(t * mn * k)
for i, (x, y, next_op) in enumerate(l): # O(k)
dx, dy = next_op() # 取下一步怎麼走
x += dx
y += dy
# 判斷邊界
if x < 1: x = 1
elif x > m: x = m
if y < 1: y = 1
elif y > n: y = n
# 將新座標存回去
l[i] = (x, y, next_op)
# 窮舉所有點 算距離總和 O(mn * k)
dis = min(sum(abs(x - xm) + abs(y - ym) for x, y, _ in l)
for xm in range(1, m + 1) for ym in range(1, n + 1))
ans.append(dis) # 加入答案
print("\n".join(map(str, ans)))
main()
```
- Python $O(K \log K + K \times T)$
```python=
def main():
from sys import stdin
from operator import itemgetter
e = stdin.readline
# 點移動方向
d = {"L": (0, -1), "R": (0, 1), "U": (-1, 0), "D": (1, 0)}.__getitem__
m, n, k, t = map(int, e().split())
# 每個點的資料 list[tuple[int, int, callable[[], tuple[int, int]]]]
l = [(*map(int, e().split()), map(d, e()).__next__) for _ in range(k)]
# 取第一次前綴和 O(klogk)
xm = sorted(map(itemgetter(0), l))[k >> 1]
ym = sorted(map(itemgetter(1), l))[k >> 1]
# 算總和 O(k)
dis = sum(abs(x - xm) + abs(y - ym) for x, y, _ in l)
ans = [dis] # 每一輪的答案
for _ in range(t): # O(t * k)
# 紀錄與 xm - 1, xm, xm + 1 的距離總和
disx_de = disx_eq = disx_in = 0
# 紀錄與 ym - 1, ym, ym + 1 的距離總和
disy_de = disy_eq = disy_in = 0
for i, (x, y, next_op) in enumerate(l): # O(k)
dx, dy = next_op() # 取下一步怎麼走
x += dx
y += dy
# 判斷邊界
if x < 1: x = 1
elif x > m: x = m
if y < 1: y = 1
elif y > n: y = n
# 將新座標存回去
l[i] = (x, y, next_op)
# 算距離
x -= xm
y -= ym
disx_de += abs(x + 1)
disx_eq += abs(x)
disx_in += abs(x - 1)
disy_de += abs(y + 1)
disy_eq += abs(y)
disy_in += abs(y - 1)
# 取距離最小的作為新的中位點
xs, xm = min((disx_de, xm - 1),
(disx_eq, xm ),
(disx_in, xm + 1))
ys, ym = min((disy_de, ym - 1),
(disy_eq, ym ),
(disy_in, ym + 1))
ans.append(xs + ys) # 加入答案
print("\n".join(map(str, ans)))
main()
```
## 分數密碼 (Fraction)
> 出題者：rickytsung
> 難度：p3
> 考點：離散化、離線、複雜度分析
> 預計時間限制 : 3s for c/cpp/java 20s for python
### Statement
背景: 西元 $9487$ 年，暴力又被TLE 被抓去外星人 ㅎㄹㅎ” 的基地了! 他醒來發現自己在一個奇怪的地方。
暴力又被TLE : 我怎麼會在這裡? 你們是誰?
ㅎㄹㅎ” : 母公花勾氣披喔思密達～
暴力又被TLE : 你們抓我要幹嘛 ??
ㅎㄹㅎ” : 我們打算進攻逮丸 Chung 油的基地，但是需要你幫我們忙，成功了我們就考慮放你走。
暴力又被TLE : 喔喔那我要做甚麼?
ㅎㄹㅎ” : 逮丸 Chung 油的基地入口有個門禁系統，他是一個像密碼鎖的東西，螢幕上有兩行格子需要填入，上面有 $n$ 個格子需要被填入、下面有 $m$ 個格子需要被填入，然後恰好填入正整數 $1 \sim n+m$ 各一次，如下面這張圖就是 $n=2, m=3$ 的情況，你要把右邊的數字一對一的放到左邊格子裡面。
暴力又被TLE : 聽起來不難? 那密碼有線索嗎?
ㅎㄹㅎ” : 他們的密碼很特別，是已知 $t$ 個最簡分數 (形式為 $p/q$) ，我們要分別求有幾種填入方法能在當我們將密碼鎖視為一個分數時，上除以下的結果會是對應的最簡分數，如今天我們知道一個最簡分數是 $2/59$，上圖那個密碼鎖如果上面填入 $12$ 下面為 $354$，就是對於 $2/59$ 的一種填入方法，因為 $\frac{12}{354} = \frac{2}{59}$。
暴力又被TLE : 豪難喔... 你有想法嗎?
ㅎㄹㅎ” : 我們有一個時間複雜度為 $O(-114514)$ 的方法可以求出一個最簡分數對應的答案。
暴力又被TLE : 那你們就用這方法就好了啊? 好啦，我要回家了啦，之前的出題費匯給你啦，乞丐。
ㅎㄹㅎ” : 但是使用一次這方法時間就會倒退 $114514$ 單位，當 $t$ 很大的時候，時間會回到宇宙誕生之前，這樣我們就不存在了。
為了保護世界和平(?，並且讓 暴力又被TLE 離開 ㅎㄹㅎ” 的基地，請你幫幫他! (或是你也可以選擇不幫他把他蛋雕，這樣 APCSS 就不會有滅台題了)
### Input
輸入第一行有三個數字分別代表 $n, m, t$，$t$ 代表接下來有幾個最簡分數。
接著有 $t$ 行，每行有一個形式為 "$p/q$" 的最簡分數 (不含引號，$p/q$ 有可能是假分數，但為了方便輸入格式統一，本題保證 $p/q$ 的值不會是整數，也就是保證 $p$ 除以 $q$ 餘數不為 $0$)。
$1 \leq n,m$
$n+m \leq 9$
$1 \leq t \leq 10^5$
對於每一組 $p, q$ :
$1 \leq p \leq 10^8$
$2 \leq q \leq 10^8$
$p/q$ 是最簡分數
### Output
輸出 $t$ 行，代表對於對應分數有幾種填法，在轉換成分數後會跟對應的值相等。
### Sample
- Input 1
```
2 3 3
2/59
9/22
19/2
```
- Output 1
```
1
1
0
```
說明：
將 $1 \sim 5$ 填入一個上方二位數、下方三位數的分數中。
其中:
$2/59$ 有 $1$ 種填法 : $\frac{12}{354}$ 。
$9/22$ 有 $1$ 種填法 : $\frac{54}{132}$ 。
$19/2$ 有 $0$ 種填法。
- Input 2
```
4 5 5
2/5
1/62
1/8
114514/9999991
2/59
```
- Output 2
```
3
2
46
0
0
```
說明：
將 $1 \sim 9$ 填入一個上方四位數、下方五位數的分數中。
其中:
$2/5$ 有 $3$ 種填法 : $\frac{6894}{17235}$、$\frac{8694}{21735}$、$\frac{9486}{23715}$ 。
$1/62$ 有 $2$ 種填法 : $\frac{1283}{79546}$、$\frac{1528}{94736}$。
$1/8$ 有 $46$ 種填法。
$114514/9999991$ 和 $2/59$ 有 $0$ 種填法。
### Subtask
- Subtask 1 (20%) - $n, m \leq 3$
- Subtask 2 (30%) - $t = 1$
- Subtask 3 (50%) - 無其他限制
### Solution
#### Subtask 1
直接對分子分母從 $1\sim 999$ 暴力枚舉接著判斷有沒有符合條件就可以了，將化簡過後的結果存在一個 $10^n \times 10^m$ 的陣列就可以 $O(1)$ 查一組 $p,q$ 的答案了，空間複雜度為 $O(10^{n+m})$。時間會多一個 $\text{log}$ 因為要做約分(可以使用輾轉相除法)
#### Subtask 2
發現 $10^{n+m}$ 很大，但是其實填入方法只有 $(n+m)!$ 個 ，! 表示階乘，$n!=n \times (n-1) \times (n-2) \times ... \times 2 \times 1$
以本題的限制最大是 $9! = 362880$，其實沒有很大，不過我們要怎麼快速的窮舉呢?
C++ 的 STL 有個 ```next_permutation()```，給予一個排序好的 vector 他可以生成下一個排列，也就是我們可以將 $1 \sim n+m$ 放入一個 vector 中，然後利用它來窮舉
因為 $t=1$，我們約分好就直接檢查是否等於 $p,q$ 即可。
令 $D =n+m$，則時間複雜度為 $O(D! \cdot D)$
#### Subtask 3
發現照 subtask 2 的方法做 $t$ 次會感人的 $\text{TLE}$。
但是照 subtask 1 直接開陣列紀錄結果又會因為陣列太大而開不了 (這題範圍會高達 $10^9 \approx 3.7 \text{GB}$ )
這裡可以使用 map 的資料結構，用離散化的方法存，令 $D =n+m$，空間複雜度就降到 $O(D!)$、存入 map 時間複雜度是 $O(D! \log(D!))$。注意這裡可能會有不同分數化簡是同個值，所以這個 $D!$ 是上界。
從 map 拿出的總時間複雜度是 $O(t \log(D!))$，考慮到 $D! \cdot log D$ 很小所以時間複雜度是 $O(D! \cdot D + t \log(D!))$
#### Code
- C++ sub 2 without io
```cpp=
// Author : rickytsung
// Problem : APCS13_P3_subtask_1-2
// Date : 2025/1/2
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if (a%b == 0) return b;
else return(gcd(b, a%b));
}
int main() {
int n, m, p, q, t, ans = 0;
cin >> n >> m >> t; // t=1;
cin >> p >> q;
vector<int> v;
for(int i = 1; i <= n+m; i++) v.push_back(i);
do{
int x = 0, y = 0;
for(int i = 0; i < n; i++){
x *= 10;
x += v[i];
}
for(int i = n; i < n+m; i++){
y *= 10;
y += v[i];
}
int gen = gcd(x, y);
int x2 = x/gen;
int y2 = y/gen;
if(x2 == p && y2 == q){
ans++;
}
}while(next_permutation(v.begin(), v.end()));
cout << ans << '\n';
}
```
- C++ full
``` cpp=
// Author : rickytsung
// Problem : APCS13_P3_subtask_all
// Date : 2025/1/2
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if (a%b == 0) return b;
else return(gcd(b, a%b));
}
int main() {
int n, m, t, cnt = 0;
cin >> n >> m >> t;
vector<int> v;
map<pair<int,int>, int> mp;
static int ans[362885] = {0};
for(int i = 1; i <= n+m; i++) v.push_back(i);
do{
int x = 0, y = 0;
for(int i = 0; i < n; i++){
x *= 10;
x += v[i];
}
for(int i = n; i < n+m; i++){
y *= 10;
y += v[i];
}
int gen = gcd(x, y);
int x2 = x/gen;
int y2 = y/gen;
auto it = mp.find({x2, y2});
if(it == mp.end()){
mp[{x2, y2}] = ++cnt;
}
ans[mp[{x2, y2}]]++;
}while(next_permutation(v.begin(), v.end()));
while(t--){
string s;
int p = 0, q = 0, i = 0;
cin >> s;
for(i = 0; s[i] != '/'; i++){
p *= 10;
p += s[i] - '0';
}
for(i++; s[i]; i++){
q *= 10;
q += s[i] - '0';
}
//testcase dbg
assert(q != 0 && p % q != 0 && gcd(p,q) == 1);
auto it = mp.find({p, q});
if(it == mp.end()){
cout << 0 << '\n';
continue;
}
cout << ans[it->second] << '\n';
}
}
```
- Python
只需要狂砸各種模組就好了 hehe。
```python=
def main():
from sys import stdin
from collections import defaultdict
from itertools import permutations
from math import gcd
n, m, t = map(int, stdin.readline().split())
cnt = defaultdict(int) # 用來計數
for p in permutations("123456789"[:n + m]):
a, b = int("".join(p[:n])), int("".join(p[n:]))
c = gcd(a, b) # 用來約分
cnt[f"{a // c}/{b // c}\n"] += 1
# 使用 .get 而不是 .__getitem__ 來取值
# 避免 __missing__ 而插入新鍵浪費時間
print("\n".join(str(cnt.get(i, 0)) for i in stdin))
main()
```
- Python 一行解 by 橘子 OrzOrz
用 Counter 更適合一行解的計數，而 `fractions.Fraction` 則是 Python 中專門用來處理分數的模組，會幫你自動約分，但這兩者都偏肥偏慢。
```python!
print(*(lambda n,m,t:(lambda mp:(mp[input()]for _ in range(t)))(__import__("collections").Counter(str(__import__("fractions").Fraction(int("".join(s[:n])),int("".join(s[n:]))))for s in __import__("itertools").permutations("123456789"[:n+m]))))(*map(int,input().split())),sep="\n")
```
### gen
#1-4
```cpp=
// subtask 1 gen
// gen > {1-4}
#include "bits/stdc++.h"
#include "testlib.h"
using namespace std;
int gcd(int a, int b){
if (a%b == 0) return b;
else return(gcd(b, a%b));
}
int main(int argc, char* argv[]){
registerGen(argc, argv, 1);
int n = 1, m = 1;
int t = 1;
for(int test = 1; test <= 4; test++){
startTest(test);
vector<pair<int,int>> input;
input.push_back({9999991,9999999});
input.push_back({9999999,9999991});
if(test == 1){
n = 2;
m = 3;
t = 99999;
input.push_back({13,452});
}
if(test == 2){
n = 2;
m = 2;
t = 99998;
input.push_back({13,42});
}
if(test == 3){
n = 3;
m = 2;
t = 99997;
input.push_back({452,13});
}
if(test == 4){
n = 3;
m = 3;
t = 99996;
input.push_back({613,245});
}
while(input.size() < t){
int p = rnd.next(1, 339) ;
int q = rnd.next(2, 339) ;
int gc = gcd(p, q);
p /= gc;
q /= gc;
if(q == 1) continue;
input.push_back({p,q});
}
cout << n << ' ' << m << ' ' << t << '\n';
for(auto &i : input){
cout << i.first << '/' << i.second << '\n';
}
}
}
```
#5-10 are handmade
#5
```
5 4 1
19/2
```
#6
```
1 8 1
1/1371742
```
#7
```
6 3 1
41911/7
```
#8
```
4 5 1
1/17
```
#9
```
4 4 1
5/4
```
#10
```
4 5 1
2/19
```
#11-20
p.s. actually they're almost the same after #14
```cpp=
// subtask 3 gen
// gen > {11-20}
#include "bits/stdc++.h"
#include "testlib.h"
using namespace std;
int gcd(int a, int b){
if (a%b == 0) return b;
else return(gcd(b, a%b));
}
int main(int argc, char* argv[]){
registerGen(argc, argv, 1);
int n = 1, m = 1;
int t = 1;
for(int test = 11; test <= 20; test++){
startTest(test);
vector<pair<int,int>> input;
input.push_back({9999991,9999999});
input.push_back({9999999,9999991});
if(test == 11){
n = 1;
m = 8;
t = 99999;
input.push_back({12345679,8});
}
if(test == 12){
n = 8;
m = 1;
t = 99998;
input.push_back({8,12345679});
}
if(test == 13){
n = 5;
m = 4;
t = 99997;
input.push_back({7/2});
input.push_back({9/2});
input.push_back({11/2});
input.push_back({1/123});
}
if(test >= 14){
n = 4;
m = 5;
t = 100000 - rnd.next(1, 10);
input.push_back({1/8});
input.push_back({1/17});
input.push_back({1/26});
input.push_back({1/35});
}
while(input.size() < t){
int p = rnd.next(1, 339) ;
int q = rnd.next(2, 339) ;
int gc = gcd(p, q);
p /= gc;
q /= gc;
if(q == 1) continue;
input.push_back({p,q});
}
cout << n << ' ' << m << ' ' << t << '\n';
for(auto &i : input){
cout << i.first << '/' << i.second << '\n';
}
}
}
```
## 輸送帶 (Conveyor Belt)
> 出題者：rickytsung
> 難度：p4
> 考點：圖論 (bfs)、貪心、排序
> 預計時間限制 : 3s
### Statement
有個貨運公司叫做正燒，為了自動化流程，它有一個輸送帶系統。
首先正燒貨運的輸送帶系統中間有一個圓環狀的構造，由 $n$ 個貨物集中點 (以下簡稱集中點) 編號 $1 \sim n$ 組成，我們稱它為「中央圓環」，對於一個正整數 $i(1 \le i \le n-1)$，集中點 $i$ 和 $i+1$ 這兩個點中間都有一個雙向的輸送帶可以傳輸貨物，集中點 $1$ 和集中點 $n$ 也有一個雙向的輸送帶，形成一個環狀的構造。
除此之外，還有不在「中央圓環」上的集中點，他們編號為 $n+1 \sim n+m$，貨物會從中央圓環的一個集中點進入，接著透過中央圓環移動，並藉由一些額外的「次要輸送帶」來達到這些不在圓環上的點，這些輸送帶為"單向"的。
然而值得注意的是，這些「次要輸送帶」保證不會有可以將貨物傳送到「中央圓環」上任一點的輸送帶，也就是今天如果有一個「次要輸送帶」可以將貨物從集中點 $u$ 單向的傳送到集中點 $v$，則保證 $v$ "一定不是" 「中央圓環」的一部分。
正燒貨運整個的輸送帶系統系統構造如下圖，圓形點代表「中央圓環」，方形點代表其他集中點。
因為正燒貨運的科技非常進步，貨物每通過一個輸送帶消耗的時間都是 $1$ 單位。今天給你正整數 $n$、$m$ 以及 $k$ 個「次要輸送帶」，且保證所有的集中點一定有至少一種方式可以透過這些傳送帶到達，想請問您如果今天貨物一開始在 「中央圓環」上的 $p$ 號集中點，那分別至少需要多久的時間才可以傳送到對應的集中點上。另外因為 「中央圓環」可能很大，您只需要求出非 「中央圓環」上的集中點的答案即可，也就是你只要求出從集中點 $p$ 到集中點 $n+1 \sim n+m$ 分別所需的最短時間。
### Input
輸入的第一行有四個正整數分別代表 $n,m,k,p$，也就是屬於/不屬於中央圓環上的集中點數量、次要輸送帶的數量、貨物的起始位置。
接著有 $k$ 行，第 $i$ 行有兩個正整數 $u_i, v_i$，代表有一個「次要輸送帶」可以將貨物從集中點 $u_i$ 單向的傳送到集中點 $v_i$。
* $3 \le n \le 10^9$
* $1 \le m \le 2 \times 10^5$
* $m \le k \le 3.5 \times 10^5$
* $1 \le p \le n$
* $1 \le u_i \le n+m(1 \le i \le k)$
* $n+1 \le v_i \le n+m(1 \le i \le k)$
* $u_i \neq v_i(1 \le i \le k)$
* 保證所有的集中點一定有至少一種方式可以透過這些傳送帶到達
### Output
輸出 $m$ 行，第 $i$ 行輸出一個整數代表從集中點 $p$ 到集中點 $n+i$ 所需的最短時間。
### Sample
- Input 1
```
4 4 5 3
1 7
2 5
4 8
5 6
6 7
```
- Output 1
```
2
3
3
2
```
說明：
範例#1說明 : 以下為畫出來的圖:
起始集中點為 $3$。
以下分別為一組將貨物運送到 $5,6,7,8$ 的最短路徑:
$5:\ 3 \rightarrow 2 \rightarrow 5$，所花時間為 $2$。
$6:\ 3 \rightarrow 2 \rightarrow 5 \rightarrow 6$，所花時間為 $3$。
$7:\ 3 \rightarrow 4 \rightarrow 1 \rightarrow 7$，所花時間為 $3$。
$8:\ 3 \rightarrow 4 \rightarrow 8$，所花時間為 $2$。
- Input 2
```
6 5 9 6
2 9
3 9
4 7
4 8
7 8
7 10
9 11
10 9
11 10
```
- Output 2
```
3
3
3
4
4
```
說明：
範例#2說明 : 畫出來的圖如題目敘述範例圖。
- Input 3
```
123456789 1 2 3
123456789 123456790
123456789 123456790
```
- Output 3
```
4
```
說明：
範例#3說明 : 請注意 $n$ 有可能很大，以及可能有兩條一模一樣的輸送帶。
將貨物運送到 $123456790$ 的最短路徑為:
$3 \rightarrow 2 \rightarrow 1 \rightarrow 123456789 \rightarrow 123456790$，所花時間為 $4$。
### Subtask
- Subtask 1 (20%) - $m \le 100, k \le 200$ 且全部的「次要傳送帶」的起點都是「中央圓環」的一部分 ($\forall\ i$滿足 $1 \le u_i \le n$)
- Subtask 2 (30%) - $m \le 100,k \le 200$
- Subtask 3 (50%) - 無其他限制
### Solution
#### Subtask 1
這題值得注意的是這個熟悉的、大的感人的 $n$，顯然整個圖建出來會爆開。
首先分析一下這個子任務，主要後面有個特別的條件 : 全部的「次要傳送帶」的起點都是「中央圓環」的一部分，那這個圖會長的像這樣:
也就是從圓環走一格就可以到我們想知道的點，如果知道走到圓環上某點的最短路徑，那那一點的答案就是它加1。
那要怎麼算圓環上的 $p$ 走到環上面某一點 $q$ 的距離呢?
在圓環上從 $p$ 走到 $q$ 有兩種路徑 : 順時針和逆時針，其中有個路徑不通過輸送帶 $(1,n)$，那這距離顯然就是 $p-q$ 的絕對值，那另一個方向就會是 n 扣除這個值 (考慮到兩邊加上去理應是個圓環)。
所以我們就枚舉這些能連通到我們想要的點就可以了。
#### Subtask 2
承 subtask1，我們可以對每個有跟次要傳送帶的點當起點，對這個圖做 bfs，很明顯最多做 $k$ 次，一次時間複雜度顯然是 $O(m+k)$，所以整體是 $O(mk+k^2)$ (不過實際上不會跑滿)
#### Subtask 3
承 subtask2，我們發現 $O(mk+k^2)$ 不夠快，原因是因為要跑 $k$ 次，但是如果我們把圓上的距離排序，變成說一個 bfs 進行到一半發現現在最近的和外面距離一樣的時候也讓它跟著一起跑，整體時間複雜度下降到 $O(m+klgk)$，足夠快通過。
#### Another Solution
這題也可以使用 Dijkstra 解 (超綱)
因為本題邊權 >= 0，首先先預處理把 $p$ 到圓環上重要的點變成一個權重為圓上距離的邊，接著維護一個 priorityqueue (min heap)，依次將最近的點拿出來，接著進行擴展 (將鄰近的點放進去裡面)。
#### Code
- C++ full
``` cpp=
// Author : rickytsung
// Problem : APCS13-p4-full-fixed
// Date : 2025/1/3
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main() {
IOS;
int n, m, k, p, u, v, cnt = 0;
cin >> n >> m >> k >> p;
map<int,int> mp;
map<int,int>::iterator it;
vector<vector<int>> O;
vector<pair<int,int>> dist;
vector<int> G[m+1];
int ans[m+1];
bool vis[m+1] = {0};
for(int i = 0; i <= m; i++){
ans[i] = 2e9; // init
}
for(int i = 0; i < k; i++){
cin >> u >> v;
if(u <= n){
assert(v > n);
it = mp.find(u);
if(it == mp.end()){ // new key
mp[u] = cnt;
O.push_back(vector<int>());
int di = abs(u - p);
dist.push_back(make_pair(min(n - di, di), cnt));
cnt++;
}
O[mp[u]].push_back(v - n);
}
else{
G[u - n].push_back(v - n);
}
}
sort(dist.begin(), dist.end());
// for(auto & i: dist){
// cout << i.first << ' ' << i.second << '\n';
// }
const int entryN = dist.size();
int ptr = 0, cur, key;
queue<int> q;
while(ptr != entryN || !q.empty()){
if(q.empty() || (ptr != entryN && dist[ptr].first <= ans[q.front()])){
key = dist[ptr].second;
cur = dist[ptr].first;
for(auto& i: O[key]){
q.push(i);
ans[i] = min(ans[i], cur + 1);
}
ptr++;
}
else{
key= q.front();
q.pop();
if(vis[key]) continue;
vis[key] = 1;
cur = ans[key];
for(auto& i: G[key]){
q.push(i);
ans[i] = min(ans[i], cur + 1);
}
}
}
for(int i = 1; i <= m; i++){
cout << ans[i] << '\n';
}
return 0;
}
```
- Python AC
```python=
def main():
from sys import stdin
from collections import deque
inf = float("INF")
e = stdin.readline
n, m, k, p = map(int, e().split())
a = [(inf, None)] # 中央圓環 -> 次要輸送帶 初始化為 sentinel
b = [[] for _ in range(m)] # 次要輸送帶之間互傳
ans = [inf] * m # 到各次要輸送帶距離
for _ in range(k):
u, v = map(int, e().split())
v -= n + 1 # 轉換為僅次要輸送帶的編號 (扣掉中央圓環)
if u <= n: # 中央圓環 -> 次要輸送帶
# 計算環狀最短距離
dis = abs(u - p)
dis = min(dis, n - dis) + 1
ans[v] = dis # 更新答案
a.append((dis, v))
else: # 次要輸送帶 -> 次要輸送帶
b[u - n - 1].append(v)
a.sort() # 將 中央圓環 -> 次要輸送帶 照距離升冪排序 方便等等遍歷
nxt = iter(a).__next__
# 用來取最短路的 queue
q = deque((nxt(), )) # 初始化取最短的一條 中央圓環 -> 次要輸送帶
da, ua = nxt() # 取下一個 中央圓環 -> 次要輸送帶 準備插隊
while True:
if not q or da <= q[0][1]: # 嘗試插隊
if ua is None: break # 代表 q, a 都沒了 結束迴圈
dis, u = da, ua # a 插隊
da, ua = nxt() # 取下一個
else:
dis, u = q.popleft() # 取 q
if dis > ans[u]: continue # 如果是過舊數據就跳過 不可能更新答案
dis += 1 # 走往下一個 距離 + 1
for v in b[u]:
if dis < ans[v]: # 更短路徑
ans[v] = dis # 更新距離
q.append((dis, v)) # 加入 queue 尾端
print("\n".join(map(str, ans))) # 印出所有距離
main()
```
### gen
subtask 1: 1-4
```cpp=
// subtask 1 gen
// gen > {1-4}
#include "bits/stdc++.h"
#include "testlib.h"
using namespace std;
int gcd(int a, int b){
if (a%b == 0) return b;
else return(gcd(b, a%b));
}
int main(int argc, char* argv[]){
registerGen(argc, argv, 1);
for(int test = 1; test <= 4; test++){
startTest(test);
vector<pair<int,int>> input;
int n = 1e9 - rnd.next(0, 10);
int m = 100;
int k = 200;
int p = 6e8 + rnd.next(0, 10);
int now = 1e9 - 50;
for(int i = 1; i <= 100; i++){
int a = rnd.next(1, n);
input.push_back({a,n+i});
}
while(input.size() < k){
int a = rnd.next(1, n);
int b = n+rnd.next(1, m);
input.push_back({a,b});
}
cout << n << ' ' << m << ' ' << k << ' ' << p << '\n';
for(auto &i : input){
cout << i.first << ' ' << i.second << '\n';
}
}
}
```
subtask 2: 5-10
```cpp=
// subtask 2 gen
// gen > {5-10}
#include "bits/stdc++.h"
#include "testlib.h"
using namespace std;
int gcd(int a, int b){
if (a%b == 0) return b;
else return(gcd(b, a%b));
}
int main(int argc, char* argv[]){
registerGen(argc, argv, 1);
for(int test = 5; test <= 10; test++){
startTest(test);
vector<pair<int,int>> input;
int n = 1e9 - rnd.next(0, 10);
int m = 100;
int k = 200;
int p = 6e8 + rnd.next(0, 10);
int now = 1e9 - 50;
for(int i = 1; i <= 100; i++, now+=2){
if(now > n) now -= n;
input.push_back({now, n+i});
if(i < 100) input.push_back({n+i, n+i+1});
}
while(input.size() < k){
int a = p + rnd.next(1, 5);
int b = n+1+rnd.next(80, m);
input.push_back({a,b});
}
cout << n << ' ' << m << ' ' << k << ' ' << p << '\n';
for(auto &i : input){
cout << i.first << ' ' << i.second << '\n';
}
}
}
```
subtask 3: 11-20
```cpp=
// subtask 3 gen
// gen > {11-20}
#include "bits/stdc++.h"
#include "testlib.h"
using namespace std;
int gcd(int a, int b){
if (a%b == 0) return b;
else return(gcd(b, a%b));
}
int main(int argc, char* argv[]){
registerGen(argc, argv, 1);
for(int test = 11; test <= 20; test++){
startTest(test);
vector<pair<int,int>> input;
int n = 1e9 - rnd.next(0, 10);
int m = 200000;
int k = 350000;
int p = 6e8 + rnd.next(0, 10);
int now = 1e9 - 100000;
for(int i = 1; i <= 100000; i++, now+=2){
if(now > n) now -= n;
input.push_back({now, n+i});
input.push_back({n+i, n+i+1}); // chain (for spfa)
}
for(int i = 100001; i < m; i++){
input.push_back({n+i, n+i+1});
}
input.push_back({n+m, n+100001}); // ring
for(int i = 0; i < 40000; i++){
input.push_back({rnd.next(1,n), n+100000+rnd.next(1, 100000)});
}
while(input.size() < k){
int a = n+100000+rnd.next(1, 100000);
for(int i = 0; i < 987; i++){
int b = n+100000+rnd.next(1, 100000);
if(input.size() == k || a == b) continue;
input.push_back({a,b});
}
}
cout << n << ' ' << m << ' ' << k << ' ' << p << '\n';
for(auto &i : input){
cout << i.first << ' ' << i.second << '\n';
}
}
}
```
Sign in with Wallet
Connect another wallet