# APCS 20191026 題解
###### tags: `APCS`

以下數字範圍只列所有子題中最大的
題目敘述有修改過

## 第一題

### 題目大意

給一個有 $n$ 項的數列 $A$，由第四項起由左而右開始變更數字，變更的方式是，若 $|A_i-A_{i-1}|>5$，就把 $A_i$ 變成 $A_{i-3}$、$A_{i-2}$、$A_{i-1}$ 的中位數，至於在 $A_i$ 之前的項的值都是考慮變更後的數字，而非原始值。

給 $n$ 和 $A$，求變更後的數列。

$1 \leq n \leq 32$
$1 \leq A_i \leq 35$

### 解法

就掃一遍一邊改就好，超級簡單。

時間複雜度 $O(n)$。

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    for(int i = 3; i < n; i++){
        if(abs(a[i] - a[i - 1]) <= 5) continue;
        int t[3] = {a[i - 3], a[i - 2], a[i - 1]};
        sort(t, t + 3);
        a[i] = t[1];
    }

    for(int i = 0; i < n; i++){
        if(i != 0) cout << " ";
        cout << a[i];
    }
    cout << "\n";

    return 0;
}

## 第二題

### 題目大意

給一個有 $n$ 個數的數列 $P$，有三種操作：

1. 洗牌：把 $P$ 變成 $\{P_1,P_{n/2+1},P_{2},P_{n/2+2},...,P_{n/2},P_{n}\}$，也就是把 $P$ 平分成前後兩部分，再交錯取兩部分的第一項，放到新的數列尾端。
2. 反洗牌：把 $P$ 變成 $\{P_1,P_3,P_5,...,P_{n-1},P_{2},P_{4},...,P_n\}$，也就是把偶數項移到尾端。
3. $k$-切牌：把 $P$ 變成 $\{P_{k+1},{P_{k+2},...,P_n,P_1,P_2,...,P_k}\}$，也就是把前 $k$ 項移到尾端。（$3 \leq k < n$）。

給一個大小為 $m$ 的序列 $A$，$A_i$ 表示第 $A_i$ 個操作為何，$1$ 表示洗牌，$2$ 表示反洗牌，其餘表示 $A_i$-切牌。再給一個數列 $X$，表示 $P$ 進行完 $A$ 中的操作後的結果。求初始的 $P$。

$4 \leq n \leq 200$，$n$ 是偶數
$1 \leq m \leq 20$

### 解法

就是把每種操作反推回來：

1. 洗牌反過來：把 $X$ 變成 $\{X_1,X_3,X_5,...,X_{n-1},X_2,X_4,...,X_n\}$，等同於把 $X$ 反洗牌。
2. 反洗牌反過來：把 $X$ 變成 $\{X_1,X_{n/2+1},X_{2},X_{n/2+2},...,X_{n/2},X_{n}\}$，也就是把 $X$ 洗牌。
3. $k$-切牌反過來：把 $X$ 變成 $\{P_{n-k+1},P_{n-k+2},...,P_{n},P_1,P_2,...,P_{n-k}\}$，也就是對 $X$ 做 $(n-k)$-切牌。

這樣一來，只要從最後一個操作開始反推就能得到最初的數列。

時間複雜度 $O(nm)$。

（注意程式碼中我用的陣列 index 是從 0 開始）

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n, m;
    cin >> n >> m;

    vector<int> x(n);
    for(int i = 0; i < n; i++) cin >> x[i];
    vector<int> a(m);
    for(int i = 0; i < m; i++) cin >> a[i];

    for(int i = m - 1; i >= 0; i--){

        vector<int> t(n);
        if(a[i] == 1){
            int now = 0;
            for(int j = 0; j < n; j += 2) t[now++] = x[j];
            for(int j = 1; j < n; j += 2) t[now++] = x[j];
        }
        else if(a[i] == 2){
            int now = 0;
            for(int j = 0; j < n / 2; j++){
                t[now++] = x[j];
                t[now++] = x[n / 2 + j];
            }
        }
        else{
            int now = 0;
            for(int j = n - a[i]; j < n; j++) t[now++] = x[j];
            for(int j = 0; j < n - a[i]; j++) t[now++] = x[j];
        }
        x = t;

    }

    for(int i = 0; i < n; i++){
        if(i != 0) cout << " ";
        cout << x[i];
    }
    cout << "\n";

    return 0;
}

## 第三題

### 題目大意

有一個有 $n$ 格的一維表格，每一格從左到右編號為 $0$ 到 $n-1$，有一隻皮卡丘起始位置為 $0$，每次可做下列兩種操作：

1. 往左走 $L$ 格
2. 往右走 $R$ 格

不能走出表格外面。在完成一次操作後，若移動到的格子為 $i$，皮卡丘會瞬間移動到 $S(i)$，$S(i)$ 是 $i$ 的「瞬間移動位置」，$S(i)$ 有可能等於 $i$，此時 $i$ 稱為停留點，每一個格子的瞬間移動位置必定是停留點，因此不會連續瞬間移動，也就是說，對於任何 $0 \leq S(i) < n$，$S(S(i))=S(i)$。（$S(i)$ 有可能超出界外，表示皮卡丘也不能走到 $i$，不然它會瞬移出界）

給 $n$、目標位置 $P$ 和 $L$、$R$，還有 $S(0)$、$S(1)$、……、$S(n-1)$，求需要幾次操作，皮卡丘才會移動到 $P$。

$2 \leq n \leq 10^6$
$|S(i)| \leq 10^8$
起點和目標位置必為停留點

### 解法

把這個表格想成一張有向不帶權圖，每個節點表示一個格子，編號同格子編號。由節點 $i$ 畫有向邊往 $S(i-L)$ 和 $S(i+R)$，如果出界就不要那條邊了。這樣就可以算 $0$ 到 $P$ 的最短路徑，不過這張圖不帶權，所以直接 BFS 就好。

時間複雜度 $O(n)$。

#include <bits/stdc++.h>

#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second

using namespace std;

int main(){

    int n, p, l, r;
    cin >> n >> p >> l >> r;

    vector<int> s(n);
    for(int i = 0; i < n; i++) cin >> s[i];

    vector<bool> visit(n);
    queue<pii> q;
    q.push(mp(0, 0));
    visit[0] = true;
    while(!q.empty()){
        int v = q.front().F, step = q.front().S;
        q.pop();
        if(v == p){
            cout << step << "\n";
            return 0;
        }

        if(v - l >= 0 && s[v - l] >= 0 && s[v - l] < n && !visit[s[v - l]]){
            q.push(mp(s[v - l], step + 1));
            visit[s[v - l]] = true;
        }
        if(v + r >= 0 && s[v + r] >= 0 && s[v + r] < n && !visit[s[v + r]]){
            q.push(mp(s[v + r], step + 1));
            visit[s[v + r]] = true;
        }
    }
    cout << "-1\n";

    return 0;
}

## 第四題

### 題目大意

給一個 $m$ 列 $n$ 行（直行橫列）的矩陣，這個矩陣裡的數字只有 $0$ 或 $1$，最上和最下的列與最左和最右的行稱為邊界線，如果一條邊界線上的所有數字都一樣，那這條邊界線可以被刪除，而這個矩陣的行數或列數就會減 1。你可以改變一些數字，使得這個矩陣可以被完全刪除。

給 $m$、$n$ 和原始矩陣，求最少需要改變幾個數字。

$m, n \leq 25$

### 解法

這是 DP，先設第 $r$ 列和第 $c$ 行的交點為 $(r,c)$，令 $dp[x_1][y_1][x_2][y_2]$ 為以 $(x_1, y_1)$ 和 $(x_2, y_2)$ 為左上角和右下角的子矩陣，需要改幾個數字才能被刪除、令 $row(r, y_1, y_2)$ 為 $(r, y_1)$ 到 $(r, y_2)$ 需要改幾個數字才能使所有數字一樣、$column(c, x_1, x_2)$ 為 $(x_1, c)$ 到 $(x_2, c)$ 需要改幾個數字才能使所有數字一樣。

初始狀態：
$dp[i][j][i][j]=0$，也就是大小只有 $1 \times 1$ 的矩陣不需要改任何數字就可以被刪除。

轉移：
$dp[x_1][y_1][x_2][y_2]=\\
\min(dp[x_1+1][y_1][x_2][y_2]+row(x_1, y_1, y_2),\\
dp[x_1][y_1+1][x_2][y_2]+column(y_1, x_1, x_2), \\
dp[x_1][y_1][x_2-1][y_2]+row(x_2, y_1, y_2), \\
dp[x_1][y_1][x_2][y_2-1]+column(y_2, x_1, x_2))$

時間複雜度 $O(n^2m^2)$。

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> rs, cs;

int row(int r, int y1, int y2){
    return min(rs[r][y2] - rs[r][y1 - 1], y2 - y1 + 1 - (rs[r][y2] - rs[r][y1 - 1]));
}

int column(int c, int x1, int x2){
    return min(cs[c][x2] - cs[c][x1 - 1], x2 - x1 + 1 - (cs[c][x2] - cs[c][x1 - 1]));
}

int main(){

    int m, n;
    cin >> m >> n;

    vector<vector<int>> a(m + 1, vector<int>(n + 1));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }

    rs.resize(m + 1, vector<int>(n + 1));
    cs.resize(n + 1, vector<int>(m + 1));

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            rs[i][j] = a[i][j] + rs[i][j - 1];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cs[i][j] = a[j][i] + cs[i][j - 1];
        }
    }

    vector<vector<vector<vector<int>>>> dp(m + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(m + 1, vector<int>(n + 1))));

    for(int rl = 1; rl < m; rl++){ //含有 rl+1 列
        for(int cl = 1; cl < n; cl++){ //含有 cl+1 行
            for(int i = 1; i + rl <= m; i++){
                for(int j = 1; j + cl <= n; j++){

                    dp[i][j][i + rl][j + cl] = min({
                        dp[i + 1][j][i + rl][j + cl] + row(i, j, j + cl),
                        dp[i][j + 1][i + rl][j + cl] + column(j, i, i + rl),
                        dp[i][j][i + rl - 1][j + cl] + row(i + rl, j, j + cl),
                        dp[i][j][i + rl][j + cl - 1] + column(j + cl, i, i + rl)
                    });
                }
            }
        }
    }

    cout << dp[1][1][m][n] << "\n";

    return 0;
}