# 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());
}
```
:::