# APCS 20221023 題解
## [巴士站牌](https://zerojudge.tw/ShowProblem?problemid=i428)
### 想法
對於每個點找他其中一邊的鄰居看看距離,再比大小求最大最小值。
### 時間複雜度
$O(N)$
### Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
array<int, 104> X, Y;
signed main(){
int n, ner = 1 << 30, far = 0;
cin >> n >> X[1] >> Y[1];
for(int i = 2; i <= n; i++){
cin >> X[i] >> Y[i];
ner = min(ner, abs(X[i] - X[i - 1]) + abs(Y[i] - Y[i - 1]));
far = max(far, abs(X[i] - X[i - 1]) + abs(Y[i] - Y[i - 1]));
}
cout << far << " " << ner << "\n";
return 0;
}
```
## [運貨站](https://zerojudge.tw/ShowProblem?problemid=j123)
### 想法
對於每個包裹先把他放在倉庫的最右邊,接著一步一步往內推直到碰上牆壁或是其他包裹。最後檢查包裹的右界是否露在倉庫外就完事了。
### 時間複雜度
$O((N + R)C)$
### Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int r, c;
array<int, 5> Ly = {3, 0, 1, 1, 2}, Lx = {0, 2, 1, 2, 1};
array<array<int, 34>, 54> D;
int push(int x, int y, int t){
for(; x; x--){
if(t == 0 && (D[x][y] || D[x][y - 1] || D[x][y - 2] || D[x][y - 3])) break;
else if(t == 1 && D[x][y]) break;
else if(t == 2 && (D[x][y] || D[x][y - 1])) break;
else if(t == 3 && (D[x][y] || D[x + 2][y - 1])) break;
else if(t == 4 && (D[x][y] || D[x][y - 1] || D[x + 1][y - 2])) break;
}
x++;
if(x + Lx[t] > c) return 1;
if(t == 0) D[x][y] = D[x][y - 1] = D[x][y - 2] = D[x][y - 3] = 1;
else if(t == 1) D[x][y] = D[x + 1][y] = D[x + 2][y] = 1;
else if(t == 2) D[x][y] = D[x][y - 1] = D[x + 1][y] = D[x + 1][y - 1] = 1;
else if(t == 3) D[x][y] = D[x + 1][y] = D[x + 2][y] = D[x + 2][y - 1] = 1;
else D[x][y] = D[x][y - 1] = D[x + 1][y] = D[x + 1][y - 1] = D[x + 1][y - 2] = 1;
return 0;
}
signed main(){
int n, y, up = 0, sum = 0;
char t;
cin >> r >> c >> n;
for(int i = 1; i <= n; i++){
cin >> t >> y, y += 1 + Ly[t - 'A'];
up += push(c, y, t - 'A');
}
for(int i = 1; i <= c; i++){
for(int j = 1; j <= r; j++){
sum += !D[i][j];
}
}
cout << sum << " " << up << "\n";
return 0;
}
```
## [石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124)
### 想法
把題目給的序列直接拿去建樹,然後 DFS 求差值總和。
### 時間複雜度
$O(N)$
### Code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int p = 0, sum = 0;
vector<int> V;
int DFS(){
int u = V[p++], v;
if(!u) return 0;
for(int i = 0; i < 2 + (u & 1); i++){
v = DFS();
if(v) sum += abs(u - v);
}
return u;
}
signed main(){
int v;
while(cin >> v) V.pb(v);
DFS();
cout << sum << "\n";
return 0;
}
```
## [蓋步道](https://zerojudge.tw/ShowProblem?problemid=j125)
### 想法
對步道中出現的最大差值二分搜。二分搜中每次對於所有鄰點高度相差不超過當前二分搜的值建邊,檢查左上到右下是否連通,是的話則右界減小,反之左界增加。最後再跑一次最短路求路徑長就好了。
### 時間複雜度
$O(N^2logC)$
### Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct ufo{
int x, y, d;
};
array<int, 4> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
array<array<int, 304>, 304> H, dis;
int RUN(int n, int p){
queue<ufo> Q;
for(array<int, 304> &D : dis) for(int &d : D) d = 0;
Q.push({1, 1, 1});
while(!Q.empty()){
auto [x, y, d] = Q.front(); Q.pop();
if(dis[x][y] || !x || !y || x > n || y > n) continue;
dis[x][y] = d;
for(int i = 0; i < 4; i++){
if(abs(H[x][y] - H[x + dx[i]][y + dy[i]]) <= p) Q.push({x + dx[i], y + dy[i], d + 1});
}
}
return dis[n][n];
}
int RFS(int n){
int p = 0;
for(int i = 1 << 20; i; i >>= 1){
if(!RUN(n, p + i)) p += i;
}
RUN(n, p + 1);
return p + 1;
}
signed main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> H[i][j];
}
}
cout << RFS(n) << "\n" << dis[n][n] - 1 << "\n";
return 0;
}
```