# APCS 2021年09月題解
## 第一題 七言對聯
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g275
### 解套
N/A
### 題目分析
注意本題是多筆測資
用陣列a,b存兩對聯的平仄，並直接按照提述判斷條件，用字串存答案，最後輸出
如此時間複雜度$O(n)$
### 解題流程
輸入$→$if判斷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,a[8],b[8];
```
a跟b分別是兩個對聯的平仄
#### 輸入
```cpp=5
cin>>n;
while(n--){
for(int i=1;i<8;i++)cin>>a[i];
for(int i=1;i<8;i++)cin>>b[i];
```
多筆測資，先輸入測資數量，在循環地輸入每筆測資
#### 判斷答案
```cpp=9
string s="";
if(a[2]==a[4]||a[2]!=a[6]||b[2]==b[4]||b[2]!=b[6])s+="A";
if(a[7]==0||b[7]==1)s+="B";
if(a[2]==b[2]||a[4]==b[4]||a[6]==b[6])s+="C";
```
s是答案字串
依照題述判斷是否違反A、B、C三項限制，若違反就加入答案
#### 輸出
```cpp=13
if(s=="")cout<<"None\n";
else cout<<s<<"\n";
```
若s為空(沒有違反限制)就輸出None，否則直接輸出s
因為是多筆測資所以要記得換行
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,a[8],b[8];
int main(){
cin>>n;
while(n--){
for(int i=1;i<8;i++)cin>>a[i];
for(int i=1;i<8;i++)cin>>b[i];
string s="";
if(a[2]==a[4]||a[2]!=a[6]||b[2]==b[4]||b[2]!=b[6])s+="A";
if(a[7]==0||b[7]==1)s+="B";
if(a[2]==b[2]||a[4]==b[4]||a[6]==b[6])s+="C";
if(s=="")cout<<"None\n";
else cout<<s<<"\n";
}
}
```
## 第二題 魔王迷宮
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g276
### 解套
陣列處理
### 題目分析
這題的重點是各個魔王是「同時」移動
單純的處理移動位置與放置炸彈都是基本陣列操作，因此著重在如何處理兩魔王在同一位置的情形以及處理各操作的順序
實作上我使用三個陣列，分別是儲存炸彈數量的arr，魔王位置與移動向量的v，以及各個魔王是否仍在盤面上的on
魔王會不斷移動直到超出盤面，所以開一變數tmp存還在的魔王數量，並重複操作直到tmp歸零為止
因為魔王是先放炸彈再移動，所以在操作時要先遍歷所有魔王，如果他還在就在他的位置放一個炸彈(arr+1)，並且更新他的位置，且若更新後的位置超出盤面就移除該魔王
放完炸彈後要再遍歷一次處理會被炸彈炸的魔王，遍歷時若魔王所處的位置有炸彈就移除魔王並清除炸彈(arr=0)，但這樣的作法會造成後面相同位置的魔王炸不到，所以額外開一個set存所有炸過的位置，並將所在位置出現在set裡面也視為移除條件，就能炸到所有該炸的魔王
最後遍歷一次arr，並紀錄有幾格有炸彈(不是有幾個炸彈)
我不太確定這樣時間複雜度多少...(反正會過?)
### 解題流程
輸入$→$遍歷$→$輸出
### 解題過程
#### define
```cpp=2
#define F first
#define S second
```
for懶得打字的人(我)
#### 變數宣告
```cpp=5
int n,m,k,arr[100][100]={},a,b,c,d;
vector<pair<pair<int,int>,pair<int,int>>>v;//position,move
bool on[500];
```
n,m,k如題，arr,v,on如前述，a,b,c,d只是輸入用，不是太重要
#### 輸入
```cpp=9
cin>>n>>m>>k;
for(int i=0;i<k;i++){
on[i]=1;
cin>>a>>b>>c>>d;
v.push_back({{a,b},{c,d}});
}
```
輸入各魔王資訊，編號$0～k$
#### 循環遍歷
```cpp=15
int tmp=k;
while(tmp){
set<pair<int,int>>st;
for(int i=0;i<k;i++)if(on[i]==1){
arr[v[i].F.F][v[i].F.S]++;
v[i].F.F+=v[i].S.F;
v[i].F.S+=v[i].S.S;
if(v[i].F.F<0||v[i].F.F>=n||v[i].F.S<0||v[i].F.S>=m){
on[i]=0;
tmp--;
}
}
for(int i=0;i<k;i++)if(on[i]==1){
if(arr[v[i].F.F][v[i].F.S]!=0){
on[i]=0;
tmp--;
st.insert({v[i].F.F,v[i].F.S});
arr[v[i].F.F][v[i].F.S]=0;
continue;
}
if(st.size())if(st.find({v[i].F.F,v[i].F.S})!=st.end()){
on[i]=0;
tmp--;
continue;
}
}
}
```
第18-26行處理魔王放炸彈及移動，其中第23、24行是移除操作
第27-40行則是炸魔王的操作
#### 計算答案、輸出
```cpp=42
int ans=0;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(arr[i][j])ans++;
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n,m,k,arr[100][100]={},a,b,c,d;
vector<pair<pair<int,int>,pair<int,int>>>v;//position,move
bool on[500];
int main(){
cin>>n>>m>>k;
for(int i=0;i<k;i++){
on[i]=1;
cin>>a>>b>>c>>d;
v.push_back({{a,b},{c,d}});
}
int tmp=k;
while(tmp){
set<pair<int,int>>st;
for(int i=0;i<k;i++)if(on[i]==1){
arr[v[i].F.F][v[i].F.S]++;
v[i].F.F+=v[i].S.F;
v[i].F.S+=v[i].S.S;
if(v[i].F.F<0||v[i].F.F>=n||v[i].F.S<0||v[i].F.S>=m){
on[i]=0;
tmp--;
}
}
for(int i=0;i<k;i++)if(on[i]==1){
if(arr[v[i].F.F][v[i].F.S]!=0){
on[i]=0;
tmp--;
st.insert({v[i].F.F,v[i].F.S});
arr[v[i].F.F][v[i].F.S]=0;
continue;
}
if(st.size())if(st.find({v[i].F.F,v[i].F.S})!=st.end()){
on[i]=0;
tmp--;
continue;
}
}
}
int ans=0;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(arr[i][j])ans++;
cout<<ans;
}
```
## 第三題 幸運數字
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g277
### 解套
有一長度為n的陣列$a[1],a[2],...,a[n]$，依以下規則找出「幸運號碼」：
對於區間$[L,R]$幸運號碼定義：
1. 若$L=R$，幸運號碼為$a[L]$
2. 否則設區間內最小值位置為$m$，並區間改為$[L,m-1]、[m+1,R]$中擁有較大區間和的
### 題目分析
本題最關鍵的地方在於如何找到區間最小值的位置，其他部分都挺直觀的，直接照做就好，唯一需要注意的是區間和要用前綴和算，不然會太慢
最簡單的想法可能會想要硬找，但這樣光搜尋的複雜度就是$O(n)$，而在最差的情況下(例如數列遞增、遞減)會需要循環n次，總時間複雜度就是$O(n^2)$，以題目的$n=3×10^5$來說會超時
因此我們需要一個更有效率的搜尋方式
如果不超過APCS的出題範圍好像要排序再做某種操作之類的，但我沒有想到這種作法
(該作法題解可以看[這裡](https://cbjsprogramdiary.com/2023/01/18/g277-3-%e5%b9%b8%e9%81%8b%e6%95%b8%e5%ad%97/))
我的作法是直接用**線段樹**，一種稍微進階(超出APCS範圍)的資料結構，可以用$O(nlogn)$的時間初始化，$O(logn)$的時間找出區間最值、區間和等
(線段樹詳細介紹可以看[這裡](https://oi-wiki.org/ds/seg/))
在本題用的是最基礎的線段樹，不需要修改，只需要初始化與查詢就夠了，不過因為題目還需要最大值的位置，所以線段樹存的是一個pair，存最小值與該數值的位置
額外需要注意的是要特別處理最小值剛好位於邊界的情形，因為這時候用區間和算會出問題(前面減後面)，所以直接修改區間(若在左側邊界則區間在右邊，反之亦然)
最後時間複雜度$O(nlogn)$
### 解題流程
輸入、存前綴$→$用線段樹輔助搜尋$→$輸出
### 解題過程
#### define
```cpp=2
#define F first
#define S second
#define int long long
```
要記得開long long
#### 變數宣告
```cpp=6
int n,arr[3*100000+10],pre[3*100000+10]={};
pair<int,int>tree[12*100000+10];
```
arr存數列，pre存前綴和，tree存線段樹節點
#### 線段樹
```cpp=8
void BT(int l,int r,int pos){
if(l==r){
tree[pos]={arr[l],l};
return;
}
int m=(l+r)/2;
BT(l,m,2*pos+1);
BT(m+1,r,2*pos+2);
if(tree[2*pos+1].F<tree[2*pos+2].F)tree[pos]=tree[2*pos+1];
else tree[pos]=tree[2*pos+2];
return;
}
pair<int,int>query(int ql,int qr,int l,int r,int pos){
if(r<ql||l>qr)return {1e7+10,-1};
if(ql<=l&&r<=qr)return tree[pos];
int m=(l+r)/2;
auto left=query(ql,qr,l,m,2*pos+1),right=query(ql,qr,m+1,r,2*pos+2);
if(left.F<right.F)return left;
else return right;
}
```
使用的是陣列型線段樹
#### 輸入優化
```cpp=29
ios::sync_with_stdio(0);
cin.tie(0);
```
這題輸入量很大，不輸入優化會TLE
#### 輸入、存前綴和
```cpp=31
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
pre[i]=arr[i];
if(i!=0)pre[i]+=pre[i-1];
}
```
#### 線段樹初始化
```cpp=37
BT(0,n-1,0);
```
#### 搜尋答案
```cpp=39
while(l<r){
int m=query(l,r,0,n-1,0).S;
if(r==l+1){
if(arr[l]<arr[r])l=r;
else r=l;
break;
}
if(m==l)l=m+1;
else if(m==r)r=m-1;
else{
if(pre[m-1]-pre[l]+arr[l]>pre[r]-pre[m+1]+arr[m+1])r=m-1;
else l=m+1;
}
}
```
類似於二分搜的概念，以區間最小值為分割點
第46-47行處理最小值位置剛好在最左邊或最右邊的特殊情形
#### 輸出
```cpp=53
cout<<arr[l];
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
using namespace std;
int n,arr[3*100000+10],pre[3*100000+10]={};
pair<int,int>tree[12*100000+10];
void BT(int l,int r,int pos){
if(l==r){
tree[pos]={arr[l],l};
return;
}
int m=(l+r)/2;
BT(l,m,2*pos+1);
BT(m+1,r,2*pos+2);
if(tree[2*pos+1].F<tree[2*pos+2].F)tree[pos]=tree[2*pos+1];
else tree[pos]=tree[2*pos+2];
return;
}
pair<int,int>query(int ql,int qr,int l,int r,int pos){
if(r<ql||l>qr)return {1e7+10,-1};
if(ql<=l&&r<=qr)return tree[pos];
int m=(l+r)/2;
auto left=query(ql,qr,l,m,2*pos+1),right=query(ql,qr,m+1,r,2*pos+2);
if(left.F<right.F)return left;
else return right;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
pre[i]=arr[i];
if(i!=0)pre[i]+=pre[i-1];
}
BT(0,n-1,0);
int l=0,r=n-1;
while(l<r){
int m=query(l,r,0,n-1,0).S;
if(r==l+1){
if(arr[l]<arr[r])l=r;
else r=l;
break;
}
if(m==l)l=m+1;
else if(m==r)r=m-1;
else{
if(pre[m-1]-pre[l]+arr[l]>pre[r]-pre[m+1]+arr[m+1])r=m-1;
else l=m+1;
}
}
cout<<arr[l];
}
```
## 第四題 美食博覽會
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g278
### 解套
給一長度為n的數列，求k個不重疊且各自無重複數字的子序列總長度最長可為多少
例：若數列為$[1,7,1,3,1,4,4,2,7,4]，k=3$則一種可能為$[7,1,3]、[1,4]、[2,7,4]$，答案為$8$
### 題目分析
先考慮第一個子題(有50分耶)，也就是k=1的情形，換句話說就是求最長不含重複數字的子序列
很明顯的，若一個位置的數字為$a_i$，那包含他的子序列最長只能往前延伸到上一個$a_i$的下一格，
而且同時會受到前面數字的影響(若數列為$[2,4,4,2]$，則後面的$2$會受限於前面的$4$而只能到第3格)
因此我們開一個陣列$l$存每個位置最左能延伸到哪，以及一個變數$lim$紀錄當前最嚴格的限制，就能得到以每個位置為終點的最大子序列長度($i-l[i]+1$)(詳細解釋配合後面程式碼)
接下來考慮$k\neq1$的情形
因為題目保證$n×k\leq5×10^6$，所以可以猜到這題好像是$O(nk)$的dp ~~(沒錯dp就是靠通靈)~~
假設dp陣列大小是$dp[k][n]$，$dp[i][j]$代表考慮到第i個子序列(以題目來說就是人)第j個位置的答案
思考一下dp轉移式會發現跟背包dp蠻像的
如果該子序列不包含這個位置那$dp[i][j]=dp[i][j-1]$(跟取前一個一樣)
若包含該位置那$dp[i][j]=dp[i-1][l[j]-1]+j-l[j]+1)$(上一個序列只能到$l[j]-1$，後面是自己貢獻的長度)
最後答案就會是$dp[k][n]$，如此時間複雜度$O(nk)$
### 解題流程
輸入$→$一次遍歷求各位置極限$→$動態規劃$→$輸出
### 解題過程
為了方便起見以下使用1-base
#### 變數宣告
```cpp=3
int n,k,arr[1000000+10],l[1000000+10],ans=0;
unordered_map<int,int>mp;
vector<vector<int>>dp;
```
mp用來存每一個數字上一次出現的位置(看不慣可以換成一般陣列，然後用-1表示沒出現過之類的)
#### 輸入優化
```cpp=7
ios::sync_with_stdio(0);
cin.tie(0);
```
不寫也會過(不過用cin cout還是習慣性加一下)
#### 輸入
```cpp=9
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>arr[i];
```
#### 處理每個位置往左延伸的極限($l$)
```cpp=11
int lim=1;
for(int i=1;i<=n;i++){
if(mp.find(arr[i])==mp.end()){
l[i]=1;
mp.insert({arr[i],i});
}
else{
l[i]=mp[arr[i]]+1;
mp[arr[i]]=i;
}
lim=l[i]=max(lim,l[i]);
}
```
如果數字沒出現過那先假設最左可以到位置1，並更新位置(第13-16行)
若出現過則先假設最左到上次出現的下一格，並更新位置(第17-20行)
最後更新最大極限與自身極限為兩者的最大值(第21行)
例：對$[2,4,4,2]$來說，$l[4]$一開始會是$2$，但因為前面有$4$的關係變成$3$
#### 動態規劃
```cpp=23
dp.assign(k+1,vector<int>(n+1,0));
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
dp[i][j]=max(dp[i][j-1],dp[i-1][l[j]-1]+j-l[j]+1);
}
}
```
初始化dp陣列(第23行)，並執行(第24-28行)
#### 輸出
```cpp=29
cout<<dp[k][n];
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,k,arr[1000000+10],l[1000000+10],ans=0;
unordered_map<int,int>mp;
vector<vector<int>>dp;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>arr[i];
int lim=1;
for(int i=1;i<=n;i++){
if(mp.find(arr[i])==mp.end()){
l[i]=1;
mp.insert({arr[i],i});
}
else{
l[i]=mp[arr[i]]+1;
mp[arr[i]]=i;
}
lim=l[i]=max(lim,l[i]);
}
dp.assign(k+1,vector<int>(n+1,0));
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
dp[i][j]=max(dp[i][j-1],dp[i-1][l[j]-1]+j-l[j]+1);
}
}
cout<<dp[k][n];
}
```
## 心得
這次是我第一次考的APCS，事隔一年多回來寫題解感觸挺深，還記得當初是只寫得出前兩題而且第二題不只卡超久還用超複雜寫法的新手，到現在雖然不敢說很強，但至少已經有能力寫題解分享自己的思路與寫法。唯一沒什麼改變的大概只有對程式的堅持與熱愛還有偏好砸資料結構的習慣?(最好是有人一言不合就用線段樹)
---
當初寫的時候花蠻多時間在第二題的debug上，試了好幾次才成功處理掉要同時炸掉好幾個魔王的case，以至於最後沒有多少時間寫第三題(當時根本不期望自己能寫第四題)。那時雖然剛學會線段樹也打算對第三題用，但應該是不熟的緣故，所以當下一直寫錯，只好丟了個暴力解。當時考完雖然感到有些嘔氣，但現在想起來也是因為自己能力不足才會有如此狀況。
---
這次寫前三題基本上都有想法，第四題只想得到$k=1$的解，後來上網查了一下才知道要用「往前最多延伸多少」概念，也就發現轉移式其實跟背包DP有些像，才成功寫出來。我認為算是有所進步，畢竟從原本的沒想法到能想出部分解答，只要持續努力應該遲早能自己~~通靈~~想出正解。
Sign in with Wallet
Connect another wallet