APCS 202206 題解

P1 數字遊戲

題敘

給三個正整數，求眾數以及去重之後從大排到小的順序

解題思路

1. 用任意方法將其排序之後，找到出現最多次的將其輸出
2. 若排序後
   $a_i\ne a_i-1$ 則將
   $a_i$ 輸出

參考程式

不使用 for 迴圈的方式：

int x[3];

void sol() {
    cin >> x[0] >> x[1] >> x[2];
    if (x[1] < x[2])
        swap(x[1], x[2]);
    if (x[0] < x[1])
        swap(x[0], x[1]);
    if (x[1] < x[2])
        swap(x[1], x[2]);

    if (x[0] == x[2])
        cout << 3 << " ";
    else if (x[0] == x[1])
        cout << 2 << " ";
    else if (x[1] == x[2])
        cout << 2 << " ";
    else
        cout << 1 << " ";
    
    cout << x[0] << " ";
    if (x[1] != x[0])
        cout << x[1] << " ";
    if (x[2] != x[1])
        cout << x[2] << " ";
    cout << endl;
}

---

P2 字串解碼

題敘

給一個加密過程以及加密過的字串，求加密前的字串
加密過程：

解題思路

使用一個 deque 紀錄目前的字串，以支援題目所需的操作

參考程式

#define MAXN 105
#define MAXM 1000005 
int n, m;
bool odd[MAXN];
string x, s[MAXN];

void sol() {
    cin >> n >> m;
    for (int i = n - 1; i >= 0; i--) {
        cin >> s[i];
        int cnt = 0;
        for (char c: s[i])
            cnt += (c - '0');
        odd[i] = cnt % 2;
    }
    cin >> x;
    deque<char> dq;
    for (char c: x)
        dq.push_back(c);

    for (int i = 0; i < n; i++) {
        deque<char> tmp;
        for (int j = m - 1; j >= 0; j--) {
            if (s[i][j] - '0') {
                tmp.push_back(dq.back());
                dq.pop_back();
            }
            else {
                tmp.push_front(dq.back());
                dq.pop_back();
            }
        }
        if (odd[i])
            for (int j = 0; j < m / 2; j++)
                swap(tmp[j], tmp[j + (m + 1) / 2]);
        dq = tmp;
    }
    for (int i = 0; i < m; i++)
        cout << dq[i];
    cout << endl;
}

---

P3 雷射測試

題敘

有多個以 / 或是 \ 呈現

${45}^{\circ }$ 擺放於格子點（整數座標）的鏡子，不記寬度，求一道由

$(0,0)$ 向右射出的雷射光會經過幾次反彈，保證不會循環

解題思路

本題的重點在要如何以非線性的時間求出每個鏡子上下左右的鏡子是哪個

可以觀察到：

1. 求上下的鏡子就是
   $x$ 軸不變
   $y$ 軸變
2. 求左右則是
   $y$ 軸不變
   $x$ 軸變

觀察到以上兩種性質的話我們就可以想到兩種方法：

1. 以類似圖論的方法，利用多個 vector 紀錄每個
   $x/y$ 座標座標有哪些對應的
   $y/x$ 座標，利用二分搜去找到對應的座標
2. 將原始的輸入直接以
   $x/y$ 排列，即可利用二分搜找到上下左右的點

時間複雜度：

$\mathcal{O}(n\log n)$

以下提供第二種作法

參考程式

#define MAXN 250005
#define MAXM 30005
int n, m;

const int trans[2][4] = {
    {1, 0, 3, 2},
    {3, 2, 1, 0}
};

struct Mirror {
    int F, S, t;

    bool operator <(Mirror _a) {
        if (F != _a.F)
            return F < _a.F;
        else
            return S < _a.S;
    }
} x[MAXN], y[MAXN];

Mirror now = {0, 0, 0};
int ans = 0, dir = 0;

void update(Mirror a) {
    now = a;
    dir = trans[a.t][dir];
    return;	
}

void sol() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i].F >> x[i].S >> x[i].t;
        y[i] = {x[i].S, x[i].F, x[i].t};
    }
    sort(x, x + n);
    sort(y, y + n);



    while (1) {
        if (dir == 0) {
            Mirror tmp = {now.S, now.F + 1, 0};
            auto qq = lower_bound(y, y + n, tmp);
            if (qq == y + n || (*qq).F != now.S)
                break;
            Mirror res = {(*qq).S, (*qq).F, (*qq).t};
            update(res);
        }
        else if (dir == 1) {
            Mirror tmp = {now.F, now.S + 1, 0};
            auto qq = lower_bound(x, x + n, tmp);
            if (qq == x + n || (*qq).F != now.F)
                break;
            Mirror res = *qq;
            update(res);
        }
        else if (dir == 2) {
            Mirror tmp = {now.S, now.F, 0};
            auto qq = lower_bound(y, y + n, tmp);
            if (qq == y || (*qq).F != now.S)
                break;
            qq--;
            Mirror res = {(*qq).S, (*qq).F, (*qq).t};
            update(res);
        }
        else if (dir == 3) {
            Mirror tmp = {now.F, now.S, 0};
            auto qq = lower_bound(x, x + n, tmp);
            if (qq == x || (*qq).F != now.F)
                break;
            qq--;
            Mirror res = *qq;
            update(res);
        }
        ans++;
    }
    cout << ans << endl;
}

---

P4 內積

題目敘述

給兩個長度分別為

$n,m$ 的陣列

$A,B$，求從

$A,B$ 取出一個任意長度

$l$ 的子區間

$a,b$ 的最大內積值，

$a,b$ 區間可逆

內積的算法為：

${\displaystyle \sum _{i=0}^{l-1}{a}_i\times b_i}$

解題思路

可以觀察到，對於任意一個子區間

$A[l_1,r_1],B[l_2,r_2]$，考慮兩種情況：

1. 若
   $l_1\le l_2$，那麼
   $A[l_1,r_1],B[l_2,r_2]$ 必定包含於
   $A[1,r_1],B[l_2-l_1+1,r_2]$ 內
2. 若
   $l_1>l_2$，那麼
   $A[l_1,r_1],B[l_2,r_2]$ 必定包含於
   $A[l_1-l_2+1,r_1],B[1,r_2]$ 內

綜合以上幾點我們可以發現，對於每個區間

$[l_1,r_1],[l_2,r_2]$，必定包含在

$(l_1,l_2)$ 分別為

$(1,1\sim m)$ 或是

$(1\sim n,1)$ 的區間內

若定義一個函數

$cal(l_1,l_2)$ 代表以

$l_1,l_2$ 為開頭的區間的最大區間和，那麼我們就只需要枚舉

$cal(1,1\sim m)$ 以及

$cal(1\sum n,1)$，若要算區間反轉則須把

$A$ 或是

$b$ 反轉一次並重做一次上敘的操作即可得到答案

至於

$cal()$ 的實作可以利用 (當前前墜和

$-$ 前綴最小前墜和) 的方式來找到最大連續區間和

時間複雜度：

$\mathcal{O}(n^2)$

參考程式

#define MAXN 1005
#define MAXM 1000005 
int n, m;
int x[MAXN], y[MAXN];

int cal(int i, int j) {
    int sum = 0;
    int ans = -INF;
    int mn = 0;
    for (; i < n && j < m; i++, j++) {
        sum += x[i] * y[j];
        ans = max(ans, sum - mn);
        mn = min(mn, sum);
    }
    return ans;
}

void sol() {
    cin >> n >> m;	
    for (int i = 0; i < n; i++) 
        cin >> x[i];
    for (int j = 0;j < m; j++)
        cin >> y[j];

    int ans = -INF;
    for (int i = 0; i < n; i++)
        ans = max(ans, cal(i, 0));
    for (int j = 0; j < m; j++)
        ans = max(ans, cal(0, j));
    reverse(x, x + n);
    for (int i = 0; i < n; i++)
        ans = max(ans, cal(i, 0));
    for (int j = 0; j < m; j++)
        ans = max(ans, cal(0, j));
    cout << ans << endl;
}

tags: 題解