tags: tutorial apcs 解題筆記

2020/10/17 APCS 題解

聲明：筆者沒有參與考試，題解內容僅在 ZeroJudge 上測試過。

1. 人力分配

作法：枚舉

$X_1$，計算相對應的收益，對所有可能答案取最大值。值得注意的是，收益值可能是負的。

我的扣的

#include<iostream>
#include<algorithm>
using namespace std;

int a1, b1, c1, a2, b2, c2, n;

int main(){
    cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> n;
    int ans = -2147483548;
    for(int i = 0; i <= n; ++i)
        ans = max(ans, a1 * i * i + b1 * i + c1 + a2 * (n - i) * (n - i) + b2 * (n - i) + c2);
    cout << ans;
}

2. 人口遷移

作法：暴力的模擬每一天。要好好處理移動的人數，反正寫肥一點也不會被卡。有一個小技巧是，用 1-base 的座標，並把周圍多出來的一圈設為

$-1$，這樣就不用特判邊界了。

我的扣的

#include<iostream>
#include<algorithm>
using namespace std;

int r, c, k, m;
int a[52][52], b[52][52];

int main(){
    cin >> r >> c >> k >> m;
    for(int i = 0; i <= r + 1; ++i)
        for(int j = 0; j <= c + 1; ++j)
            a[i][j] = -1;
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j)
            cin >> a[i][j];
    for(int i = 1; i <= m; ++i){
        for(int i = 1; i <= r; ++i)
            for(int j = 1; j <= c; ++j){
                if(a[i][j] == -1){ b[i][j] = -1; continue;}
                b[i][j] = a[i][j];
                if(a[i+1][j] != -1){
                    b[i][j] -= a[i][j] / k;
                    b[i][j] += a[i+1][j] / k;
                }
                if(a[i-1][j] != -1){
                    b[i][j] -= a[i][j] / k;
                    b[i][j] += a[i-1][j] / k;
                }
                if(a[i][j+1] != -1){
                    b[i][j] -= a[i][j] / k;
                    b[i][j] += a[i][j+1] / k;
                }
                if(a[i][j-1] != -1){
                    b[i][j] -= a[i][j] / k;
                    b[i][j] += a[i][j-1] / k;
                }
            }
        for(int i = 1; i <= r; ++i)
            for(int j = 1; j <= c; ++j)
                a[i][j] = b[i][j];
    }
    int mn = 2147483647, mx = -2147483648;
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j)
            if(a[i][j] != -1) mn = min(mn, a[i][j]),
            mx = max(mx, a[i][j]);
    cout << mn << '\n' << mx;
}

總之，好好處理轉移、最大最小值就好。

3. 勇者修煉

思路：看起來很像經典的 DP 題，但是多了一個方向可以走。既然上下還是單向的話就從上往下 DP 吧。對於一個點要考慮從左邊走來、從右邊走來、從上面走來三種狀況，其中上面走來會是已經做好的。那就從左右各做一次 DP 吧。

作法：令

$dp[0][i][j]$ 為從左邊走進

$(i,j)$ 的最大經驗值，

$dp[1][i][j]$ 為從右邊走進

$(i,j)$ 的最大經驗值，則轉移式：

$dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j])$

$dp[1][i][j]=max(dp[1][i][j+1],dp[0][i-1][j],dp[1][i-1][j])$

然後好好實作即可。

我的扣的

#include<iostream>
#include<algorithm>
using namespace std;

int m, n;
int a[52][10002];
int dp[2][52][10002];

int main(){
    cin >> m >> n;
    for(int i = 1; i <= m + 1; ++i)
        for(int j = 0; j <= n + 1; ++j)
            dp[0][i][j] = dp[1][i][j] = -2147483647;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> a[i][j];
    for(int i = 1; i <= m + 1; ++i){
        for(int j = 1; j <= n; ++j)
            dp[0][i][j] = a[i][j] + max(dp[0][i][j-1], max(dp[0][i-1][j], dp[1][i-1][j]));
        for(int j = n; j >= 1; --j)
            dp[1][i][j] = a[i][j] + max(dp[1][i][j+1], max(dp[0][i-1][j], dp[1][i-1][j]));
    }
    int ans = -2147483647;
    for(int j = 1; j <= n; ++j)
        ans = max(ans, max(dp[0][m+1][j], dp[1][m+1][j]));
    cout << ans;
}

備註：這題的轉移式是去偷看討論區才搞通的。我弱

4. 低地距離

思路：一個一個從左到右把數字加入某個東東，並記錄這個數字有沒有出現過。如果沒有，就紀錄「現在有多少數字比這個數字小」；出現過的話，查詢「現在總共有多少數字比這個數字小」減掉「剛才有多少數字比這個數字小」，就會是「這個數字出現兩次之間」的答案。不難想到可以用值域 BIT 維護。

我的扣的

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 1;
int n, a[N * 2], last[N];

// bit
int val[N];
void modify(int p, int v){
    for(; p <= n; p += p & -p) val[p] += v;
}
int query(int p){
    int ans = 0;
    for(; p > 0; p -= p & -p) ans += val[p];
    return ans;
}

int main(){
    cin >> n;
    for(int i = 0; i < n * 2; ++i)
        cin >> a[i];
    for(int i = 0; i <= n; ++i)
        last[i] = -1;
    for(int i = 0; i < n * 2; ++i){
        if(last[a[i]] == -1) last[a[i]] = query(a[i] - 1);
        else last[a[i]] = query(a[i] - 1) - last[a[i]];
        modify(a[i], 1);
    }
    long long ans = 0;
    for(int i = 1; i <= n; ++i)
        ans += last[i];
    cout << ans;
}

不過官解似乎不是用 BIT 而是線段樹。

有一解是先把線段樹全部設成

$1$ ，然後查詢兩個最大數之間的區間和，把兩個最大數的位置在線段樹中設成

$0$ ，然後再往下做。

以上程式碼皆經編譯執行並通過 ZeroJudge 測試。有任何問題歡迎留言提問。

後記

相隔一年之後去寫 APCS 的題目，和之前的感覺比起來簡單許多。自我感覺良好的覺得自己進步了。

寫了常數超肥的扣的，赫然發現感覺還不錯，只是沒有 #define FOR(i,n) 多重迴圈寫得很煩躁。

還有一些不同做法沒有想到，得更努力才行