# 2022年6月APCS題解
## [1. 數字遊戲](https://zerojudge.tw/ShowProblem?problemid=i399)
去除重複元素然後排序，因為我很懶所以用`set<int, greater<int> >`。
:::spoiler code:

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    set<int, greater<int> > st;
    for (int x, i = 0; i < 3; i++) {
        cin >> x;
        st.insert(x);
    }
    cout << 4 - st.size() << ' ';
    int j = 0;
    for (const auto& i : st) {
        cout << i << " \n"[(++j) == st.size()];
    }
    return 0;
}

:::
## [2. 字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400)
題目是要解碼，所以要反過來做。
:::spoiler code:

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int m, n; cin >> m >> n;
    vector<string> v(m);
    for (string& s : v) cin >> s;
    string s; cin >> s;
    reverse(v.begin(), v.end());
    vector<string> tmp(2);
    int cnt = 0;
    for (const string& ss : v) {
        tmp[0].clear(), tmp[0].reserve(n);
        tmp[1].clear(), tmp[1].reserve(n);
        cnt = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (ss[i] == 49) cnt ^= 1;
            tmp[ss[i] ^ 48].push_back(s[i]);
        }
        reverse(tmp[0].begin(), tmp[0].end());
        s = tmp[0] + tmp[1];
        if (cnt) {
            for (int i = 0, j = n - (n >> 1); j < n; i++, j++) {
                swap(s[i], s[j]);
            }
        }
    }
    cout << s << '\n';
    return 0;
}

:::
## [3. 雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401)
我用`map`套`set`來存鏡子的位置和方向，`stx`是拿`x`座標去對`y`座標，`sty`同理，之所以用`set`是因為需要找最近的鏡子四個方向分開處理，然後`map`是我懶得離散化，也能改成`unordered_map`，不過時間差異不大，都能過，複雜度$O(n{\log}n)$。
:::spoiler code:

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using i64 = long long;
template <class T> using P = pair<T, T>;

enum dir
{
    L, R, U, D
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    unordered_map<int, set<P<int> > > stx, sty;
    int n, ans = 0; cin >> n;
    for (int x, y, t; n--; ) {
        cin >> x >> y >> t;
        stx[x].insert(P<int>(y, t));
        sty[y].insert(P<int>(x, t));
    }
    dir _d = R;
    set<P<int> >::iterator it;
    for (int x = 0, y = 0, flag = 1; flag; ) {
        switch(_d) {
            case L:
                it = sty[y].lower_bound(P<int>(x, 0));
                if (it == sty[y].begin()) {
                    flag ^= 1;
                }
                else {
                    --it;
                    if (it->S) {
                        _d = U;
                    }
                    else {
                        _d = D;
                    }
                    x = it->F;
                    ++ans;
                }
                break;
            case R:
                it = sty[y].upper_bound(P<int>(x, 1));
                if (it == sty[y].end()) {
                    flag ^= 1;
                }
                else {
                    if (it->S) {
                        _d = D;
                    }
                    else {
                        _d = U;
                    }
                    x = it->F;
                    ++ans;
                }
                break;
            case U:
                it = stx[x].upper_bound(P<int>(y, 1));
                if (it == stx[x].end()) {
                    flag ^= 1;
                }
                else {
                    if (it->S) {
                        _d = L;
                    }
                    else {
                        _d = R;
                    }
                    y = it->F;
                    ++ans;
                }
                break;
            case D:
                it = stx[x].lower_bound(P<int>(y, 0));
                if (it == stx[x].begin()) {
                    flag ^= 1;
                }
                else {
                    --it;
                    if (it->S) {
                        _d = R;
                    }
                    else {
                        _d = L;
                    }
                    y = it->F;
                    ++ans;
                }
                break;
        }
    }
    cout << ans << '\n';
    return 0;
}

:::
## [4. 內積](https://zerojudge.tw/ShowProblem?problemid=i402)
這題很明顯是個DP，於是可以定義`dp[i][j]`為取$a_i$和$b_j$當結尾的內積最大值，注意到`dp[i][j]`只有可能從`dp[i-1][j-1]`轉移，所以這題其實是斜向的連續最大和，超酷。為了實作方便，設定上面DP陣列的`i`和`j`是`1-based`，然後DP初始化為`0`，每次更新DP陣列就對`ans`取一次`max`。
然後記得要把一個向量`reverse`之後再算一次。
複雜度:$O(nm)$。
:::spoiler code:

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, ans = INT_MIN; cin >> n >> m;
    vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
    vector<int> a(n), b(m);
    for (int& i : a) cin >> i;
    for (int& i : b) cin >> i;
    for (int i = 1, t; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i - 1][j - 1] + (a[i - 1] * b[j - 1]), (a[i - 1] * b[j - 1]));
            ans = max(ans, dp[i][j]);
        }
    }
    for (vector<int>& v : dp) {
        fill(v.begin(), v.end(), 0);
    }
    reverse(a.begin(), a.end());
    for (int i = 1, t; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i - 1][j - 1] + (a[i - 1] * b[j - 1]), (a[i - 1] * b[j - 1]));
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << '\n';
    return 0;
}

:::