# APCS 2020年07月題解
## 第一題 購物車
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f579
### 解套
N/A
### 題目分析
直接按題目要求一次處理即可
對於每位客人，開兩個變數x與y紀錄商品a與b分別買了幾個，當讀到絕對值等於a或b時，
代表是對a或b做拿出或放入的動作，這時直接把x或y加上輸入值即可(正負號會被考慮到且拿出、放入剛好能抵銷)，最後看兩者有沒有都大於0就能判斷是否都有買，若有則把答案加一
時間複雜度$O(n×每位客人操作次數)$
### 解題流程
輸入$→$依序處理$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int a,b,n,inp,ans=0;
```
inp是輸入用的變數，ans存答案
#### 輸入
```cpp=5
cin>>a>>b>>n;
```
#### 處理每位客人
```cpp=6
while(n--){
int x=0,y=0;
while(cin>>inp&&inp){
if(abs(inp)==a)x+=inp;
if(abs(inp)==b)y+=inp;
}
if(x>0&&y>0)ans++;
}
```
先開x,y紀錄(第7行)，接著不斷輸入inp直到其等於0為止(第8行)
若絕對值等於a或b就加到x或y(第9、10行)，最後若x與y都大於0就更新答案
#### 輸出
```cpp=14
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a,b,n,inp,ans=0;
int main(){
cin>>a>>b>>n;
while(n--){
int x=0,y=0;
while(cin>>inp&&inp){
if(abs(inp)==a)x+=inp;
if(abs(inp)==b)y+=inp;
}
if(x>0&&y>0)ans++;
}
cout<<ans;
}
```
## 第二題 骰子
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f580
### 解套
N/A
### 題目分析
首先根據題目敘述，一開始骰子的狀態如下
| 上 | 下 | 左 | 右 | 前 | 後 |
| - | - | - | - | - | - |
| 1 | 6 | 5 | 2 | 4 | 3 |
然後**向前旋轉**就是前→下、下→後、後→上、上→前
**向右旋轉**就是右→下、下→左、左→上、上→右
那為了方便我寫了一個dice[結構](https://oi-wiki.org/lang/struct/)紀錄骰子的上下左右前後，再開一個dice陣列紀錄各骰子狀況
最後按題目要求操作即可
時間複雜度$O(n)$
### 解題流程
輸入$→$操作$→$輸出
### 解題過程
#### 變數、結構宣告
```cpp=3
int n,m,a,b;
struct dice{
int up,down,left,right,ffront,bback;
dice():up(1),down(6),left(5),right(2),ffront(4),bback(3){}
};
dice arr[20+10];
```
n,m,a,b使題述相同
因為front,back是C++內建函式名稱，所以改成ffront,bback避免撞名(在這題沒有影響)
第6行是dice的初始化
#### 輸入
```cpp=10
cin>>n>>m;
while(m--){
cin>>a>>b;
```
#### 操作—交換
```cpp=13
if(a>0&&b>0)swap(arr[a],arr[b]);
```
若a,b都大於零代表交換操作，直接swap就好
#### 操作—向前旋轉
```cpp=14
else if(b==-1){
int tmp=arr[a].up;
arr[a].up=arr[a].bback;
arr[a].bback=arr[a].down;
arr[a].down=arr[a].ffront;
arr[a].ffront=tmp;
}
```
依照前述改變值
#### 操作—向右旋轉
```cpp=21
else{
int tmp=arr[a].up;
arr[a].up=arr[a].left;
arr[a].left=arr[a].down;
arr[a].down=arr[a].right;
arr[a].right=tmp;
}
```
依照前述改變值
#### 輸出
```cpp=29
for(int i=1;i<=n;i++)cout<<arr[i].up<<" ";
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
struct dice{
int up,down,left,right,ffront,bback;
dice() : up(1),down(6),left(5),right(2),ffront(4),bback(3) {}
};
dice arr[20+10];
int main(){
cin>>n>>m;
while(m--){
cin>>a>>b;
if(a>0&&b>0)swap(arr[a],arr[b]);
else if(b==-1){
int tmp=arr[a].up;
arr[a].up=arr[a].bback;
arr[a].bback=arr[a].down;
arr[a].down=arr[a].ffront;
arr[a].ffront=tmp;
}
else{
int tmp=arr[a].up;
arr[a].up=arr[a].left;
arr[a].left=arr[a].down;
arr[a].down=arr[a].right;
arr[a].right=tmp;
}
}
for(int i=1;i<=n;i++)cout<<arr[i].up<<" ";
}
```
## 第三題 圓環出口
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f581
### 解套
N/A
### 題目分析
一開始想說直接硬做，也就是一個一個跑直到分數湊滿，但寫完之後估一下複雜度就發現不會過...
($O(nm)=4×10^9>10^8$)
於是就把腦筋動到也是搜尋但比較快的二分搜上去了～~~通靈~~
首先會發現如果只單獨知道每一個房間的分數會很難搜尋，
但如果改成存前綴和就能對累積的分數進行二分搜
具體操作上開一個變數id紀錄當前的位置，而要求獲得$x$分其實就是要求累積分數達到「當前房間累積分數+$x$分」，當然還要處理溢出情況(這時候就減掉所有房間的分數從頭開始)
因此我們只要維護id，並每次透過二分搜前綴和找到下一個位置，操作$m$次就能得到答案了
時間複雜度$O(mlogn)$
### 解題流程
輸入$→$二分搜$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,a;
vector<int>v;
```
n,m同題述，v存房間分數前綴和，a只是輸入用
#### 輸入、v初始化
```cpp=6
cin>>n>>m;
v.assign(n,0);
for(int i=0;i<n;i++){
cin>>a;
v[i]=a+(i==0?0:v[i-1]);
}
```
第10行存前綴和
#### 尋找下一個房間
```cpp=12
int id=0;
for(int i=0;i<m;i++){
cin>>a;
int tgt=a+(id==0?0:v[id-1]);
if(tgt>v[n-1])tgt-=v[n-1];
id=(lower_bound(v.begin(),v.end(),tgt)-v.begin()+1)%n;
}
```
一開始在0號房間(第12行)
接著輸入目標分數(第14行)，並將之從「加多少分」轉為「累積分數多少分」(第15行)
其中在轉為累積多少分的時候要加的是v[id-1]，所以要注意id=0時不要加
那這樣會不會少加到呢?其實不會，因為id=0只有在一開始和因為溢出而回到最開始時兩種狀況，而這兩種狀況都還沒算0號房間的分數，所以不會有問題
加完之後如果超出總分的話就扣掉總分代表又繞了一圈(第16行)
(題目保證要的分數不超過總分，所以不用擔心要多減)
(這裡不能用tgt%=v[n-1]，因為tgt==v[n-1]時不能減)
最後用lower_bound找出達到該累積分數最少需要的房間編號，並+1後%n跳到下一個房間(第17行)
#### 輸出
```cpp=20
cout<<id;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,a;
vector<int>v;
int main(){
cin>>n>>m;
v.assign(n,0);
for(int i=0;i<n;i++){
cin>>a;
v[i]=a+(i==0?0:v[i-1]);
}
int id=0;
for(int i=0;i<m;i++){
cin>>a;
int tgt=a+(id==0?0:v[id-1]);
if(tgt>v[n-1])tgt-=v[n-1];
id=(lower_bound(v.begin(),v.end(),tgt)-v.begin()+1)%n;
}
cout<<id;
}
```
## 第四題 病毒演化
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f582
### 解套
求所有字串與其父字串的漢明距離(相異字元數)總和
### 題目分析
首先我們會發現每一個位置的距離會是互相獨立的，也就是說我們可以分開處理字串的每一個位置，不用擔心結果互相影響，藉此降低題目的難度
那麼對於每一個位置，要怎麼計算最小距離呢？
我們可以~~透過通靈~~發現因為是樹狀結構，感覺會跟dfs或bfs有關，不過因為有父子關係的節點比較有直接關聯，所以用dfs來算
具體的做法如下
我們定義$dp[i][j][k]$為第$i$個字串第$j$個位置是$k$的時候，由下往上到他累積的最小距離
(@,A,U,G,C轉成0,1,2,3,4)，其中$dp[i][j][0]$同時也會代表最理想情況下的值
而我們對每一個j從根節點往下遍歷
首先對於葉節點來說，如果他是@，那他的五個值都會是0；
不然就是自己原本的字元與@會是0，其他無限大
而對於非葉節點來說，首先要先把子節點都遍歷一遍，
接著看他自己是甚麼字元
如果是@話那就枚舉A,U,G,C四種狀況，用子節點計算看哪種狀況值會最小，並把@的狀況設為四者的最小值
不然的話就把自己字元除外設成無限大，自己的字元用子節點計算看哪種狀況值會最小，並把@設為自身字元的值
(計算方式後面用程式碼解釋)
每個位置處理完後讓答案加上$dp[root][j][0]$，就能算出最後答案
(即使字元不是@，計算過程也會讓@是最小距離，所以直接加他就好)
時間複雜度$O(nm)$
### 解題流程
輸入、初始化$→$遍歷位置、運算$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,a,b,root,ans=0,dp[1000+10][80+10][5]={};
string s[1000+10];
vector<int>v[1000+10];
unordered_map<char,int>mp={{'@',0},{'A',1},{'U',2},{'G',3},{'C',4}};
```
n,m同題述，a,b是題目中的i,j，s存字串，v存圖，root存根，ans存答案，dp如前述，mp是為了方便轉換字元與數字
dp一開始預設都是0，有助後面操作
#### 操作函式
**葉節點**
```cpp=8
if(v[cur].size()==0){
if(s[cur][pos]=='@')return;
else{
for(int i=0;i<=4;i++)dp[cur][pos][i]=INT_MAX;
dp[cur][pos][0]=dp[cur][pos][mp[s[cur][pos]]]=0;
return;
}
}
```
沒有子節點代表是葉節點(第8行)
若本身是@就直接回傳(都是0)
不然把本身字元與最佳情況設成0，其他設無限大
**非葉節點**
```cpp=16
else{
for(int i:v[cur])func(i,pos);
int c=mp[s[cur][pos]];
if(c!=0){
for(int i=0;i<=4;i++)dp[cur][pos][i]=INT_MAX;
dp[cur][pos][c]=0;
for(int i:v[cur])dp[cur][pos][c]+=min(dp[i][pos][c],dp[i][pos][0]+1);
dp[cur][pos][0]=dp[cur][pos][c];
return;
}
else{
for(int i=1;i<=4;i++){
for(int j:v[cur])dp[cur][pos][i]+=min(dp[j][pos][i],dp[j][pos][0]+1);
}
dp[cur][pos][0]=min({dp[cur][pos][1],dp[cur][pos][2],dp[cur][pos][3],dp[cur][pos][4]});
return;
}
}
```
先向下遞迴，把子節點處理完(第17行)
然後為了方便設c為字元轉成的數字
分兩種狀況討論
1. **字元是@**
分別處理A,T,C,G四種狀況(用子節點更新數值)，然後把最佳狀況設為四者的最小值
2. **其他字元**
將自身除外設為無限大，用子節點更新自身的數值，然後把最佳狀況設為自身的數值
#### 輸入、存圖
```cpp=36
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a>>b;
cin>>s[a];
if(a==b)root=a;
else v[b].push_back(a);
}
```
第40行判斷是否為根節點
#### 依序處理每個位置
```cpp=43
for(int i=0;i<m;i++){
func(root,i);
ans+=dp[root][i][0];
}
```
先處理每個位置(第44行)
再把答案加上跟節點的最好可能(第41行)
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,root,ans=0,dp[1000+10][80+10][5]={};
string s[1000+10];
vector<int>v[1000+10];
unordered_map<char,int>mp={{'@',0},{'A',1},{'U',2},{'G',3},{'C',4}};
void func(int cur,int pos){
if(v[cur].size()==0){
if(s[cur][pos]=='@')return;
else{
for(int i=0;i<=4;i++)dp[cur][pos][i]=INT_MAX;
dp[cur][pos][0]=dp[cur][pos][mp[s[cur][pos]]]=0;
return;
}
}
else{
for(int i:v[cur])func(i,pos);
int c=mp[s[cur][pos]];
if(c!=0){
for(int i=0;i<=4;i++)dp[cur][pos][i]=INT_MAX;
dp[cur][pos][c]=0;
for(int i:v[cur])dp[cur][pos][c]+=min(dp[i][pos][c],dp[i][pos][0]+1);
dp[cur][pos][0]=dp[cur][pos][c];
return;
}
else{
for(int i=1;i<=4;i++){
for(int j:v[cur])dp[cur][pos][i]+=min(dp[j][pos][i],dp[j][pos][0]+1);
}
dp[cur][pos][0]=min({dp[cur][pos][1],dp[cur][pos][2],dp[cur][pos][3],dp[cur][pos][4]});
return;
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a>>b;
cin>>s[a];
if(a==b)root=a;
else v[b].push_back(a);
}
for(int i=0;i<m;i++){
func(root,i);
ans+=dp[root][i][0];
}
cout<<ans;
}
```
Sign in with Wallet
Connect another wallet