# 2021年9月APCS題解
## [1. 七言對聯](https://zerojudge.tw/ShowProblem?problemid=g275)
注意到每一句只有第二、四、六、七個字會用到，而且可以把句子第二、四、六個字的平仄轉成整數來判斷。第一個規則代表上下聯一定要是${010}_2(={2}_{10})$或${101}_2(={5}_{10})$；第二個規則可以直接判斷；第三個規則則是上下聯bitwise xor要是$7_{10}(={111}_{2})$，也就是每個位置都不同。
:::spoiler code:

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, upend, downend, up, down, x, f; cin >> n;
    for (int i = 0; i < n; i++) {
        up = down = 0;
        for (int j = 0; j < 3; j++) {
            cin >> x >> x;
            (up <<= 1) += x;
        }
        cin >> upend;
        for (int j = 0; j < 3; j++) {
            cin >> x >> x;
            (down <<= 1) += x;
        }
        cin >> downend;
        f = 1;
        if ((up != 2 && up != 5) || (down != 2 && down != 5)) {
            cout << 'A';
            f = 0;
        }
        if ((!upend) || (downend)) {
            cout << 'B';
            f = 0;
        }
        if ((up ^ down) != 7) {
            cout << 'C';
            f = 0;
        }
        if (f) {
            cout << "None\n";
        }
        else {
            cout << '\n';
        }
    }
    return 0;
}

:::

## [2. 魔王迷宮](https://zerojudge.tw/ShowProblem?problemid=g276)
我把魔王包進一個結構，然後把移動和檢查出界和檢查消失的函式封裝在裡面，先放炸彈再讓魔王移動，判斷有沒有出界或踩到炸彈，如果踩到炸彈就把炸彈的位置放到一個`queue`裡面，等魔王全部移動完再移除炸彈，最後魔王全部消失的時候遍歷一次棋盤算還有幾個炸彈。
:::spoiler code:

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using p2i = pair<int, int>;

struct boss
{
    bool ok;
    int r, c, s, t;
    boss(): ok(true), r(), c(), s(), t() {}
    inline void move() {
        r += s;
        c += t;
    }
    inline bool check(const int& n, const int& m) { //判斷出界
        return (ok = ((r >= 0 && r < n) && (c >= 0 && c < m)));
    }
    explicit inline operator bool() const { //用顯式轉型成bool判斷是否已經消失
        return ok;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k, cnt, ans = 0; cin >> n >> m >> k;
    cnt = k;
    vector<vector<int> > board(n, vector<int>(m, 0));
    vector<boss> v(k);
    for (boss& b : v) {
        cin >> b.r >> b.c >> b.s >> b.t;
    }
    queue<p2i> clrpos;
    p2i tmp;
    while (cnt) {
        for (int i = 0; i < k; i++) {
            if (!v[i]) continue;
            board[v[i].r][v[i].c] = 1;
        }
        for (int i = 0; i < k; i++) {
            if (!v[i]) continue;
            v[i].move();
            if (v[i].check(n, m)) {
                if (board[v[i].r][v[i].c]) {
                    v[i].ok = false;
                    --cnt;
                    clrpos.push(p2i(v[i].r, v[i].c));
                }
            }
            else {
                --cnt;
            }
        }
        for (; !clrpos.empty(); clrpos.pop()) {
            tmp = clrpos.front();
            board[tmp.F][tmp.S] = 0;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j]) ++ans;
        }
    }
    cout << ans << '\n';
    return 0;
}

:::

## [3. 幸運數字](https://zerojudge.tw/ShowProblem?problemid=g277)
區間最小位置我是用稀疏表(因為這題不用修改，不然其實線段樹也可以用)，區間和用前綴和陣列，然後我的code裡面的編號都是0-based，然後左閉右開。
時間複雜度:sparse table build:$O(n{\log}n)$，找幸運號碼最差$O(n)$，所以是$O(n{\log}n)$。
:::spoiler code:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct sparse_table
{
    int n;
    vector<int> data;
    vector<vector<int> > table;
    sparse_table(const int& _n, vector<i64>& _pre) :n(_n), data(_n, 0), table((__lg(_n) + 1), vector<int>(n, 0)) {
        iota(table[0].begin(), table[0].end(), 0);
        for (int i = 0; i < n; i++) {
            cin >> data[i];
            _pre[i + 1] = _pre[i] + data[i];
        }
        for (int i = 1; (1 << i) <= n; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                table[i][j] = (data[table[i - 1][j]] < data[table[i - 1][j + (1 << (i - 1))]] ? table[i - 1][j] : table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    inline int operator() (const int& l, const int& r) {
        static int ansL, ansR, lglen;
        lglen = __lg(r - l);
        ansL = table[lglen][l];
        ansR = table[lglen][r - (1 << lglen)];
        return (data[ansL] < data[ansR] ? ansL : ansR);
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<i64> pre(n + 1, 0);
    sparse_table st(n, pre);
    function<i64(const int&, const int&)> calc = [&pre] (const int& _l, const int& _r) -> i64 {
        return pre[_r] - pre[_l];
    };
    int l = 0, r = n, mid;
    i64 lsum, rsum;
    while (l < r - 1) {
        mid = st(l, r);
        lsum = calc(l, mid), rsum = calc(mid + 1, r);
        if (rsum >= lsum) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    cout << st.data[l] << '\n';
    return 0;
}

:::

## [4. 美食博覽會](https://zerojudge.tw/ShowProblem?problemid=g278)
這是一題~~看數字範圍猜複雜度~~$O(nk)$的DP(或$O(n{\log}C)$，如果你是外星人)，在DP之前需要做預處理，定義`v[i]`為以第`i`個數結尾的最長無重複元素的連續子區間長度，`dp[j][i]`為第`j`個人選第`1~i`個位置結尾的前綴最大值，則轉移式會長這樣:`dp[j][i] = max(dp[j][i - 1], dp[j - 1][i - v[i]] + v[i])`，實作為了方便所以用1-based，然後我發現DP陣列只會從上一個人轉移，所以我把DP陣列滾動掉了。
時間複雜度:$O(nk)$
空間複雜度:$O(n)$
:::spoiler code:

#include <bits/stdc++.h>
using namespace std;

int pos[100001]; //存每個數字第一次出現的位置

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k; cin >> n >> k;
    vector<vector<int> > dp(2, vector<int>(n + 1, 0));
    vector<int> v(n + 1, 0);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        v[i] = min(i - pos[x], v[i - 1] + 1); //找以$a_i$為結尾的最長無重複元素的連續子區間長度
        pos[x] = i;
    }
    for (int j = 1; j <= k; j++) {
        for (int i = 1; i <= n; i++) {
            dp[j & 1][i] = max(dp[j & 1][i - 1], dp[(j & 1) ^ 1][i - v[i]] + v[i]);
        }
    }
    cout << dp[k & 1][n] << '\n';
    return 0;
}

:::
這題在zerojudge上有k值加大的版本([h926](https://zerojudge.tw/ShowProblem?problemid=h926))，需要用Aliens優化才能過，有關Aliens優化的東西可以去看[這篇](https://cp.wiwiho.me/aliens/)，~~雖然我不會證明這題用Aliens優化會是好的，但是這題的tag上就有個aliens~~
:::spoiler Aliens優化版本code:

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using p2i = pair<int, int>;

int pos[100001];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    function<bool(const p2i&, const p2i&)> cmp = [] (const p2i& a, const p2i& b) -> bool {
        return ((a.F < b.F) || (a.F == b.F && a.F > b.F));
    };
    int n, k; cin >> n >> k;
    vector<p2i> dp(n + 2, p2i(0, 0));
    vector<int> v(n + 1, 0);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        v[i] = min(i - pos[x], v[i - 1] + 1);
        pos[x] = i;
    }
    function<void(const int&)> check = [&] (const int& p) -> void {
        for (int i = 1; i <= n; i++) {
            dp[n + 1] = dp[i - v[i]];
            dp[n + 1].F += v[i] - p;
            ++dp[n + 1].S;
            dp[i] = max(dp[i - 1], dp[n + 1], cmp);
        }
    };
    int l = -1, r = (n + (n % k)) / k, mid;
    while (l < r - 1) {
        mid = (l + r) >> 1;
        check(mid);
        if (dp[n].S <= k) r = mid;
        else l = mid;
    }
    check(r);
    cout << dp[n].F + k * r << '\n';
    return 0;
}

:::