# APCS 20221023 題解
## [巴士站牌](https://zerojudge.tw/ShowProblem?problemid=i428)
### 想法
對於每個點找他其中一邊的鄰居看看距離，再比大小求最大最小值。
### 時間複雜度
$O(N)$
### Code

#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

#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

#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

#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;
}