2022 10 月 APCS實作題

簡介

2022/10/23考完APCS了，是我第一次考，實作的部分打了前三題，下面就放我當晚回家後打得程式碼吧ㄏㄏ

Problem1

題目敘述：點我(zerojudge)
想法：照著題意用迴圈跑
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)
想法：構造矩陣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)
想法：按照題意利用遞迴輸入，接著做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