# APCS 2022年10月題解
## 第一題 巴士站牌
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=i428
### 解套
給定一數字n，接下來有n行，每行由兩個數字$x_i$、$y_i$組成，
求相鄰行$|x_i-x_j|+|y_i-y_j|$最大值與最小值
即求$\max_{0\le i\le n-1}(|x_{i+1}-x_i|+|y_{i+1}-y_i|)$與$\min_{0\le i\le n-1}(|x_{i+1}-x_i|+|y_{i+1}-y_i|)$
### 題目分析
最簡單的方式是用陣列存取每個站牌的位置，再從頭遍歷，計算最大值與最小值，
這樣時間複雜度$O(n)$
### 解題流程
讀入測資$→$從頭一次遍歷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,x[100],y[100],mx=INT_MIN,mn=INT_MAX;
```
#### 讀入測資
```cpp=5
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
```
#### 一次遍歷，更新最大值與最小值
```cpp=9
for(int i=0;i<n-1;i++){
mx=max(mx,abs(x[i]-x[i+1])+abs(y[i]-y[i+1]));
mn=min(mn,abs(x[i]-x[i+1])+abs(y[i]-y[i+1]));
}
```
#### 輸出
```cpp=13
cout<<mx<<" "<<mn;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,x[100],y[100],mx=INT_MIN,mn=INT_MAX;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
for(int i=0;i<n-1;i++){
mx=max(mx,abs(x[i]-x[i+1])+abs(y[i]-y[i+1]));
mn=min(mn,abs(x[i]-x[i+1])+abs(y[i]-y[i+1]));
}
cout<<mx<<" "<<mn;
}
```
## 第二題 運貨站
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=j123
### 解套
這題題目蠻直觀的，基本上就是一個從左到右的俄羅斯方塊，
給版面的長與寬 $R$ 和 $C$ 以及方塊數 $n$ ，並給 $n$ 個方塊的種類與最高點與上方的距離
求放完所有方塊還有幾個空格，然後有幾塊放不下
### 題目分析
這題可說是經典的APCS第二題，
測資範圍不大，不太需要考慮複雜度問題。但實作很複雜，一不小心就會丟分
需要做的就是好好分析五種方塊要怎麼放，接下來就是直接模擬
(有幾個空格最後一次掃就好了，當然也能邊做邊紀錄)，如此時間複雜度$O(N+RC)$
另外題目最後一行寫說
> 保證輸入內貨物距離倉庫頂部的高度不會讓貨物底部低於地面，並且不會有任何貨物卡在倉庫門口的情形。
所以不用擔心這部分的case(一開始沒看到又多寫了好幾行code)
### 解題流程
依序讀入測資$→$一一處理$→$輸出
### 解題過程
#### 變數宣告
``` cpp=3
int r,c,n,h,no=0;
bool arr[30][50]={};
char inp;
```
開一個布林陣列 $arr$ 存該格是否有貨物
輸入則用 $inp$ 和 $h$ 存貨物種類與高度
另位開一個$no$存被丟棄的貨物數量
#### 方塊處理
接下來分析各個方塊要如何處理
> B方塊
>
``` cpp=19
else if(inp=='B'){
int st=-1;
for(int i=c-1;i>=2;i--){
if(arr[h][i]==0&&arr[h][i-1]==0&&arr[h][i-2]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h][st-1]=arr[h][st-2]=1;
}
```
B方塊感覺最簡單，所以先從它下手
只需要一直往內推，直到到底或碰到其他東西為止
實作上我們開一個變數$st$，預設值為$-1$，紀錄最右側格子的橫軸座標位置
並從最右側不斷減少$st$直到不能減少為止(方塊寬度減一)，最後$st$就是最終位置(若為$-1$代表會被淘汰)
因為格數只有三格所以全部列出來判斷一次就好(第22行)
其中第21行用i>=2是因為左右寬度三格，因此最右的一格至少要在2(也就是3-1)
---
有了B方塊的規律後，剩下四個基本上大同小異，只需更改橫坐標限制與判斷的格子數量、位置
> A方塊
```cpp=10
if(inp=='A'){
int st=-1;
for(int i=c-1;i>=0;i--){
if(arr[h][i]==0&&arr[h+1][i]==0&&arr[h+2][i]==0&&arr[h+3][i]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h+1][st]=arr[h+2][st]=arr[h+3][st]=1;
}
```
> C方塊
```cpp=28
else if(inp=='C'){
int st=-1;
for(int i=c-1;i>=1;i--){
if(arr[h][i]==0&&arr[h][i-1]==0&&arr[h+1][i]==0&&arr[h+1][i-1]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h][st-1]=arr[h+1][st]=arr[h+1][st-1]=1;
}
```
> D方塊
```cpp=37
else if(inp=='D'){
int st=-1;
for(int i=c-1;i>=2;i--){
if(arr[h][i]==0&&arr[h+1][i]==0&&arr[h+1][i-1]==0&&arr[h+1][i-2]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h+1][st]=arr[h+1][st-1]=arr[h+1][st-2]=1;
}
```
> E方塊
```cpp=46
else{
int st=-1;
for(int i=c-1;i>=1;i--){
if(arr[h][i]==0&&arr[h+1][i]==0&&arr[h+1][i-1]==0&&arr[h+2][i]==0&&arr[h+2][i-1]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h+1][st]=arr[h+1][st-1]=arr[h+2][st]=arr[h+2][st-1]=1;
}
```
#### 輸出
```cpp=56
int cnt=0;
for(int i=0;i<r;i++)for(int j=0;j<c;j++)cnt+=!arr[i][j];//等同於if(arr[i][j]==0)cnt++
cout<<cnt<<" "<<no;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int r,c,n,h,no=0;
bool arr[30][50]={};
char inp;
int main(){
cin>>r>>c>>n;
for(int t=0;t<n;t++){
cin>>inp>>h;
if(inp=='A'){
int st=-1;
for(int i=c-1;i>=0;i--){
if(arr[h][i]==0&&arr[h+1][i]==0&&arr[h+2][i]==0&&arr[h+3][i]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h+1][st]=arr[h+2][st]=arr[h+3][st]=1;
}
else if(inp=='B'){
int st=-1;
for(int i=c-1;i>=2;i--){
if(arr[h][i]==0&&arr[h][i-1]==0&&arr[h][i-2]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h][st-1]=arr[h][st-2]=1;
}
else if(inp=='C'){
int st=-1;
for(int i=c-1;i>=1;i--){
if(arr[h][i]==0&&arr[h][i-1]==0&&arr[h+1][i]==0&&arr[h+1][i-1]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h][st-1]=arr[h+1][st]=arr[h+1][st-1]=1;
}
else if(inp=='D'){
int st=-1;
for(int i=c-1;i>=2;i--){
if(arr[h][i]==0&&arr[h+1][i]==0&&arr[h+1][i-1]==0&&arr[h+1][i-2]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h+1][st]=arr[h+1][st-1]=arr[h+1][st-2]=1;
}
else{
int st=-1;
for(int i=c-1;i>=1;i--){
if(arr[h][i]==0&&arr[h+1][i]==0&&arr[h+1][i-1]==0&&arr[h+2][i]==0&&arr[h+2][i-1]==0)st=i;
else break;
}
if(st==-1)no++;
else arr[h][st]=arr[h+1][st]=arr[h+1][st-1]=arr[h+2][st]=arr[h+2][st-1]=1;
}
}
int cnt=0;
for(int i=0;i<r;i++)for(int j=0;j<c;j++)cnt+=!arr[i][j];
cout<<cnt<<" "<<no;
}
```
## 第三題 石窟探險
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=j124
### 解套
給定一樹的前序遍歷，其若節點編號是偶數則有兩個分支，否則有三個分支，且死路編號為0
求所有相鄰節點編號差的絕對值總和
### 題目分析
原本想要先把整個數列存下來，再找規律遍歷，後來發現其實可以用遞迴的方式解
定義遞迴函數$dfs$，先讀入編號$n$，並分三種狀況討論。若
1. $n$為$0$
直接回傳$0$
2. $n$為偶數
遞迴地求左節點與右節點的值，即令$l=dfs()$，$r=dfs()$
並若$l\neq0$則將答案加上$|n-l|$，$r\neq0$則將答案加上$|n-r|$
最後回傳$n$，即節點本身的值
3. $n$為奇數
遞迴地求左節點、中節點與右節點的值，即令$l=dfs()$，$m=dfs()$，$r=dfs()$
並若$l\neq0$則將答案加上$|n-l|$，$m\neq0$則將答案加上$|n-m|$、$r\neq0$則將答案加上$|n-r|$
最後回傳$n$，即節點本身的值
如此只要在$main$函式一開始呼叫$dfs$，最後輸出答案即可
如此時間複雜度$O(n)$，因為每個節點都遍歷一遍
### 解題流程
呼叫$dfs$函式$→$輸出答案
### 解題過程
#### 變數宣告
```cpp=3
long long ans=0;
```
題目有說答案可能超過$int$範圍，所以開$long\ \ long$
#### 遞迴函式宣告
```cpp=4
int dfs(){
int n;
cin>>n;
if(n==0)return 0;
if(n%2==0){
int l=dfs(),r=dfs();
if(l)ans+=abs(n-l);
if(r)ans+=abs(n-r);
}
else{
int l=dfs(),m=dfs(),r=dfs();
if(l)ans+=abs(n-l);//if(l)為if(l!=0)的簡寫
if(m)ans+=abs(n-m);
if(r)ans+=abs(n-r);
}
return n;
}
```
#### main函式
```cpp=22
int tmp=dfs();
cout<<ans;
```
其中需要注意的是因為$dfs$是$int$函式，所以需要把它回傳的值存到一個變數內
(不這樣做不一定會出事，但寫一下比較好)
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
long long ans=0;
int dfs(){
int n;
cin>>n;
if(n==0)return 0;
if(n%2==0){
int l=dfs(),r=dfs();
if(l)ans+=abs(n-l);
if(r)ans+=abs(n-r);
}
else{
int l=dfs(),m=dfs(),r=dfs();
if(l)ans+=abs(n-l);
if(m)ans+=abs(n-m);
if(r)ans+=abs(n-r);
}
return n;
}
int main(){
int tmp=dfs();
cout<<ans;
}
```
## 第四題 蓋步道
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=j125
### 解套
給一個$n×n$陣列，要找從左上角$(0,0)$走到右下角$(n-1,n-1)$的最短路徑，
但路徑中相鄰兩格值(高度差)不能超過一數字$limit$
求有最短路徑存在的前提下$limit$的最小值，與其所對應的最短路徑長度
### 題目分析
很明顯地這是一道圖論題。
這時我們先將問題簡化：**如果只是求最短路呢？**
因為圖沒有邊權，所以只需要使用基礎的$bfs$即可
這一部分解決後，再考慮到高度差的問題
如果是給定高度差，問題依然非常容易，只是在$bfs$加上判斷能不能走的條件而已
那回到原題目，要怎麼找到最小的高度差限制呢?
當沒有想法時，有一種方法是**分析複雜度**
$bfs$的複雜度是$O(V+E)$，其中$V$是點的數目，$E$是邊的數目
把題目的數值帶進去可以得到大約$300000(300*300+299*300*2)$
而考慮到電腦一秒大概只能跑$10^8$次運算，我們只能分配約$10^3$次運算給尋找高度差
但題目高度最大到$10^6$，很明顯不能一個一個試，於是我們就想到**二分搜**
如此就能把所需次數壓到大約20次$(log_{2}10^6)$
因此我們就得出了最後的解法：
對最小高度差做二分搜，並利用$bfs$判斷該高度差能否從左上角走到右下角
這樣總時間複雜度$O(n^2log(h))$
這種技巧被稱作對答案二分搜，常用在無法求出答案，只能找出一個答案合不合的情況
### 解題流程
讀入測資$→$二分搜$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,arr[300][300],mx=INT_MIN;
```
其中$mx$存最大高度值，在二分搜時會用到
#### 輸入
```cpp=52
cin>>n;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
cin>>arr[i][j];
mx=max(mx,arr[i][j]);
}
```
#### $bfs$函式
```cpp=4
int bfs(int res){
vector<vector<bool>>been(n,vector<bool>(n,0));
queue<pair<int,int>>q;
q.push({0,0});
been[0][0]=1;
int ans=1;
while(q.size()){
int t=q.size();
for(int i=0;i<t;i++){
int r=q.front().first,c=q.front().second;
q.pop();
if(r!=0&&!been[r-1][c]&&abs(arr[r][c]-arr[r-1][c])<=res){
been[r-1][c]=1;
q.push({r-1,c});
if(r-1==n-1&&c==n-1)return ans;
}
if(r!=n-1&&!been[r+1][c]&&abs(arr[r][c]-arr[r+1][c])<=res){
been[r+1][c]=1;
q.push({r+1,c});
if(r+1==n-1&&c==n-1)return ans;
}
if(c!=0&&!been[r][c-1]&&abs(arr[r][c]-arr[r][c-1])<=res){
been[r][c-1]=1;
q.push({r,c-1});
if(r==n-1&&c-1==n-1)return ans;
}
if(c!=n-1&&!been[r][c+1]&&abs(arr[r][c]-arr[r][c+1])<=res){
been[r][c+1]=1;
q.push({r,c+1});
if(r==n-1&&c+1==n-1)return ans;
}
}
ans++;
}
return -1;
}
```
函式吃的參數$res$是高度差限制
一開始先在函式內宣告一個$bool$二維陣列$been$記錄一個點有沒有到過，
與一個隊列$q$來執行$bfs$，其中隊列裡存的$pair$是$\{$橫軸座標$,$縱軸座標$\}$
第15到35行就是一般的$bfs$程式，只是加上高度差的判斷而已
另外$ans$存的是最短路徑的長度，並在遇到目標點(右下角)時就直接回傳，
如果最後怎麼都走不到目標點就回傳$-1$，也就是無解的意思
#### 二分搜
```cpp=40
pair<int,int>b_s(int l,int r){
if(l==r)return {l,bfs(l)};
else if(r==l+1){
int t=bfs(l);
if(t!=-1)return {l,t};
else return {r,bfs(r)};
}
int m=(l+r)/2,t=bfs(m);
if(t==-1)return b_s(m+1,r);
else return b_s(l,m);
}
```
函式回傳的是最小高度限制與所對應的最短路徑長度
二分搜執行時以$bfs$的值為判斷條件，若值為$-1$將範圍上修，不然下修
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,arr[300][300],mx=INT_MIN;
int bfs(int res){
vector<vector<bool>>been(n,vector<bool>(n,0));
queue<pair<int,int>>q;
q.push({0,0});
been[0][0]=1;
int ans=1;
while(q.size()){
int t=q.size();
for(int i=0;i<t;i++){
int r=q.front().first,c=q.front().second;
q.pop();
if(r!=0&&!been[r-1][c]&&abs(arr[r][c]-arr[r-1][c])<=res){
been[r-1][c]=1;
q.push({r-1,c});
if(r-1==n-1&&c==n-1)return ans;
}
if(r!=n-1&&!been[r+1][c]&&abs(arr[r][c]-arr[r+1][c])<=res){
been[r+1][c]=1;
q.push({r+1,c});
if(r+1==n-1&&c==n-1)return ans;
}
if(c!=0&&!been[r][c-1]&&abs(arr[r][c]-arr[r][c-1])<=res){
been[r][c-1]=1;
q.push({r,c-1});
if(r==n-1&&c-1==n-1)return ans;
}
if(c!=n-1&&!been[r][c+1]&&abs(arr[r][c]-arr[r][c+1])<=res){
been[r][c+1]=1;
q.push({r,c+1});
if(r==n-1&&c+1==n-1)return ans;
}
}
ans++;
}
return -1;
}
pair<int,int>b_s(int l,int r){
if(l==r)return {l,bfs(l)};
else if(r==l+1){
int t=bfs(l);
if(t!=-1)return {l,t};
else return {r,bfs(r)};
}
int m=(l+r)/2,t=bfs(m);
if(t==-1)return b_s(m+1,r);
else return b_s(l,m);
}
int main(){
cin>>n;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
cin>>arr[i][j];
mx=max(mx,arr[i][j]);
}
auto tmp=b_s(0,mx);
cout<<tmp.first<<"\n"<<tmp.second;
}
```
## 心得
因為六月才剛考過的關係，這次APCS就想說先不要報，等一月的再說(當時沒想到的是一月臨時有事去不了QQ)，結果到ZJ上看到題目時才發現這次居然有兩題圖論！沒有DP！~~我最討厭的就是DP了！~~
後來就抱著悔恨的心情默默把四題寫完，一邊想說自己為甚麼沒有報...
---
或許是因為比較擅長圖論的關係，整體而言我覺得最難的反而是第二題，在寫的時候花了一些時間思考要怎麼找到每個方塊最後的位置，最後才決定硬做，直接從最右邊的位置開始往左試，確認一個位置合不合也直接用硬驗的方式。丟到ZJ上一次就過的時候也蠻開心的，~~果然暴力才是王道阿~~
第三題很快就想到遞迴的做法，然後發現題目好像就這樣...沒有更多的延伸。雖然網路上也有人是用stack或是vector做，但我個人還是覺得遞迴比較直觀，而且main函式非常簡潔～
至於第四題我認為我原本可能要想一下，結果我就看到ZJ上的標籤
然後我就知道解法了(都不給人思考的誒)
不過我對對答案二分搜確實也不是那麼熟，剛好藉這題練一下
這題最大的問題反而是我bfs有個智障bug一直沒找出來(好像是if後面忘了寫那個條件要幹嘛之類的)，害我吃了四個NA(自作自受)，經過20分鐘debug後終於找到了...
---
整體而言我覺得這次題目有對到我胃口，寫起來算是順，只是遇到這種狀況要多注意不要犯智障的錯誤，讓自己debug到死
另外就是我還是要去好好練DP，總不能每次都祈禱最後一題是圖論吧？而且如果我DP也不錯的話這次大概也不會那麼嘔了
Sign in with Wallet
Connect another wallet