# APCS 20220612 題解 ## 第一題:數字遊戲 [(題目敘述)](https://zerojudge.tw/ShowProblem?problemid=i399) * 用 sum[] 統計數字 1~9 出現的次數 * 找到 sum[]最大值即為出現次數最多的值 * 從i = 9往回跑,sum[i]值大於0就輸出(可避免印出重複的數字) :::spoiler Example ```cpp= #include <bits/stdc++.h> using namespace std; // 第一題程式碼 by 小律 int main() { int a, b, c, sum[10] = {0}, Max = 0; cin >> a >> b >> c; sum[a]++; sum[b]++; sum[c]++; //統計每個數字出現的次數 for(int i=1; i<=9; i++) Max = max(Max, sum[i]); //找出現次數最多的值 cout << Max << ' '; for(int i=9; i>=1; i--){ if(sum[i] > 0) cout << i << ' '; } return 0; } ::: ## 第二題:字串解碼 [(題目敘述)](https://zerojudge.tw/ShowProblem?problemid=i400) * 反過來還原密碼 * 用deque可以輕鬆 (push_back/front) & (pop_back/front) :::spoiler Example ```cpp= #include <bits/stdc++.h> using namespace std; // 第二題程式碼 by 小律 int main() { int n, w; cin >> n >> w; vector <string> v; deque <char> dq, pre, save; for(int i=0; i<n; i++) { string s; cin >> s; v.push_back(s); } for(int i=0; i<w; i++) { char c; cin >> c; dq.push_back(c); } for(int i=n-1; i>=0; i--){ //返回Step 1,先按照是指令是1 or 0 去還原 //順便統計1的數量 int counts = 0; for(int j=w-1; j>=0; j--){ if(v[i][j] == '1'){ counts++; pre.push_back(dq.back()); dq.pop_back(); } else{ pre.push_front(dq.back()); dq.pop_back(); } } dq = pre; //判斷字串是否要翻轉 if(counts % 2 == 1){ if(w % 2 == 0){ for(int k=0; k<w/2; k++){ dq.push_back(dq.front()); dq.pop_front(); } } else{ for(int k=0; k<w/2; k++){ save.push_back(dq.front()); dq.pop_front(); } for(int k=0; k<w/2; k++){ dq.push_front(dq.back()); dq.pop_back(); } for(int k=0; k<w/2; k++){ dq.push_back(save.front()); save.pop_front(); } } } pre.clear(); save.clear(); } for(int i=0; i<w; i++) cout << dq[i]; cout <<'\n'; return 0; } ``` ::: ## 第三題:雷射測試[(題目敘述)](https://zerojudge.tw/ShowProblem?problemid=i401) * 用vector <map <int, int> , int> 存鏡子的座標&鏡子的方向 * 使用二分搜(upper_bound)找到離反射點最近的鏡子座標 * 因為y可能是負數,-30000 <= y <= 30000,所以都加上N(N = 35000),解決陣列key不能為負數的問題 :::spoiler Example 1(遞迴)zj 的遞迴深度有限制,超過會造成 RE(NA 95%) ```cpp= #include <bits/stdc++.h> using namespace std; // NA 95% #define pb push_back int n, dir = 1, ans = -1, N = 35000; vector <int> x[70000], y[70000]; vector <int> rx[70000], ry[70000]; map <pair<int, int>, int> val; // dir 1 = right, 2 = down, 3 = left, 4 = up // 0 / 1\ void run(int X, int Y){ ans++; if(dir == 1 || dir == 3){ if(y[Y+N].size()){ auto it = (dir == 1) ? upper_bound(y[Y+N].begin(), y[Y+N].end(), X+N) : upper_bound(ry[Y+N].begin(), ry[Y+N].end(), X+N, greater<int>()) ; if (it != y[Y+N].end() && it != ry[Y+N].end()){ if(val[{*it, Y+N}] == 1){ dir = (dir == 1) ? 2 : 4; run(*it-N, Y); } else if(val[{*it, Y+N}] == 0){ dir = (dir == 1) ? 4 : 2; run(*it-N, Y); } } } } else if(dir == 2 || dir == 4){ if(x[X+N].size()){ auto it = (dir == 2) ? upper_bound(rx[X+N].begin(), rx[X+N].end(), Y+N, greater<int>()) : upper_bound(x[X+N].begin(), x[X+N].end(), Y+N); if (it != x[X+N].end() && it != rx[X+N].end()){ if(val[{X+N, *it}] == 1){ dir = (dir == 2) ? 1 : 3; run(X, *it-N); } else if(val[{X+N, *it}] == 0){ dir = (dir == 2) ? 3 : 1; run(X, *it-N); } } } } } int main() { cin >> n; for(int i=0; i<n; i++) { int a, b, c; cin >> a >> b >> c; x[a+N].pb(b+N); y[b+N].pb(a+N); rx[a+N].pb(b+N); ry[b+N].pb(a+N); val[{a+N, b+N}] = c; } for(int i=0; i<70000; i++){ sort(x[i].begin(), x[i].end()); sort(y[i].begin(), y[i].end()); sort(rx[i].rbegin(), rx[i].rend()); sort(ry[i].rbegin(), ry[i].rend()); } run(0, 0); cout << ans << '\n'; return 0; } ``` ::: :::spoiler Example 2(非遞迴)(AC) ```cpp= #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define pb push_back int n, dir = 1, ans = -1, N = 35000; vector<int> x[70000], y[70000]; vector<int> rx[70000], ry[70000]; map<pair<int, int>, int> val; // dir 1 = right, 2 = down, 3 = left, 4 = up // 1 '/' 2 '\' void run(int X, int Y) { bool conti = true; while (conti) { conti = false; ans++; if (dir == 1 || dir == 3) { if (y[Y].size()) { auto it = (dir == 1) ? upper_bound(all(y[Y]), X) : upper_bound(all(ry[Y]), X, greater<int>()); if (it != y[Y].end() && it != ry[Y].end()) { if (val[{*it, Y}] == 1) { dir = (dir == 1) ? 2 : 4; } else if (val[{*it, Y}] == 0) { dir = (dir == 1) ? 4 : 2; } X = *it; conti = true; continue; } } } else if (dir == 2 || dir == 4) { if (x[X].size()) { auto it = (dir == 2) ? upper_bound(all(rx[X]), Y, greater<int>()) : upper_bound(all(x[X]), Y); if (it != x[X].end() && it != rx[X].end()) { if (val[{X, *it}] == 1) { dir = (dir == 2) ? 1 : 3; } else if (val[{X, *it}] == 0) { dir = (dir == 2) ? 3 : 1; } Y = *it; conti = true; continue; } } } } } int main() { cin >> n; for (int i = 0; i < n; i++) { int a, b, c; cin >> a >> b >> c; a += N, b += N; x[a].push_back(b); y[b].push_back(a); rx[a].push_back(b); ry[b].push_back(a); val[{a, b}] = c; } for (int i = 0; i < 70000; i++) { sort(x[i].begin(), x[i].end()); sort(y[i].begin(), y[i].end()); sort(rx[i].rbegin(), rx[i].rend()); sort(ry[i].rbegin(), ry[i].rend()); } run(N, N); cout << ans << '\n'; return 0; } ``` ::: ## 第四題: 內積[(題目敘述)](https://zerojudge.tw/ShowProblem?problemid=i402) * 先建立一個sq[][] 存 x[i] * y[j] 的值 * prefix_sum 所有斜直線的值取max即為答案(記得注意陣列要倒轉) :::spoiler Example ```cpp= #include <bits/stdc++.h> using namespace std; typedef long long ll; // 第四題程式碼 by 小律 ll n, m, x[1005] , y[1005] ; ll sq[1100][1100], sq2[1100][1100]; vector <ll> v; void Do(int a, int now){ // now0 sq now1 sq2 for(ll i=0; i<a; i++){ ll Max = -999, sum = 0, zero = 0; for(ll j=0; i+j<a; j++){ if(now == 0) sum += (a == n) ? sq[i+j][j] : sq[j][i+j]; else sum += (a == n) ? sq2[i+j][j] : sq2[j][i+j]; Max = max(Max, sum); sum = max(zero, sum); } v.push_back(Max); } } int main() { for(int i=0; i<1005; i++){ for(int j=0; j<1005; j++){ sq[i][j] = -999; sq2[i][j] = -999; } } cin >> n >> m; for(ll i=0; i<n; i++) cin >> x[i] ; for(ll i=0; i<m; i++) cin >> y[i] ; for(ll i=0; i<n; i++){ for(ll j=0; j<m; j++){ sq[i][j] = x[i] * y[j]; sq2[i][m-j-1] = x[i] * y[j]; } } Do(n, 0); Do(m, 0); Do(n, 1); Do(m, 1); cout << *max_element(v.begin(), v.end()); } ``` :::