---
tags: 競賽程式, cp, APCS, 演算法, 圖論, 二分搜, 資料結構, 枚舉, 遞迴
---
# 2022 10 月 APCS實作題

<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>
## 簡介
2022/10/23考完APCS了，是我第一次考，實作的部分打了前三題，下面就放我當晚回家後打得程式碼吧ㄏㄏ
## Problem1
***題目敘述***：[點我(zerojudge)](https://zerojudge.tw/ShowProblem?problemid=i428)
***想法***：照著題意用迴圈跑
***AC CODE***(在zj上面跑的)：

#include<bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 9999999
int per(int x){
	if(x<0)return x*-1;
	else return x;
}
int dis(int x1, int y1, int x2, int y2){
	return per(x1-x2)+per(y1-y2);
}
int main(){
	wh_ale;
	int n, i, j, mn=INF, mx=-1, a[1000][2];
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a[i][0] >> a[i][1];
	}
	int now;
	for(i=1;i<n;i++){
		now=dis(a[i][0], a[i][1], a[i-1][0], a[i-1][1]);
		mn=min(now, mn);
		mx=max(now, mx);
	}
	cout << mx << ' ' << mn <<'\n';
	return 0;
}

## Problem2
***題目敘述***：[點我(zerojudge)](https://zerojudge.tw/ShowProblem?problemid=j123)
***想法***：構造矩陣```a[37][57]```模擬箱子，並且初始化0代表沒有放置物品，1則代表有，同時使用另一個陣列```now[37]```紀錄目前每個高度最外側的放置位置。接著按照輸入的行李箱類別以及高度用迴圈做搜尋，如果搜尋後發現可以放置則變更```a[37][57]```狀態，否則無法放置的數目增加1
***AC CODE***(在zj上面跑的)：

#include<bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 9999999
int main(){
	wh_ale;
	int r, c, n, i, j, ans, cnt=0;
	int a[37][57]={};
	int now[37]={};
	cin >> r >> c >> n;
	bool k;
	ans=r*c;
	char x;
	int t;
	while(n--){
		k=false;
		cin >> x >> t;
		if(x=='A'){
			for(i=max({now[t], now[t+1], now[t+2], now[t+3]});i<c;i++){
				if(a[t][i]==0 and a[t+1][i]==0 and a[t+2][i]==0 and a[t+3][i]==0){
				    a[t][i]=1;
				    a[t+1][i]=1;
				    a[t+2][i]=1;
				    a[t+3][i]=1;
				    for(j=0;j<4;j++){
				        now[t+j]=i+1;
				    }
				    k=true;
			        ans-=4;
			        break;
				}
			}
		}
		else if(x=='B'){
			for(i=max(now[t], 2);i<c;i++){
				if(a[t][i]==0 and a[t][i-1]==0 and a[t][i-2]==0){
				    a[t][i]=1;
				    a[t][i-2]=1;
				    a[t][i-1]=1;
				    now[t]=i+1;
				    k=true;
			        ans-=3;
			        break;
				}
			}
		}
		else if(x=='C'){
			for(i=max({now[t], now[t+1], 1});i<c;i++){
				if(a[t][i]==0 and a[t+1][i]==0 and a[t+1][i-1]==0 and a[t][i-1]==0){
				    a[t][i]=1;
				    a[t+1][i]=1;
				    a[t+1][i-1]=1;
				    a[t][i-1]=1;
				    now[t]=i+1;
				    now[t+1]=i+1;
				    k=true;
			        ans-=4;
			        break;
				}
			}
		}
		else if(x=='D'){
			for(i=max({now[t], now[t+1], 2});i<c;i++){
				if(a[t][i]==0 and a[t+1][i]==0 and a[t+1][i-1]==0 and a[t+1][i-2]==0){
				    a[t][i]=1;
				    a[t+1][i]=1;
				    a[t+1][i-1]=1;
				    a[t+1][i-2]=1;
				    now[t]=i+1;
				    now[t+1]=i+1;
				    k=true;
			        ans-=4;
			        break;
				}
			}
		}
		else if(x=='E'){
			for(i=max({1, now[t+1], now[t], now[t+2]});i<c;i++){
				if(a[t][i]==0 and a[t+1][i]==0 and a[t+1][i-1]==0 and a[t+2][i]==0 and a[t+2][i-1]==0){
				    a[t][i]=1;
				    a[t+1][i]=1;
				    a[t+1][i-1]=1;
				    a[t+2][i]=1;
				    a[t+2][i-1]=1;
				    now[t]=i+1;
				    now[t+1]=i+1;
				    now[t+2]=i+1;
				    k=true;
			        ans-=5;
			        break;
				}
			}
		}
		if(k==false) cnt++;
	}
	cout << ans <<' '<<cnt <<'\n';
	return 0;
}

***小提醒：*** 迴圈要記得break
## Problem3
***題目敘述***：[點我(zerojudge)](https://zerojudge.tw/ShowProblem?problemid=j124)
***想法***：按照題意利用遞迴輸入，接著做DFS跑
***AC CODE***(在zj上面跑的)：

#include<bits/stdc++.h>
using namespace std;
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 9999999
#define int long long
#define phb push_back
int n, cnt=0, st;
vector<int> g[200001];
int per(int x){
	if(x<0)return x*-1;
	else return x;
}
void dfs(int x){
	int i;
	for(i=0;i<g[x].size();i++){
		cnt += per(g[x][i]-x);
		dfs(g[x][i]);
	}
}
void read(int x){
	int k, i;
	if(x%2==0){
		for(i=0;i<2;i++){
			cin >> k;
			if(k != 0){
				g[x].phb(k);
				read(k);
			}
		}
	}
	else {
		for(i=0;i<3;i++){
			cin >> k;
			if(k != 0){
				g[x].phb(k);
				read(k);
			}
		}
	}
}
signed main(){
	wh_ale;
	cin >> st;
	read(st);
	dfs(st);
	cout << cnt <<'\n';
	return 0;
}

***小提醒：*** 要記得開 ```long long```