# APCS 20220612 題解
前言 : 我確診很閒所以來寫這東西
如果你覺得我的 code 沒有註解的話,這可能是為了順便訓練讀者的觀念題讀題能力(X
## [數字遊戲](https://zerojudge.tw/ShowProblem?problemid=i399)
開一個陣列維護每個數字出現的次數,更新最大值,輸出最大值。
最後把陣列倒著跑回來,有出現就輸出。
複雜度 : $O(1)$
```cpp=
#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;
}
```
## [字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400)
題目給了我們加密方法,所以我們把他倒著做就能解密了。
人話 : 把 $e$ 從頭跑到尾,如果 $e_i$ 是 $0$,那把 $T_i$ 丟到 $S$ 的左指標,同時 $S$ 的左指標往右一格。如果 $e_i$ 是 $1$,那把 $T_i$ 丟到 $S$ 的右指標,同時 $S$ 的右指標往左一格。
最後如果 $e$ 中 $1$ 出現次數是奇數就把 $S$ 左右對調。
複雜度 : $O(NM)$
```cpp=
#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;
}
```
## [雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401)
先把所有鏡子照 $x$ 排序,找左右鄰居,然後改照 $y$ 排序,找上下鄰居。
然後暴力跑,不會有環,所以最多每個鏡子的正反面都被射過一遍。
複雜度 : $O(NlogN)$
```cpp=
#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;
}
```
## [內積](https://zerojudge.tw/ShowProblem?problemid=i402)
暴利枚舉在 $A$ 上面要取的起點 $p$,長度為 $B$ 的長度,搞一個 $C, C_i = A_{p + i} * B_i$,在 $C$ 上面做最大區間和。還要把 $A$ 或 $B$ 翻轉再做一次。
最大區間和 : 不斷往後加,每加一次更新答案,如果當前區間和小於 $0$,歸零繼續跑。
複雜度 : $O(NM)$
```cpp=
#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;
}
```