# APCS 2020年01月題解
## 第一題 猜拳
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h026
### 解套
N/A
### 題目分析
直接按照題述進行相關操作
先輸入所有妹妹準備出的拳，接著從頭遍歷
每一輪先輸出哥哥要出的拳，接著判斷勝負，如果分出勝負就輸出並直接return 0結束程式
否則就照題述決定下一輪哥哥要出的拳，不過要注意如果是第一輪的話因為妹妹不可能"連續兩輪出一樣的拳"，所以不能判斷這一條(陣列會吃到邊界外)
最後如果能把所有迴圈跑完(沒有被結束)代表平手，輸出相關內容
時間複雜度$O(N)$
### 解題流程
輸入$→$遍歷、輸出
### 解題過程
#### 變數宣告
```cpp=3
int f,n,y[10];
```
意義與題述同
#### 輸入
```cpp=5
cin>>f>>n;
for(int i=0;i<n;i++)cin>>y[i];
```
#### 迴圈遍歷
```cpp=7
for(int i=0;i<n;i++){
cout<<f<<" ";
if(f==0&&y[i]==2||f==2&&y[i]==5||f==5&&y[i]==0){
cout<<": Won at round "<<i+1;
return 0;
}
else if(y[i]==0&&f==2||y[i]==2&&f==5||y[i]==5&&f==0){
cout<<": Lost at round "<<i+1;
return 0;
}
else{
if(i>=1&&y[i-1]==y[i]){
if(y[i]==0)f=5;
else if(y[i]==2)f=0;
else f=2;
}
else f=y[i];
}
}
```
先輸出要出的拳(第8行)
接著判斷有沒有贏(第9-12行)以及有沒有輸(第13-16行)
其中第12、15行直接return 0結束main函式避免跑到後面的平手部分
最後按照規則決定下一輪要出的拳(第17-24行)
#### 平手的輸出
```cpp=26
cout<<": Drew at round "<<n;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int f,n,y[10];
int main(){
cin>>f>>n;
for(int i=0;i<n;i++)cin>>y[i];
for(int i=0;i<n;i++){
cout<<f<<" ";
if(f==0&&y[i]==2||f==2&&y[i]==5||f==5&&y[i]==0){
cout<<": Won at round "<<i+1;
return 0;
}
else if(y[i]==0&&f==2||y[i]==2&&f==5||y[i]==5&&f==0){
cout<<": Lost at round "<<i+1;
return 0;
}
else{
if(i>=1&&y[i-1]==y[i]){
if(y[i]==0)f=5;
else if(y[i]==2)f=0;
else f=2;
}
else f=y[i];
}
}
cout<<": Drew at round "<<n;
}
```
## 第二題 矩陣總和
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h027
### 解套
定義兩相同小矩陣的「距離」為相同位置但數字不同的位置數量
求一大矩陣所有子矩陣中與小矩陣距離不超過$r$的子矩陣個數，以及其中總和與小矩陣相差最小的值
(若無輸出-1)
### 題目分析
因為矩陣大小最多只到$10×100$，所以可以考慮暴力一點的作法
直接遍歷大矩陣中所有與小矩陣大小相同的子矩陣，計算距離與總和即可
實作上我是枚舉子矩陣的左上角(這樣就能透過小矩陣長寬推得邊界)
並額外寫一個計算距離與總和的函式calc，並用calc回傳的值更新答案
時間複雜度$O(nmst)$
### 解題流程
輸入$→$枚舉子矩陣、計算答案$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int s,t,n,m,r;
int small[10][100],big[10][100],ssum=0,cnt=0,ans=INT_MAX;
```
small存小矩陣，big存大矩陣，ssum存小矩陣元素和，cnt存要多少子矩陣距離不超過$r$，ans存最小距離差，其餘與題述同
#### calc函式
```cpp=5
pair<int,int> calc(int x1,int y1){
int cnt=0,ans=0;
for(int i=x1;i<=x1+s-1;i++)for(int j=y1;j<=y1+t-1;j++){
ans+=big[i][j];
if(big[i][j]!=small[i-x1][j-y1])cnt++;
}
return {cnt,ans};
}
```
參數x1,x2是子矩陣的左上角座標(第5行)
一開始宣告cnt,ans存距離與元素和(第6行)
接者遍歷子矩陣，計算cnt和ans(第7-10行)
最後以pair形式回傳cnt與ans(第11行)
#### 輸入
```cpp=14
cin>>s>>t>>n>>m>>r;
for(int i=0;i<s;i++)for(int j=0;j<t;j++){
cin>>small[i][j];
ssum+=small[i][j];
}
for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>big[i][j];
```
第17行算小矩陣元素和
#### 枚舉子矩陣
```cpp=20
for(int i=0;i<=n-s;i++)for(int j=0;j<=m-t;j++){
auto num=calc(i,j);
if(num.first<=r){
cnt++;
ans=min(abs(num.second-ssum),ans);
}
}
```
先用num存calc函式計算的值(第21行)
接著判斷距離是否不超過$r$，若是就更新cnt與ans(第22-25行)
#### 輸出
```cpp=27
cout<<cnt<<"\n";
if(cnt!=0)cout<<ans;
else cout<<-1;
```
輸出cnt與ans，其中若沒有符合條件的子矩陣就不輸出ans改輸出-1
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int s,t,n,m,r;
int small[10][100],big[10][100],ssum=0,cnt=0,ans=INT_MAX;
pair<int,int> calc(int x1,int y1){
int cnt=0,ans=0;
for(int i=x1;i<=x1+s-1;i++)for(int j=y1;j<=y1+t-1;j++){
ans+=big[i][j];
if(big[i][j]!=small[i-x1][j-y1])cnt++;
}
return {cnt,ans};
}
int main(){
cin>>s>>t>>n>>m>>r;
for(int i=0;i<s;i++)for(int j=0;j<t;j++){
cin>>small[i][j];
ssum+=small[i][j];
}
for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>big[i][j];
for(int i=0;i<=n-s;i++)for(int j=0;j<=m-t;j++){
auto num=calc(i,j);
if(num.first<=r){
cnt++;
ans=min(abs(num.second-ssum),ans);
}
}
cout<<cnt<<"\n";
if(cnt!=0)cout<<ans;
else cout<<-1;
}
```
## 第三題 砍樹
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h028
### 解套
N/A
### 題目分析
首先要先了解到一個重要的性質
> 無論砍樹的順序為何，最後能砍除的樹木是相同的
這個性質讓我們不必花時間思考「能砍掉最多樹木的方法」之類的，
只要最後有把能砍的樹木都砍完就行了
至於為什麼會這樣呢？因為題目有寫
知道順序不影響後，接下來就只要把該砍的樹都砍完就行了
這題的操作主要可以分成兩種：
判斷一棵樹可不可以砍，以及找到某棵樹的前一棵以及後一棵樹
判斷一棵樹能不能砍的部分比較簡單，只要一開始存好每棵樹的位置與高度，找到前後的樹再算一下就好了，所以本題的重點還是在於找到前後的樹
很明顯地一棵樹的前後會因為有樹被砍掉而有所改變，所以不能直接用原始輸入的順序判斷
我原本的想法是用set維護現存的樹已達到$O(logn)$查詢、刪除，在一年前也過了，但最近重寫發現時間限制被壓緊，所以只好想新的解法
後來發現可以直接用陣列紀錄一棵樹前後樹的編號，這樣就能$O(1)$查詢，
而且刪除的操作也算簡單，只要把「前一棵樹的下一棵樹」改成「自己的下一棵樹」、「下一棵樹的前一棵樹」改成「自己的前一棵樹」就能解決，如此就能避免真的把樹刪掉，節省時間
**前：**
| 樹編號 | 前一棵樹 | 後一棵樹 |
| -------- | -------- | -------- |
| 2 | 1 | 3 |
| 3 | 2 | 4 |
| 4 | 3 | 5 |
**後：**
| 樹編號 | 前一棵樹 | 後一棵樹 |
| -------- | -------- | -------- |
| 2 | 1 | 4 |
| 3 | 2 | 4 |
| 4 | 2 | 5 |
實作上開一個二維陣列$loc[N][2]$，其中$loc[i][0]$、$loc[i][1]$分別代表編號為$i$的樹前一棵與後一棵的編號
於是就得到我們的解法：從左往右掃依次判斷每棵樹能不能砍(用$loc$加速)，如果砍成功就更新答案、$loc$，並**跳回到前一棵樹**，因為如果這棵樹砍了，空間就變大了，可能讓前一棵樹變得可以砍
最終複雜度應該是$O(n)$，因為每顆樹最多砍掉一次，且就總數來看頂多處理$2n$次
### 解題流程
輸入$→$初始化$→$砍樹(遍歷+回頭檢查)$→$輸出
### 解題過程
#### define
```cpp=2
#define pos first
#define h second
```
依照存的東西更改命名
#### 變數宣告
```cpp=5
int n,l,cnt=0,mx=0,loc[100000+10][2];
pair<int,int>arr[100000+10];
```
cnt砍了幾棵樹，mx存最高的能砍的樹，arr存每棵樹的位置與高度，loc同前述，n,l同題述
#### 輸入優化
```cpp=8
ios::sync_with_stdio(0);
cin.tie(0);
```
不加也會過
#### 輸入
```cpp=10
cin>>n>>l;
for(int i=1;i<=n;i++)cin>>arr[i].pos;
for(int i=1;i<=n;i++)cin>>arr[i].h;
```
#### 初始化
```cpp=13
arr[0]={1,0};
arr[n+1]={l,0};
for(int i=0;i<=n+1;i++){
loc[i][0]=i-1;
loc[i][1]=i+1;
}
```
為了方便操作在arr前後加上邊界(這題設$0～l$或$1～l$都會過)
#### 砍樹
```cpp=19
int it=1;
while(1){
if(arr[it].pos-arr[it].h>=arr[loc[it][0]].pos||arr[it].pos+arr[it].h<=arr[loc[it][1]].pos){
cnt++;
mx=max(mx,arr[it].h);
loc[loc[it][0]][1]=loc[it][1];
loc[loc[it][1]][0]=loc[it][0];
if(loc[it][0]!=0)it=loc[it][0];
else it=loc[it][1];
}
else it=loc[it][1];
if(it>n)break;
}
```
一開始初始化位置為1(第19行)
接著不斷重複以下操作：
先判斷一棵樹能不能砍(第21行)
如果可以的話就更新答案(第22.23行)，然後更新前後樹木的位置關係，最後更新it
需要注意的是如果it已經是第一棵樹了就不用往前，不然都要往前推一棵
如果不行就直接跳到下一棵樹
最後判斷如果已經到底了就終止迴圈
#### 輸出
```cpp=32
cout<<cnt<<"\n"<<mx;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define pos first
#define h second
using namespace std;
int n,l,cnt=0,mx=0,loc[100000+10][2];
pair<int,int>arr[100000+10];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>l;
for(int i=1;i<=n;i++)cin>>arr[i].pos;
for(int i=1;i<=n;i++)cin>>arr[i].h;
arr[0]={1,0};
arr[n+1]={l,0};
for(int i=0;i<=n+1;i++){
loc[i][0]=i-1;
loc[i][1]=i+1;
}
int it=1;
while(1){
if(arr[it].pos-arr[it].h>=arr[loc[it][0]].pos||arr[it].pos+arr[it].h<=arr[loc[it][1]].pos){
cnt++;
mx=max(mx,arr[it].h);
loc[loc[it][0]][1]=loc[it][1];
loc[loc[it][1]][0]=loc[it][0];
if(loc[it][0]!=0)it=loc[it][0];
else it=loc[it][1];
}
else it=loc[it][1];
if(it>n)break;
}
cout<<cnt<<"\n"<<mx;
}
```
## 第四題 貨物分配
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=h029
https://zerojudge.tw/ShowProblem?problemid=f163
(f163的測資範圍較大，要開多一點記憶體，接下來開的大小是根據h029，要丟f163麻煩自行調整)
### 解套
構造一個二元樹狀結構，從根往下加值，每次把數值加到值比較小的子樹上，
並輸出最後到達的葉節點編號
### 題目分析
說實話我不太確定這題究竟想要考什麼？
感覺應該是想考圖論中的二元樹，不過好像又只有用到存圖跟存點權的技巧，所以...
我的做法是用叫arr的pair陣列存每個節點的左右節點，並用叫w的int陣列存每個節點的重量
初始化重量時由下往上，若是貨艙就直接回傳原本的重量，否則把自身重量設為左右兩節點的值加起來再回傳
每次放貨物就從根節點往下遍歷，把重量加到比較輕的子樹上並更新自身重量，重覆遞迴到遇到葉節點為止(貨箱)，最後輸出到達的貨箱
為此需要兩個函式，分別是初始化重量的init函式以及放置貨物的put函式
另外題目有保證入口編號一定是1，所以不須判斷
時間複雜度$O(mn)$(如果是一條鍊的話)
### 解題流程
輸入、存圖$→$初始化二元樹$→$放貨物、輸出
### 解題過程
#### define
```cpp=2
#define L first
#define R second
```
讓自己寫起來比較順
#### 變數宣告
```cpp=5
int n,m,w[200000],goods[100],p,s,t;
pair<int,int>arr[100000];
```
n,m,p,s,t同題述，w,arr如前述，goods存每個貨物重量
#### init函式
```cpp=7
int init(int id){
if(id>=n)return w[id];
w[id]=init(arr[id].L)+init(arr[id].R);
return w[id];
}
```
若編號大於n代表是貨艙，直接回傳重量(第8行)
不然把重量設為左右節點的重量和(要先各自初始化完)再回傳自身重量(第9-10行)
#### put函式
```cpp=12
void put(int good,int id){
w[id]+=good;
if(id>=n){
cout<<id<<" ";
return;
}
if(w[arr[id].L]<=w[arr[id].R])put(good,arr[id].L);
else put(good,arr[id].R);
return;
}
```
先更新自身重量(第13行)
若已抵達貨倉就直接輸出並結束(第14-17行)
不然就依照左右重量決定貨物放到哪裡，並回傳(第18-20行)
#### 輸入優化
```cpp=23
ios::sync_with_stdio(0);
cin.tie(0);
```
不加也會過
#### 輸入、存圖
```cpp=25
cin>>n>>m;
for(int i=n;i<2*n;i++)cin>>w[i];
for(int i=0;i<m;i++)cin>>goods[i];
for(int i=1;i<n;i++){
cin>>p>>s>>t;
arr[p]={s,t};
}
```
#### 初始化
```cpp=32
int a=init(1);
```
因為是int函式所以還是要把值存到某個地方去
#### 放貨物
```cpp=33
for(int i=0;i<m;i++)put(goods[i],1);
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define L first
#define R second
using namespace std;
int n,m,w[200000],goods[100],p,s,t;
pair<int,int>arr[100000];
int init(int id){
if(id>=n)return w[id];
w[id]=init(arr[id].L)+init(arr[id].R);
return w[id];
}
void put(int good,int id){
w[id]+=good;
if(id>=n){
cout<<id<<" ";
return;
}
if(w[arr[id].L]<=w[arr[id].R])put(good,arr[id].L);
else put(good,arr[id].R);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=n;i<2*n;i++)cin>>w[i];
for(int i=0;i<m;i++)cin>>goods[i];
for(int i=1;i<n;i++){
cin>>p>>s>>t;
arr[p]={s,t};
}
int a=init(1);
for(int i=0;i<m;i++)put(goods[i],1);
}
```
Sign in with Wallet
Connect another wallet