APCS 20220612 題解

前言 : 我確診很閒所以來寫這東西
如果你覺得我的 code 沒有註解的話，這可能是為了順便訓練讀者的觀念題讀題能力(X

數字遊戲

開一個陣列維護每個數字出現的次數，更新最大值，輸出最大值。
最後把陣列倒著跑回來，有出現就輸出。

複雜度 :

$O(1)$

#include <bits/stdc++.h>
using namespace std;
array<int, 10> C;
signed main(){
    int x, cnt = 0;
    for(int i = 0; i < 3; i++){
        cin >> x;
        C[x]++, cnt = max(cnt, C[x]);
    }
    cout << cnt << " ";
    for(int i = 9; i; i--){
        if(C[i]) cout << i << " ";
    }
    cout << "\n";
    return 0;
}

字串解碼

題目給了我們加密方法，所以我們把他倒著做就能解密了。
人話 : 把

$e$ 從頭跑到尾，如果

$e_i$ 是

$0$，那把

$T_i$ 丟到

$S$ 的左指標，同時

$S$ 的左指標往右一格。如果

$e_i$ 是

$1$，那把

$T_i$ 丟到

$S$ 的右指標，同時

$S$ 的右指標往左一格。
最後如果

$e$ 中

$1$ 出現次數是奇數就把

$S$ 左右對調。

複雜度 :

$O(NM)$

#include <bits/stdc++.h>
using namespace std;
array<string, 104> E;
string trans(string &T, string &e){
    int n = T.size(), l = 0, r = n - 1, sum = 0;
    string S;
    for(int i = 0; i < n; i++) S += ' ';
    for(int i = 0; i < n; i++){
        if(e[i] == '0') S[l++] = T[i];
        else S[r--] = T[i];
    }
    for(char c : e) sum += c;
    for(int i = 0; i < n >> 1; i++){
        if(sum & 1) swap(S[i], S[i + (n >> 1) + (n & 1)]);
    }
    return S;
}
signed main(){
    int m, n;
    string S;
    cin >> m >> n;
    for(int i = 1; i <= m; i++) cin >> E[i];
    cin >> S;
    for(int i = m; i; i--) S = trans(S, E[i]);
    cout << S << "\n";
    return 0;
}

雷射測試

先把所有鏡子照

$x$ 排序，找左右鄰居，然後改照

$y$ 排序，找上下鄰居。
然後暴力跑，不會有環，所以最多每個鏡子的正反面都被射過一遍。

複雜度 :

$O(NlogN)$

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct ban{
    int p, x, y;
};
array<int, 250004> T, X, Y;
array<array<int, 4>, 250004> N;
vector<ban> B;
bool cmpx(ban a, ban b){
    return a.x < b.x;
}
bool cmpy(ban a, ban b){
    return a.y < b.y;
}
int exp(int x, int k){
    int p = 1;
    for(; k; k >>= 1){
        if(k & 1) p *= x;
        x *= x;
    }
    return p;
}
int shoot(int p, int f){
    int cnt = 0;
    for(; p; f = (f + exp(-1, f) * T[p] + 4) % 4, p = N[p][f], cnt++);
    return cnt;
}
signed main(){
    int n, x, y, t;
    cin >> n;
    B.pb({1, 30000, 30000});
    for(int i = 2; i <= n + 1; i++){
        cin >> x >> y >> t, x += 30000, y += 30000;
        B.pb({i, x, y}), T[i] = t? 1 : -1;
    }
    sort(B.begin(), B.end(), cmpx);
    for(auto [p, i, j] : B){
        N[p][0] = Y[j], N[Y[j]][2] = p, Y[j] = p;
    }
    sort(B.begin(), B.end(), cmpy);
    for(auto [p, i, j] : B){
        N[p][3] = X[i], N[X[i]][1] = p, X[i] = p;
    }
    cout << shoot(N[1][2], 2) << "\n";
    return 0;
}

內積

暴利枚舉在

$A$ 上面要取的起點

$p$，長度為

$B$ 的長度，搞一個

$C,C_i=A_{p+i}\ast B_i$，在

$C$ 上面做最大區間和。還要把

$A$ 或

$B$ 翻轉再做一次。
最大區間和 : 不斷往後加，每加一次更新答案，如果當前區間和小於

$0$，歸零繼續跑。

複雜度 :

$O(NM)$

#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30;
array<int, 1004> A, B;
int dot(int p, int n, int m){
    int sum = 0, ans = -inf;
    for(int i = 1; i <= m; i++){
        if(p + i < 1 || p + i > n) continue;
        sum += A[p + i] * B[i];
        ans = max(ans, sum), sum = max(sum, 0);
    }
    return ans;
}
signed main(){
    int n, m, ans = -inf;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> A[i];
    for(int i = 1; i <= m; i++) cin >> B[i];
    for(int i = 1 - m; i <= n; i++) ans = max(ans, dot(i, n, m));
    for(int i = 1; i <= m >> 1; i++) swap(B[i], B[m - i + 1]);
    for(int i = 1 - m; i <= n; i++) ans = max(ans, dot(i, n, m));
    cout << ans << "\n";
    return 0;
}