# APCS 第十三場模擬賽
## 2025/1/25 題解簡報
---
# p1
### 出題者：LittleOrange
### 首殺：babbrian (0:03:53)
----
# 簡易題敘
----
在一個一維坐標系有 $n$ 個點，給你鄰近兩點各自的距離，接著要在上面移動 $q$ 次，每次給你是從現在位置移動到哪個編號的點，問你移動的總長度?
----
直接實作即可
----
# AC code
```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";
}
```
---
# p2
### 出題者：kzzz.\_.17
### 首殺：zhu0901 (0:33:19)
----
# 簡易題敘
----
一個 $n \times m$ 格子上有 $k$ 個點，接著會有 $q$ 個操作，每個操作會將這些點的位置分別上下左右移動(但出界則忽略)，請你求每個時間點對於下面問題的答案:
* 請找一個整數點 $P$ 能最小化這 $k$ 個點跟它的曼哈頓距離的和? 找到此值即可。
----
# Subtasks
----
- Subtask #1 (20%) K=1
- Subtask #2 (20%) T=0
- Subtask #3 (60%) 無其他限制
----
# Subtask 1 : K=0
----
## 完全送分欸
可以發現P點一直跟唯一的點重疊
答案會是0
code:
```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 2 : T=1
----
題目範圍的N和M都不大
枚舉網格上所有位置的同時計算與所有點的距離
計算出的結果取最小就是答案
```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解
剩下就是點的移動了
實作上我習慣先把移動後的點先存起來
確認在網格範圍內再賦值給移動的點
移動後和子題二一樣枚舉所有位置
建議把不同功能的程式包成函式
比較好實作和除錯
----
# AC code
- AC (5ms/3MB)
```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();
}
}
```
----
# 更優解?
----
觀察到 $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)$，但常數大就算了。
完整code在文字版題解
---
# p3
### 出題者：rickytsung
### 首殺：oscar_chien (0:12:57)
----
# 簡易題敘
----
有個特別的分數，它的規則是分子要填 $n$ 個數字，分母要填 $m$ 個數字，然後整數 $1 \sim n+m$ 在裡面各出現一次。
給定 $n,m$ 以及 $t$ 個最簡分數，對於給的每一個問你:
分別有幾個這樣特別的分數的值會跟給定的一樣。
* $n+m \leq 9$
* $t \le 10^5$
----
- Subtask 1 (20%) - $n, m \leq 3$
- Subtask 2 (30%) - $t = 1$
- Subtask 3 (50%) - 無其他限制
----
# 暴力 ?
----
直接暴力? 假設今天 $n = m = 3$，那我們可以直接把分子分母都從 $100$ 跑到 $999$，先檢查符不符合整數 $1 \sim n+m$ 在裡面各出現一次，然後接著利用輾轉相除法，就可以得到它的最簡型態，然而注意像這樣一次的運算量就是 $O(10^{n+m})$，問題在於有 $t$ 次確認，當 $t = 10^5$ 的時候每次都跑 $O(10^{n+m})$，估計出來會變 $10^{11}$ 次運算會跑不完，所以我們想個紀錄方式。
----
# 儲存 ?
----
如果我們先跑過所有合法的分數一次，接著把每個結果有幾個存起來，之後再去裡面拿呢?
例如 : 開一個二維陣列 $A$， $A[i][j]$ 存最簡分數是 $i/j$ 的答案，那我們前面跑到合法的分數的時候就化簡完後得到的 $i/j$ 將 $A[i][j]$ 加 $1$。
這樣就通過了 Subtask 1。
然而將目光移動到下一個子任務，很快我們發現了問題。
----
# 暴力 II ?
----
$n+m$ 最多可以到 $9$，也就是根據前面的 $O(10^{n+m})$ 的計算量會達到 $10^9$ ，然而其實很多分數都不合法，我們能不能用另一種方式暴力呢?
答案是可以的，把上面跟下面的格子想成是一種數字排列
變成枚舉 $1 \sim n+m$ 的[排列](https://zerojudge.tw/ShowProblem?problemid=e446)
前面 $n$ 項是為分子、後面看成分母
這樣實際只會有 $O(n!)$ 個排列($9!=362880$)
使用 C++ 內建的 `next_permutation` 就可以輕鬆做到!
----
# 儲存 II ?
----
因為 subtask 2 的 $t = 1$ 所以不用儲存，但 subtask 3 又遇到和 subtask 1 不能做 $t$ 次的問題了!
如果如法炮製，記憶體會 $\approx 3.7 \text{GB}$ (如果開的是 int 陣列)，太大了!
這時可以利用 `map` (Python 的 `dict`) 離散化!
----
# 複雜度分析
這題的想法不難，主要難點是複雜度分析
令 $D =n+m$，空間複雜度就降到 $O(D!)$、存入 map 時間複雜度是 $O(D!lg(D!))$。注意這裡可能會有不同分數化簡是同個值，所以這個 $D!$ 是上界。
從 map 拿出的總時間複雜度是 $O(tlg(D!))$，考慮到 $D! lg D$ 很小，所以時間複雜度是 $O(D! \cdot D + tlg(D!))$
----
# 小提醒
* 雖然這題有保證輸入的分數型態不會是整數 (少給你輸入判一個 case hehe)，但有些寫法還是要記得判斷一下分子除以分母是 1 的狀況。
* 小心不要爆型態喔
* subtask 1 和 2 的關係在這題沒有重疊，由於 judge 沒有自動聯集(實際的測驗也沒有)，所以如果剛好只會前兩個子任務的話，自己要在 code 裡面判斷!
----
# Code
``` 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]; // numerator
}
for(int i = n; i < n+m; i++){
y *= 10;
y += v[i]; // denominator
}
int gen = gcd(x, y);
int x2 = x/gen; // simpify
int y2 = y/gen;
auto it = mp.find({x2, y2}); // check if it's a new element
if(it == mp.end()){
mp[{x2, y2}] = ++cnt; // add a new element
}
ans[mp[{x2, y2}]]++; // add the mapped count
}while(next_permutation(v.begin(), v.end())); // brute force all permutation
while(t--){
string s;
int p = 0, q = 0, i = 0;
cin >> s;
// read input
for(i = 0; s[i] != '/'; i++){
p *= 10;
p += s[i] - '0';
}
for(i++; s[i]; i++){
q *= 10;
q += s[i] - '0';
}
auto it = mp.find({p, q});
if(it == mp.end()){ // if not in map -> answer is 0
cout << 0 << '\n';
continue;
}
cout << ans[it->second] << '\n';
}
}
```
---
# p4
### 出題者：rickytsung
### 首殺：rayho0319 (1:43:08)
----
為啥又是你?
因為正燒雞底題目出爛了
----
# 簡易題敘
----
有個圖，這個圖有個大小 $n$ 雙向圓環，接著有 $k$ 單向邊可以讓你走到圓環外的點 (有 $m$ 個這樣的點) ，但不會有邊是讓你走到圓環裡的。所有邊的權重為 $1$，給定一個圓環上的點，問你從圓環上指定的一個點走到圓環外的點的最短距離分別是多少。
* $3 \le n \le 10^9$
* $1 \le m \le 2 \times 10^5$
* $m \le k \le 3.5 \times 10^5$
----
- 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%) - 無其他限制
----
# Subtask 1
----
首先是因為圓環可能很大，不能直接暴力在圖上一個個走路，發現圓環距離我們要的點的答案是 $1$，
圖長這樣，大家都叫我閉(眼)卡(在廁)所:
那我們可以發現圓環上相異兩點的距離，有順逆時針兩種走法，其中一種走法的長度會是兩者編號的絕對值、那另一個走法很顯然是 $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)$，足夠快通過。
----
# Code
```cpp=
// Author : rickytsung
// Problem : APCS13-p4-full
// 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; // add critcal point
O.push_back(vector<int>());
int di = abs(u - p);
// distance
dist.push_back(make_pair(min(n - di, di), cnt));
cnt++;
}
O[mp[u]].push_back(v - n); // center to outside
}
else{
G[u - n].push_back(v - n); // outside to outside
}
}
sort(dist.begin(), dist.end());
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()])){
// find which side is better?
// visited outside point vs critical point
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;
}
```
----
# Another Solution
----
這題也可以使用 Dijkstra 解 (超綱)
因為本題邊權 >= 0，首先先預處理把 $p$ 到圓環上重要的點變成一個權重為圓上距離的邊，接著維護一個 priorityqueue (min heap)，依次將最近的點拿出來，接著進行擴展 (將鄰近的點放進去裡面)。
---
# 優異參賽者表揚
----
### 首殺
#### p1 : babbrian (0:03:53)
#### p2 : zhu0901 (0:33:19)
#### p3 : oscar_chien (0:12:57)
#### p4 : rayho0319 (1:43:08)
----
# 首位破台
## rayho0319 (1:43:08)
---
# Fun facts
----
首submit但RE
再不本地測試阿
----
小知識
二維char陣列不能直接cin(出題者現在才知道)
這筆CE惹
----
關於工作人員不小心搶到首殺
橘子 (32:19)
zhu0901 (33:19)
---
# 謝謝您今天的參與
## APCS 模擬測驗出題團隊感謝您
{"title":"APCS 第十三場模擬賽簡報","description":"模擬題，小心指出去就好","contributors":"[{\"id\":\"34d91565-9500-4e65-834e-faf84ff85f3e\",\"add\":24000,\"del\":13089}]"}