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\le n\le 32$

$1\le A_i\le 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\le k<n$）。

給一個大小為

$m$ 的序列

$A$，

$A_i$ 表示第

$A_i$ 個操作為何，

$1$ 表示洗牌，

$2$ 表示反洗牌，其餘表示

$A_i$-切牌。再給一個數列

$X$，表示

$P$ 進行完

$A$ 中的操作後的結果。求初始的

$P$。

$4\le n\le 200$，

$n$ 是偶數

$1\le m\le 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\le S(i)<n$，

$S(S(i))=S(i)$。（

$S(i)$ 有可能超出界外，表示皮卡丘也不能走到

$i$，不然它會瞬移出界）

給

$n$、目標位置

$P$ 和

$L$、

$R$，還有

$S(0)$、

$S(1)$、……、

$S(n-1)$，求需要幾次操作，皮卡丘才會移動到

$P$。

$2\le n\le {10}^6$

$|S(i)|\le {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\le 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$ 的矩陣不需要改任何數字就可以被刪除。

轉移：

$$\begin{gathered} 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)) \end{gathered}$$

時間複雜度

$O(n^2{m}^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;
}