# APCS 2022年06月題解
## 第一題 數字遊戲
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=i399
### 解套
N/A
### 題目分析
這種題目有很多作法，最基礎的應該是存三個變數然後分各種狀況討論
但那樣實作複雜度感覺有點高，所以我直接用C++內建的資料結構(~~我就懶~~)
要滿足「去除重複項」和「從大到小排列」，很明顯要用set
(其實也能用vector再排序再erase unique，但一樣感覺好麻煩)
另外要用set<int,greater< int>才會讓元素從大到小排列
而眾數數量可以由4-st.size()算出來
如此時間複雜度$O(1)$
(技術上是$O(nlogn)$，但反正n只有三，當常數也行ㄏㄏ)
### 解題流程
讀入測資$→$塞入set$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int a,b,c;
```
#### 把數字放進set
```cpp=6
set<int,greater<int>>st;
st.insert(a);
st.insert(b);
st.insert(c);
```
#### 輸出
眾數數量
```cpp=10
cout<<4-st.size();
```
元素
```cpp=11
auto it=st.begin();
while(it!=st.end()){
cout<<" "<<*it;
it++;
}
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main(){
cin>>a>>b>>c;
set<int,greater<int>>st;
st.insert(a);
st.insert(b);
st.insert(c);
cout<<4-st.size();
auto it=st.begin();
while(it!=st.end()){
cout<<" "<<*it;
it++;
}
}
```
## 第二題 字串解碼
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=i400
### 解套
依指定規則解密
### 題目分析
**重要觀念：解密時要把加密時所有順序都反著做**
除了加密字串要由後往前處理外，
也要先做加密步驟2(按照01判斷接前接後)再做加密步驟1(前後交換)
接下來分析一下加密的兩個步驟要怎麼反操作
1. 很明顯操作不變，因為交換的反操作就是交換
2. 因為加密是「若為0接後面，否則接前面」，因此要還原它就要「若為0接前面，否則接後面」，而且在加密時是「由1到n」，所以解密要「由n到1」
如此就得到解密步驟：
1. 從後往前遍歷字串，並按照01產生新字串，同時記錄有幾個1
2. 如果1的數量是奇數就把字串前後交換
在執行上，步驟1時我用deque執行剪接字元的操作，並於步驟2時再依照需求把它轉成相對應的字串
整個解密過程我寫成一個函數，方便重複調用(加密字串可能不只一個)
如此複雜度$O(mn)$
### 解題流程
讀入測資$→$重複解密$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int m,n;
string s,e;
vector<string>Es;
```
m,n,s,e與題目同義
Es存所有01字串
#### 解密函式
**函式宣告**
```cpp=6
string chg(string s,string e){
```
s是要解密的字串，e是01字串
**變數**
```cpp=7
int cnt=0;
deque<char>dq;
```
cnt紀錄01字串裡有幾個1，dq用於解密操作
```cpp=18
string rt;
```
最後回傳的字串
**步驟一(按照01字串生成新字串)**
```cpp=9
for(int i=e.size()-1;i>=0;i--){
if(e[i]=='1'){
cnt++;
dq.push_back(s[i]);
}
else{
dq.push_front(s[i]);
}
}
```
從後往前遍歷字串，若該位置為1將字元接到後面，否則接到前面
同時記錄1的數量
**步驟二(前後半交換)**
不需交換
```cpp=19
if(cnt%2==0){
for(char i:dq)rt+=i;
return rt;
}
```
直接把dq轉成字串並回傳
---
需要交換
```cpp=23
else{
if(s.size()%2==0){
int mid=s.size()/2;
for(int i=mid;i<s.size();i++)rt+=dq[i];
for(int i=0;i<mid;i++)rt+=dq[i];
}
else{
int mid=s.size()/2;
for(int i=mid+1;i<s.size();i++)rt+=dq[i];
rt+=dq[mid];
for(int i=0;i<mid;i++)rt+=dq[i];
}
return rt;
}
```
先把dq後半變成字串，再把前半段接上去，最後回傳
#### 讀入測資
```cpp=39
cin>>m>>n;
while(m--){
cin>>e;
Es.push_back(e);
}
cin>>s;
```
#### 解密、輸出
```cpp=45
while(Es.size()){
s=chg(s,Es[Es.size()-1]);
Es.pop_back();
}
cout<<s;
```
將01字串按輸入順序倒著處理
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int m,n;
string s,e;
vector<string>Es;
string chg(string s,string e){
int cnt=0;
deque<char>dq;
for(int i=e.size()-1;i>=0;i--){
if(e[i]=='1'){
cnt++;
dq.push_back(s[i]);
}
else{
dq.push_front(s[i]);
}
}
string rt;
if(cnt%2==0){
for(char i:dq)rt+=i;
return rt;
}
else{
if(s.size()%2==0){
int mid=s.size()/2;
for(int i=mid;i<s.size();i++)rt+=dq[i];
for(int i=0;i<mid;i++)rt+=dq[i];
}
else{
int mid=s.size()/2;
for(int i=mid+1;i<s.size();i++)rt+=dq[i];
rt+=dq[mid];
for(int i=0;i<mid;i++)rt+=dq[i];
}
return rt;
}
}
int main(){
cin>>m>>n;
while(m--){
cin>>e;
Es.push_back(e);
}
cin>>s;
while(Es.size()){
s=chg(s,Es[Es.size()-1]);
Es.pop_back();
}
cout<<s;
}
```
## 第三題 雷射測試
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=i401
### 解套
一平面上有許多鏡子，其中有\與/兩種，一雷射光從$(0,0)$向右出發，其會反射幾次？
### 題目分析
很明顯地，這題最大的挑戰在於如何快速地找到下一個遇到的鏡子
如果每次都要從所有鏡子裡$O(n)$地找，複雜度會是$O(n^2)$，顯然是無法接受的，而跟搜尋有關又比線性搜尋快的是...二分搜！
不過這時又會遇到另一個問題，就是鏡子要事先按照甚麼順序排序
這時會發現如果是往左右走會需要遇到相同y座標的鏡子才行，故鏡子應該按照y座標由小到大排序
//畫圖?
同理如果是往上下走會需要遇到相同x座標的鏡子才行，故鏡子應該按照x座標由小到大排序
因此就得到我們的實作方式：
開兩個set儲存鏡子座標，一個叫xst按x座標由小到大排，另一個叫yst按y座標由小到大排
遍歷時紀錄當前的x座標、y座標、鏡子種類與前進方向，並根據前進方向尋找下一面鏡子，
若找不到下一面鏡子則結束遍歷
如此時間複雜度$O(nlogn)$
### 解題流程
讀入測資$→$遍歷、處理$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,x,y;
bool t;
set<pair<pair<int,int>,bool>>xst,yst;
```
變數名稱與題目或前面提到的相同
```cpp=14
int ans=0,cx=0,cy=0,ct=0,d=3;// up down left right 0 1 2 3
```
ans存最終答案，cx、cy、ct分別是當前x座標、y座標與鏡子種類，
d存前進方向(上下左右分別是0123)
#### 讀入測資、初始化
```cpp=7
cin>>n;
for(int i=0;i<n;i++){
cin>>x>>y>>t;
xst.insert({{x,y},t});
yst.insert({{y,x},t});
}
yst.insert({{0,0},0});
```
因為一開始是從$(0,0)$向右，故在yst放入初始點座標
#### 遍歷
**方向向上**
```cpp=16
if(d==0){
auto it=xst.find({{cx,cy},ct}),nxt=xst.find({{cx,cy},ct});
nxt++;
if(nxt==xst.end()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.first;
cy=nxt->first.second;
ct=nxt->second;
if(ct==0)d=3;
else d=2;
}
}
```
(因為是向上所以用xst尋找)
在xst中找到當前座標與下一個座標(下一個座標用目前座標往後推來得到)(第17～18行)
此時若沒有下一個位置(到底了)或是下一個位置x座標已經不一樣了，
代表雷射不會再繼續反射，終止遍歷(第19行)
接下來就是更新座標與鏡子種類，並根據鏡子種類決定新的方向
若從下面往上撞上$/$，方向會改為向右(3)，若從下面往上撞上$\backslash$，方向會改為向左(2)
---
其他方向依此類推
**方向向下**
```cpp=28
else if(d==1){
auto it=xst.find({{cx,cy},ct}),nxt=xst.find({{cx,cy},ct});
nxt--;
if(it==xst.begin()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.first;
cy=nxt->first.second;
ct=nxt->second;
if(ct==0)d=2;
else d=3;
}
}
```
因為向下y座標會減少，故下一位置要用當前位置往前推一個
**方向向左**
```cpp=40
else if(d==2){
auto it=yst.find({{cy,cx},ct}),nxt=yst.find({{cy,cx},ct});
nxt--;
if(it==yst.begin()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.second;
cy=nxt->first.first;
ct=nxt->second;
if(ct==0)d=1;
else d=0;
}
}
```
**方向向右**
```cpp=52
else{
auto it=yst.find({{cy,cx},ct}),nxt=yst.find({{cy,cx},ct});
nxt++;
if(nxt==yst.end()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.second;
cy=nxt->first.first;
ct=nxt->second;
if(ct==0)d=0;
else d=1;
}
}
```
---
**更新答案**
```cpp=64
ans++;
yst.erase({{0,0},0});
```
另外要把初始座標刪掉，因為那邊事實上沒有鏡子
#### 輸出
```cpp=67
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,x,y;
bool t;
set<pair<pair<int,int>,bool>>xst,yst;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>x>>y>>t;
xst.insert({{x,y},t});
yst.insert({{y,x},t});
}
yst.insert({{0,0},0});
int ans=0,cx=0,cy=0,ct=0,d=3;// up down left right 0 1 2 3
while(1){
if(d==0){
auto it=xst.find({{cx,cy},ct}),nxt=xst.find({{cx,cy},ct});
nxt++;
if(nxt==xst.end()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.first;
cy=nxt->first.second;
ct=nxt->second;
if(ct==0)d=3;
else d=2;
}
}
else if(d==1){
auto it=xst.find({{cx,cy},ct}),nxt=xst.find({{cx,cy},ct});
nxt--;
if(it==xst.begin()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.first;
cy=nxt->first.second;
ct=nxt->second;
if(ct==0)d=2;
else d=3;
}
}
else if(d==2){
auto it=yst.find({{cy,cx},ct}),nxt=yst.find({{cy,cx},ct});
nxt--;
if(it==yst.begin()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.second;
cy=nxt->first.first;
ct=nxt->second;
if(ct==0)d=1;
else d=0;
}
}
else{
auto it=yst.find({{cy,cx},ct}),nxt=yst.find({{cy,cx},ct});
nxt++;
if(nxt==yst.end()||nxt->first.first!=it->first.first)break;
else{
cx=nxt->first.second;
cy=nxt->first.first;
ct=nxt->second;
if(ct==0)d=0;
else d=1;
}
}
ans++;
yst.erase({{0,0},0});
}
cout<<ans;
}
```
## 第四題 內積
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=i402
### 解套
有兩長度分別為$n,m$的陣列$A_1,A_2,...,A_n$與$B_1,B_2,...,B_n$
對任何正整數$r$，求$\sum_{k=0}^{r} A_{i+k}+B_{j+k}$的最大值
### 題目分析
看到這題我第一個想到的是：「這題的n和m都只有1000而已誒！好像可以$O(nm)$硬爆之類的」
不過用最直觀的方式(所有組合試一遍且沒有優化)複雜度大概會是$O(n^2m)$之類的
所以問題就變成：要如何效率的枚舉？
這時我們發現，如果我們固定其中一個陣列永遠從第一個數字開始試，並枚舉另一陣列的起始位置，
就能把可能的組合數壓到$n$或$m$
(例如第二個陣列固定從第一個開始，另一個陣列依序用第一個、第二個...跟第一個配)
而對每一個組合來說，答案會跟最大子序列和有些相似，只是處理的數字會是兩個陣列相應值的乘積
舉例來說，假設兩陣列分別是$[1,2,3,4]$、$[-1,9,7,-5]$，那枚舉的部分就會讓1配到-1、2配到-1、3配到-1、4配到-1
而就2配到-1的例子來說，就相當於處理$[-2,27,28]$的最大子序列和，也就是55
不過題目說可以翻轉，所以要把某個陣列倒轉後，再把上述過程重複一遍，就能的到答案
如此時間複雜度是枚舉的$O(n)$乘上最大子序列和的$O(n)$，也就是$O(n^2)$
### 解題流程
讀入測資$→$遍歷、處理$→$翻轉$→$遍歷、處理$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,A[1000+10],B[1000+10];
```
變數名稱與題述相同
```cpp=6
int ans=INT_MIN;
```
最終的答案，先設為極小值
#### 輸入
```cpp=5
cin>>n>>m;
```
```cpp=7
if(n>m){
for(int i=0;i<n;i++)cin>>A[i];
for(int i=0;i<m;i++)cin>>B[i];
}
else{
for(int i=0;i<n;i++)cin>>B[i];
for(int i=0;i<m;i++)cin>>A[i];
swap(n,m);
}
```
為方便起見，強制讓A是長度比較長的陣列，且n比m大
#### 計算答案
```cpp=16
for(int i=-m+1;i<n;i++){
int tmp=0;
for(int j=0;j<m;j++){
if(i+j>=n||i+j<0)continue;
tmp+=A[i+j]*B[j];
ans=max(ans,tmp);
tmp=max(tmp,0);
}
}
```
外層迴圈決定A陣列的起始位置，內層迴圈則是一般的最大子序列和
```cpp=25
for(int i=0;i<m/2;i++)swap(B[i],B[m-i-1]);
```
將B陣列倒轉
```cpp=26
for(int i=-m+1;i<n;i++){
int tmp=0;
for(int j=0;j<m;j++){
if(i+j>=n||i+j<0)continue;
tmp+=A[j+i]*B[j];
ans=max(ans,tmp);
tmp=max(tmp,0);
}
}
```
B陣列倒轉後再更新一次答案
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,A[1000+10],B[1000+10];
int main(){
cin>>n>>m;
int ans=INT_MIN;
if(n>m){
for(int i=0;i<n;i++)cin>>A[i];
for(int i=0;i<m;i++)cin>>B[i];
}
else{
for(int i=0;i<n;i++)cin>>B[i];
for(int i=0;i<m;i++)cin>>A[i];
swap(n,m);
}
for(int i=-m+1;i<n;i++){
int tmp=0;
for(int j=0;j<m;j++){
if(i+j>=n||i+j<0)continue;
tmp+=A[i+j]*B[j];
ans=max(ans,tmp);
tmp=max(tmp,0);
}
}
for(int i=0;i<m/2;i++)swap(B[i],B[m-i-1]);
for(int i=-m+1;i<n;i++){
int tmp=0;
for(int j=0;j<m;j++){
if(i+j>=n||i+j<0)continue;
tmp+=A[j+i]*B[j];
ans=max(ans,tmp);
tmp=max(tmp,0);
}
}
cout<<ans;
}
```
## 心得
這是第二次參加APCS，比起上次有把握了許多，原本的目標是拿到四級分並看看有沒有辦法五級，後來也確實達成了，原本心情還不錯，只是後來聽說同學拿到五級分，自己事後再想想發現第四題真的沒有那麼難，自己當初應該要寫出來的，所以懊惱了一陣子...
---
當初在寫的時候前三題基本上沒有遇到大障礙，只是因為第二跟第三題實作量都比較大一些所以花了比較多時間。第四題我記得當時想弄一種有點複雜的DP，結果要到太多記憶體導致程式當掉(這是事後想到發現的，那時候只是自己乾著急而已)。不過因為原本只想說把前三題寫完，時間也剩不多，我就放棄思考第四題而去檢查前三題看有沒有bug，當然後來證明這個選擇不是太聰明。
---
我認這次最難的是第三題，因為實作上最複雜，當時只有想到set，不過後來自己重寫的時候發現用vector配lower_bound就不用把原點也放進去事後再拿掉。另外第四題事實證明沒有想像中那麼難，甚至算不太上是DP，可見自己不應該自我設限，即使一開始想不出來也要努力嘗試，說不定就試出答案了。
Sign in with Wallet
Connect another wallet