# APCS 2022年01月題解
## 第一題 程式交易
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h081
### 解套
N/A
### 題目分析
直接按照題目說的做就好
開三個變數ans,buy,sell紀錄獲利、購入價格、售出價格
因為題目保證價格都是正整數，所以buy與sell都預設是0，
並在後續透過兩者是不是0判斷當下是要買進還是賣出
另外因為題目說「若交易結束仍持有股票，則不考慮該股票買進的成本，直接無視該股票即可」，
所以是在每一次賣出時才算利潤
如此時間複雜度$O(n)$
### 解題流程
輸入測資$→$遍歷、處理$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,d,arr[100],ans=0,buy=0,sell=0;
```
arr即題目所提的a，其他與題目、前述相同
#### 輸入
```cpp=5
cin>>n>>d;
for(int i=0;i<n;i++)cin>>arr[i];
```
#### 遍歷、處理
```cpp=7
buy=arr[0];
for(int i=1;i<n;i++){
if(buy!=0&&arr[i]>=buy+d){
ans+=arr[i]-buy;
buy=0;
sell=arr[i];
}
if(sell!=0&&arr[i]<=sell-d){
buy=arr[i];
sell=0;
}
}
```
一開始先在時間點0買入(題目說1但我的程式碼是0-base)
接著依時間順序處理所有價格，會分成兩種情形：
1.當下已購入股票(要賣)：判斷方式是buy不等於0
此時若符合條件(arr[i]>=buy+d)則賣出，更新ans、buy、sell
2.當下未購入股票(要買)：判斷方式是sell不等於0
此時若符合條件(arr[i]<=sell-d)則買入，更新ans、buy、sell
#### 輸出
```cpp=19
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,d,arr[100],ans=0,buy=0,sell=0;
int main(){
cin>>n>>d;
for(int i=0;i<n;i++)cin>>arr[i];
buy=arr[0];
for(int i=1;i<n;i++){
if(buy!=0&&arr[i]>=buy+d){
ans+=arr[i]-buy;
buy=0;
sell=arr[i];
}
if(sell!=0&&arr[i]<=sell-d){
buy=arr[i];
sell=0;
}
}
cout<<ans;
}
```
## 第二題 贏家預測
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h082
### 解套
按照題目敘述操作即可
### 題目分析
因為n最大只有1000，m最大只有5，所以在解題時不太需要考慮複雜度的問題，
可以直接按題目說的模擬看看
開一個vector<pair<pair<int,int>,pair<int,int>>>arr紀錄每個人的$[$戰力、應變力、輸的次數、編號$]$，以及型態與之相同的win與lose暫時紀錄勝者與敗者
接著就不斷重複以下步驟直到只剩一人為止(arr.size()==1)：
1. 從頭遍歷arr，每次跳兩個，按照題述判斷勝負，將贏家push進win、輸家push進lose，並變更戰力、應變力與輸的次數
2. 把arr清空後，先把win的人push進去再把lose的人push進去，清空win、lose
最後輸出剩下的人的編號
如此時間複雜度$O(n^2m)$(m最大只到5所以也可以不算)
另外需要注意可能會爆int，所以要開long long
### 解題流程
輸入測資$→$反覆遍歷、處理$→$輸出
### 解題過程
#### 各種define
(這部分沒寫不會怎樣，只是後面打字量爆增)
```cpp=2
#define F first
#define S second
#define int long long int
#define a arr[i].F.F
#define b arr[i].F.S
#define c arr[i+1].F.F
#define d arr[i+1].F.S
```
第2-3行算是常見的縮寫，第5-8行是根據題目定義的，第4行是在一開始沒想到會爆int的補救措施
#### 變數宣告
```cpp=10
int n,m;
vector<pair<pair<int,int>,pair<int,int>>>arr;//戰力，應變力，輸，編號
int s[1000],t[1000],id[1000];
vector<pair<pair<int,int>,pair<int,int>>>win;
vector<pair<pair<int,int>,pair<int,int>>>lose;
```
與前述、題述相同(id即題目的idx)
#### 輸入
```cpp=16
cin>>n>>m;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++)cin>>t[i];
for(int i=0;i<n;i++)cin>>id[i];
for(int i=0;i<n;i++){
arr.push_back({{s[id[i]-1],t[id[i]-1]},{0,id[i]}});
}
```
#### 反覆遍歷
```cpp=23
while(arr.size()>1){
for(int i=0;i+1<arr.size();i+=2){
if(a*b>=c*d){
win.push_back({{a+c*d/2/b,b+c*d/2/a},{arr[i].S.F,arr[i].S.S}});
lose.push_back({{c+c/2,d+d/2},{arr[i+1].S.F+1,arr[i+1].S.S}});
}
else{
win.push_back({{c+a*b/2/d,d+a*b/2/c},{arr[i+1].S.F,arr[i+1].S.S}});
lose.push_back({{a+a/2,b+b/2},{arr[i].S.F+1,arr[i].S.S}});
}
}
if(arr.size()%2==1)win.push_back(arr[arr.size()-1]);
arr.clear();
for(int j=0;j<win.size();j++)arr.push_back(win[j]);
win.clear();
for(int j=0;j<lose.size();j++){
if(lose[j].S.F==m)continue;
else arr.push_back(lose[j]);
}
lose.clear();
}
```
要注意若輸的次數已經到達m次就不用繼續處理(不用push進lose)
第34行處理總人數是奇數的情況，此時直接晉級，不動數值
#### 輸出
```cpp=44
cout<<arr[0].S.S;
```
輸出最後勝者的編號
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define F first
#define S second
#define int long long int
#define a arr[i].F.F
#define b arr[i].F.S
#define c arr[i+1].F.F
#define d arr[i+1].F.S
using namespace std;
int n,m;
vector<pair<pair<int,int>,pair<int,int>>>arr;//戰力，應變力，輸，編號
int s[1000],t[1000],id[1000];
vector<pair<pair<int,int>,pair<int,int>>>win;
vector<pair<pair<int,int>,pair<int,int>>>lose;
signed main(){
cin>>n>>m;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++)cin>>t[i];
for(int i=0;i<n;i++)cin>>id[i];
for(int i=0;i<n;i++){
arr.push_back({{s[id[i]-1],t[id[i]-1]},{0,id[i]}});
}
while(arr.size()>1){
for(int i=0;i+1<arr.size();i+=2){
if(a*b>=c*d){
win.push_back({{a+c*d/2/b,b+c*d/2/a},{arr[i].S.F,arr[i].S.S}});
lose.push_back({{c+c/2,d+d/2},{arr[i+1].S.F+1,arr[i+1].S.S}});
}
else{
win.push_back({{c+a*b/2/d,d+a*b/2/c},{arr[i+1].S.F,arr[i+1].S.S}});
lose.push_back({{a+a/2,b+b/2},{arr[i].S.F+1,arr[i].S.S}});
}
}
if(arr.size()%2==1)win.push_back(arr[arr.size()-1]);
arr.clear();
for(int j=0;j<win.size();j++)arr.push_back(win[j]);
win.clear();
for(int j=0;j<lose.size();j++){
if(lose[j].S.F==m)continue;
else arr.push_back(lose[j]);
}
lose.clear();
}
cout<<arr[0].S.S;
}
```
## 第三題 數位占卜
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h083
### 解套
給定m個字串，求有幾組字串前後接在一起後再從中切開可形成兩個一模一樣的字串
(ex. piep+ie=piepie=pie|pie)
### 題目分析
> 我原本在2022/4過的程式碼因為後來調整時限現在過不了(我太廢)，本題解法參考自[這裡](https://ithelp.ithome.com.tw/articles/10285351)
> (細節上還是有一點差別)
>
這題最大的重點在於如何有效率地找到能與一字串對應的相應字串
首先對於已經組合的字串來說(如例子中的piepie)，他的形式是SS(假設S是一字串)
為了要把SS拆得比較細，因此再假設他是ABAB
這時會發現要組成ABAB，符合的有三種可能：A+BAB、AB+AB、ABA+B
但是題目說不會有相同的字串，所以AB+AB的可能就刪掉了
而又會發現A+BAB和ABA+B如果都算會造成一個答案重複算到(如piep+ie和ie+piep)
所以只要選一個算就好，而我算的是ABA+B
那這要怎麼實作呢？因為字串都不是很長，所以我們可以直接枚舉
枚舉其中一字串兩側長度一樣的子字串，如果發現他們一樣就代表都是A，這時剩下的部分就是B，再看其他字串有沒有剛好等於B的就好了，如果有就把答案加一
(例如piep，先切成p | ie | p，發現"p"=="p"，於是搜尋其他字串有沒有剛好是"ie"的)
至於搜尋的部分我是用unordered_set 達到$O(1)$搜尋(用二分搜也會過，但比較慢)
這樣總複雜度會是$O(mn)$(假設n是字串長度)
### 解題流程
輸入測資$→$枚舉、用函式算答案$→$輸出
### 解題過程
#### 變數宣告
```cpp=4
int m,ans=0;
string s;
unordered_set<string>st;
```
ans存答案，st存所有字串，方便搜尋
#### 找目標字串的函式
```cpp=6
void findaim(string& tmp){
for(int i=1;i*2<=tmp.size();i++){
auto a=tmp.substr(0,i),aa=tmp.substr(tmp.size()-i,i);
if(a!=aa)continue;
else{
if(st.find(tmp.substr(i,tmp.size()-i-i))!=st.end())ans++;
}
}
return;
}
```
枚舉A部分(第8行)，若兩者不同就繼續找(第9行)，不然就搜尋中間的B部分(第11行)
#### 輸入優化
```cpp=17
ios::sync_with_stdio(0);
cin.tie(0);
```
如果用二分搜又不加就會TLE
#### 輸入
```cpp=19
cin>>m;
for(int i=0;i<m;i++){
cin>>s;
st.insert(s);
}
```
同時把字串放進set裡
#### 遍歷找答案
```cpp=24
auto it=st.begin();
while(it!=st.end()){
string tmp=*it;
findaim(tmp);
it++;
}
```
枚舉所有字串，計算每個字串貢獻的答案
#### 輸出
```cpp=30
cout<<ans;
```
輸出答案
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int m,ans=0;
string s;
unordered_set<string>st;
void findaim(string& tmp){
for(int i=1;i*2<=tmp.size();i++){
auto a=tmp.substr(0,i),aa=tmp.substr(tmp.size()-i,i);
if(a!=aa)continue;
else{
if(st.find(tmp.substr(i,tmp.size()-i-i))!=st.end())ans++;
}
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>m;
for(int i=0;i<m;i++){
cin>>s;
st.insert(s);
}
auto it=st.begin();
while(it!=st.end()){
string tmp=*it;
findaim(tmp);
it++;
}
cout<<ans;
}
```
## 第四題 牆上海報
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h084
### 解套
給一個大小為n的陣列代表牆壁高度與一大小為k的陣列代表海報寬度，
求最大整數mx使得所有牆壁高度大於mx的子序列長度能依順序完全對應到每個海報寬度
### 題目分析
這題有兩個主要的觀念點，分別是：
* 二分搜：h最大可以到$10^9$，因此解法的複雜度要嘛跟h無關要嘛是$O(logh)$，如果是$O(logh)$的話感覺應該是二分搜
* 貪心：這部分我認為算直觀，不需要特別想，就是在檢驗某個高度合不合要求時的處理方式，即由右往左掃，貪心地匹配可用牆壁與海報，最後看海報能不能放完
因此我們得到我們的解法，二分搜最高的高度h，並用貪心的方式檢查搜到的高度符不符合
如此時間複雜度$O(nlog(max(h_i))$
### 解題流程
輸入測資$→$用貪心為條件做二分搜$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,k,mx=0;
vector<int>wall,paper;
```
n,k與題述相同，mx存最大高度， wall、paper分別存牆壁高度與海報寬度
#### 檢驗函數
```cpp=5
bool check(int h){
vector<int>v;
int tmp=0;
for(int i=0;i<n;i++){
if(wall[i]>=h)tmp++;
else{
if(tmp!=0){
v.push_back(tmp);
tmp=0;
}
}
}
if(tmp!=0)v.push_back(tmp);
```
實作上，我們先遍歷所有牆壁高度，並將符合條件(大於等於指定高度)的區間長度存起來
例：牆壁$[6,3,7,5,1]$，$h=4$，那麼區間就是$[1,2]$，分別對應$[6]$與$[7,5]$
```cpp=18
int cnt=0;
for(int i=k-1;i>=0&&v.size();i--){
if(v.back()>=paper[i]){
v.back()-=paper[i];
cnt++;
if(v.back()==0)v.pop_back();
}
else{
while(v.back()<paper[i]&&v.size())v.pop_back();
i++;
}
}
```
因為題目要求照順序貼，所以我們由後往前遍歷(這樣就不用多存一個指標)
開一個變數cnt紀錄貼了幾個海報
若遇到可以貼的海報(牆壁寬度大於等於海報寬度)，就把cnt加一
並把能用的長度減掉海報寬度，若長度變為0就pop掉
若無法貼就把牆壁長度pop到能貼為止
```cpp=30
return cnt==k;
}
```
最後若cnt等於k代表海報貼得完，回傳true，不然回傳0
#### 輸入
```cpp=33
cin>>n>>k;
wall.assign(n,0);
paper.assign(k,0);
for(int i=0;i<n;i++){
cin>>wall[i];
mx=max(wall[i],mx);
}
for(int i=0;i<k;i++)cin>>paper[i];
```
同時記錄mx
#### 二分搜
```cpp=41
int l=1,r=mx,ans=0;
while(l<=r){
if(l==r){
ans=l;
break;
}
if(l+1==r){
if(check(r))ans=r;
else ans=l;
break;
}
int mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
```
對最高高度做二分搜，ans存答案
#### 輸出
```cpp=56
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,k,mx=0;
vector<int>wall,paper;
bool check(int h){
vector<int>v;
int tmp=0;
for(int i=0;i<n;i++){
if(wall[i]>=h)tmp++;
else{
if(tmp!=0){
v.push_back(tmp);
tmp=0;
}
}
}
if(tmp!=0)v.push_back(tmp);
int cnt=0;
for(int i=k-1;i>=0&&v.size();i--){
if(v.back()>=paper[i]){
v.back()-=paper[i];
cnt++;
if(v.back()==0)v.pop_back();
}
else{
while(v.back()<paper[i]&&v.size())v.pop_back();
i++;
}
}
return cnt==k;
}
int main(){
cin>>n>>k;
wall.assign(n,0);
paper.assign(k,0);
for(int i=0;i<n;i++){
cin>>wall[i];
mx=max(wall[i],mx);
}
for(int i=0;i<k;i++)cin>>paper[i];
int l=1,r=mx,ans=0;
while(l<=r){
if(l==r){
ans=l;
break;
}
if(l+1==r){
if(check(r))ans=r;
else ans=l;
break;
}
int mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
cout<<ans;
}
```
Sign in with Wallet
Connect another wallet