# 10/23 APCS參考題解
難得我比較有把握的一次APCS 希望能撈個5級分 QQ
## pA: 巴士站牌
[題目連結](https://zerojudge.tw/ShowProblem?problemid=i428)
簡單題，用一個陣列維護資訊，再跑過一次就好
:::spoiler code
```cpp!
#include <iostream>
using namespace std;
// 宣告變數
int mi=1e9, ma=-1e9; // mi紀錄最小值，ma紀錄最大值
// 用來儲存題目的輸入
int n;
int x[105], y[105];
int main(){
// 輸入，資訊的編號是0~n-1
cin >> n;
for (int i=0 ; i<n ; i++){
cin >> x[i] >> y[i];
}
// 從第1個車站開始，直到n-1
// 每次都是比較i跟i-1（即相鄰的車站）
for (int i=1 ; i<n ; i++){
// 如果現在檢查的車站距離比以前的還要短
// 那麼就更新最小值
if (abs(x[i]-x[i-1])+abs(y[i]-y[i-1])<mi){
mi=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
}
// 備註：這個寫法更簡潔
// mi=min(mi, abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);)
// 同上
if (abs(x[i]-x[i-1])+abs(y[i]-y[i-1])>ma){
ma=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
}
}
// 輸出
cout << ma << " " << mi << endl;
return 0;
}
```
:::
## pB: 貨運站
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j123)
一題正常的pB，簡單但複雜的實作題，感覺很像俄羅斯方塊
由於前兩題幾乎不用考慮時間複雜度，看到的時候我就打算模擬了
看到輸出，我是打算維護兩個變數：已經被塞入的空格（這點與題目的書初步一樣，但是我認為更好維護）以及不能被放入貨物數量
步驟大概是
1. 初始化版面，留下左邊邊界當作中止點
2. 確認是哪種貨物（一個一個手刻原始座標），並且在起點生成
3. 將方塊從慢慢把左邊邊界移動，**直到碰到邊界或是前面放的方塊**
4. 結束後，檢查是否可以放置，如果可以的話就將方塊設成**已經被放入的貨物**，否則增加第二個變數的值。
:::spoiler code
```cpp!
#include <bits/stdc++.h>
using namespace std;
#define int long long
// 宣告
int r, c, n, tmp;
int op1=0, op2=0; // op1: 維護有多少格子被放置, op2: 維護有多少貨物放不進去
char type;
vector<pair<char, int>> v; // 維護輸入
int arr[100][100]; // 貨櫃版面, 0: 空格，1: 正在放入的貨物，2: 邊界或是已經放入的貨物
signed main(void){
// 初始化版面
for (int i=0 ; i<100 ; i++){
arr[i][0]=2;
}
// 輸入
cin >> r >> c >> n;
for (int i=0 ; i<n ; i++){
cin >> type >> tmp;
v.push_back({type, tmp});
}
// 放入貨物
for (int i=0 ; i<n ; i++){
pair<int, int> block[5]; // 貨物的每個方格座標
int block_cnt; // 貨物的大小
// 生成貨物 & 設定初始座標(x=60為起點)
if (v[i].first=='A'){
block_cnt=4;
block[0]={v[i].second, 60};
block[1]={v[i].second+1, 60};
block[2]={v[i].second+2, 60};
block[3]={v[i].second+3, 60};
}
if (v[i].first=='B'){
block_cnt=3;
block[0]={v[i].second, 60};
block[1]={v[i].second, 61};
block[2]={v[i].second, 62};
}
if (v[i].first=='C'){
block_cnt=4;
block[0]={v[i].second, 60};
block[1]={v[i].second+1, 60};
block[2]={v[i].second, 61};
block[3]={v[i].second+1, 61};
}
if (v[i].first=='D'){
block_cnt=4;
block[0]={v[i].second+1, 60};
block[1]={v[i].second+1, 61};
block[2]={v[i].second, 62};
block[3]={v[i].second+1, 62};
}
if (v[i].first=='E'){
block_cnt=5;
block[0]={v[i].second+1, 60};
block[1]={v[i].second+2, 60};
block[2]={v[i].second, 61};
block[3]={v[i].second+1, 61};
block[4]={v[i].second+2, 61};
}
// 在初始地點放置貨物
for (int j=0 ; j<block_cnt ; j++){
arr[block[j].first][block[j].second]=1;
}
// 移動貨物直到不能移動
bool check=1;
while (1){
for (int j=0 ; j<block_cnt ; j++){
if (arr[block[j].first][block[j].second-1]==2){
check=0;
break;
}
}
if (check){
// 每個方塊都可以被移動，更新版面
for (int j=0 ; j<block_cnt ; j++){
arr[block[j].first][block[j].second]=0;
arr[block[j].first][block[j].second-1]=1;
block[j].second--;
}
continue;
}else{
// 不能被移動了，確認是否有超出範圍
check=1;
for (int j=0 ; j<block_cnt ; j++){
if (block[j].second>c){
check=0;
}
}
if (check){
// 可以被放置，更新op1以及目前版面
op1+=block_cnt;
for (int j=0 ; j<block_cnt ; j++){
arr[block[j].first][block[j].second]=2;
}
}else{
// 不能被放置，更新op2以及清掉貨物
op2++;
for (int j=0 ; j<block_cnt ; j++){
arr[block[j].first][block[j].second]=0;
}
}
break;
}
}
}
// 輸出
cout << r*c-op1 << " " << op2 << "\n"; // 因為op1維護有多少格子被放置，記得要用貨物箱大小扣除
return 0;
}
```
:::
## pC: 石窟探險
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j124)
我第一眼想到的是跟2019年2月[合成函數](https://judge.tcirc.tw/ShowProblem?problemid=d002)很像
大概的想法就是DFS一次，要回溯的時候只要不是根或是0再把答案給遞迴上去
:::spoiler code
```cpp!
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e18;
// 宣告
int f(int x){
int n;
cin >> n;
if (n==0){
return 0;
}
int add=0;
if (x!=-1){
add=abs(x-n);
}
if (n%2==0){
return add+f(n)+f(n);
}else{
return add+f(n)+f(n)+f(n);;
}
}
signed main(void){
// 輸入
cout << f(-1) << "\n";
return 0;
}
```
:::
## pD: 蓋步道
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j125)
原本我想要用動態規劃的，但是想不出來狀態要怎麼轉移，剛好昨天才在寫[Reset K Edges](https://codeforces.com/contest/1739/problem/D)，結構驚人的相似，發現**是否能在k的平緩度以下**具有單調性，稍微算一下時間複雜度是$O(300 \times 300 \times 4\times \log_2{10^6})$，感覺還不錯就開始寫了
另外，因為題目有要另外求最短距離，所以得用BFS而不是DFS，並且由於有可能會從四個方向轉移，因此vis紀錄需要多開一個維度
:::spoiler code
```cpp!
#include <bits/stdc++.h>
using namespace std;
#define int long long
// 宣告
int n, tmp;
int arr[400][400], vis[4][400][400];
int op1, op2; // op1: 最小的相差值，op2: 最小的長度
const int mx[4]={1, 0, -1, 0};
const int my[4]={0, 1, 0, -1};
struct position{
int x;
int y;
int len;
};
// check函式
bool check(int mid){
//初始化
memset(vis, 0, sizeof(vis));
queue<position> que;
que.push({1, 1, 0});
// 記得紀錄vis
vis[0][1][1]=1;
vis[1][1][1]=1;
vis[2][1][1]=1;
vis[3][1][1]=1;
// BFS 流程
while (que.size()){
position now=que.front();
que.pop();
// 確認是否抵達終點（因為BFS的特性，最先到終點的一定是答案）
if (now.x==n && now.y==n){
op1=mid;
op2=now.len;
return 1;
}
// 繼續尋找周圍的點
for (int j=0 ; j<4 ; j++){
int next=arr[now.x+mx[j]][now.y+my[j]];
if (next!=-1 && vis[j][now.x+mx[j]][now.y+my[j]]==0 && abs(next-arr[now.x][now.y])<=mid){
que.push({now.x+mx[j], now.y+my[j], now.len+1});
vis[j][now.x+mx[j]][now.y+my[j]]=1;
}
}
}
return 0;
}
signed main(void){
// 輸入
cin >> n;
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=n ; j++){
// 使用based 1，待會邊界比較好寫
cin >> arr[i][j];
}
}
// 初始化邊界，用-1代表
for (int i=0 ; i<=n+1 ; i++){
arr[0][i]=-1;
arr[n+1][i]=-1;
arr[i][0]=-1;
arr[i][n+1]=-1;
}
// 二分搜 (左閉右開寫法)
int l=0, r=1e6+1, mid;
while (l<r){
mid=l+(r-l)/2;
if (check(mid)){
r=mid;
}else{
l=mid+1;
}
}
// 輸出
cout << op1 << " " << op2 << "\n";
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet