# 2022年10月APCS題解
## P1巴士站牌
[題目](https://zerojudge.tw/ShowProblem?problemid=i428)
>初階教學:
沒什麼好講的，照題序打
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
vector<pair<int, int> > vc(200);
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> vc[i].x;
cin >> vc[i].y;
}
int maxn = 0;
int minn = INT_MAX;
for(int i = 0; i < n - 1; i++){
maxn = max(maxn,abs(vc[i].x - vc[i+1].x) + abs(vc[i].y - vc[i+1].y));
minn = min(minn,abs(vc[i].x - vc[i+1].x) + abs(vc[i].y - vc[i+1].y));
}
cout << maxn << ' ' << minn << '\n';
}
```
## 運貨站
[題目](https://zerojudge.tw/ShowProblem?problemid=j123)
>初階教學:
實作題，每種方塊都是從最外面一格一格向內推，如果撞到東西了，就更新陣列，然後break，輸入下一個。
最後在跑過一輪看有多少位置沒有被更新過。
A B C D E的code都差不多，就只有判斷和更新一點點不一樣
>by進階助教
>不能用向外推的方式
>會爛掉的側資:
>1 1 1 0
0 0 1 0
0 0 1 0
0 0 1 0
C 1
```cpp=
#include<bits/stdc++.h>
using namespace std;
int arr[1000][1000];
int main(){
int r, c, n;
cin >> r >> c >> n;
int blank = 0, out = 0;
for(int i = 0; i < r; i++){
arr[i][0] = 1;
}
while(n--){
char cc; cin >> cc;
int t; cin >> t;
if(cc == 'A'){
for(int i = c; i >= 0; i--){
if(arr[t][i] or arr[t+1][i] or arr[t+2][i] or arr[t+3][i]){
if(i < c){
arr[t][i+1] = 1;
arr[t+1][i+1] = 1;
arr[t+2][i+1] = 1;
arr[t+3][i+1] = 1;
}
else{
out++;
}
break;
}
}
}
if(cc == 'B'){
for(int i = c; i >= 0; i--){
if(arr[t][i]){
if(i + 3 <= c){
arr[t][i+1]=1;
arr[t][i+2]=1;
arr[t][i+3]=1;
}
else{
out++;
}
break;
}
}
}
if(cc == 'C'){
for(int i = c; i >= 0; i--){
if(arr[t][i] or arr[t+1][i]){
if(i+2 <= c){
arr[t][i+1] = 1;
arr[t][i+2] = 1;
arr[t+1][i+1] = 1;
arr[t+1][i+2] = 1;
}
else{
out++;
}
break;
}
}
}
if(cc == 'D'){
for(int i = c; i >= 0; i--){
if(arr[t+1][i] or arr[t][i+2]){
if(i + 3 <= c){
arr[t+1][i+1]=1;
arr[t+1][i+2]=1;
arr[t+1][i+3]=1;
arr[t][i+3] = 1;
}
else{
out++;
}
break;
}
}
}
if(cc == 'E'){
for(int i = c; i >= 0; i--){
if(arr[t][i+1] or arr[t+1][i] or arr[t+1][i+1] or arr[t+2][i] or arr[t+2][i+1]){
if(i+2 <= c){
arr[t][i+2] = 1;
arr[t+1][i+1] = 1;
arr[t+1][i+2] = 1;
arr[t+2][i+1] = 1;
arr[t+2][i+2] = 1;
}
else{
out++;
}
break;
}
}
}
// for(int i = 0; i < r; i++){
// for(int j = 0; j <= c; j++){
// cout << arr[i][j] ;
// }cout << '\n';
// }
}
for(int i = 0; i < r; i++){
for(int j = 1; j <= c; j++){
if(!arr[i][j])blank++;
}
}
cout << blank << ' ' << out << '\n';
}
```
## 石窟探險
[題目](https://zerojudge.tw/ShowProblem?problemid=j124)
>初階教學:
用DFS跟著探險家走，輸入偶數就向下DFS兩個叉路，基數就三個，0就回傳，並在DFS傳值時傳上一個節點的值，只要現在的節點不是0就可以把兩個差加入ans中
(這題節點數*節點值的大小會爆int，所以記得開long long)
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans = 0;
bool flag = 1;
void dfs(int p){
int x;
cin >> x;
if(flag){
ans -= x;
flag = 0;
}
ans += abs(p - x);
if(x == 0){
ans -= abs(p - x);
return;
}
if(x % 2 == 0){
dfs(x);
dfs(x);
return;
}
else if(x % 2 == 1){
dfs(x);
dfs(x);
dfs(x);
return;
}
}
signed main(){
dfs(0);
cout << ans << '\n';
}
```
>進階教學:
照著題目做
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector< int > tree;
void add_node(int n) {
tree.emplace_back( n );
tree.emplace_back( n );
if( n & 1 )
tree.emplace_back( n );
}
int main () {
ll ans = 0, n;
cin >> n;
add_node(n);
while( cin >> n ) {
if( n!=0 )
ans += abs(tree.back()-n);
tree.pop_back();
if( n!= 0)
add_node(n);
}
cout << ans;
}
```
> frankie:
```cpp=
#include <bits/stdc++.h>
#define V vector
#define sz size()
#define pb push_back
#define em empty()
using LL = long long;
using namespace std;
constexpr int N=1e6+1;
V < V<int> > vec(N,V<int>());
LL ans=0;
V <int> v;
void dfs(const int &cur){
v.pb(cur);
for (const int &i:vec[cur]) if (i) dfs(i);
if (v.sz>1) return ans+=abs(v.back()-v[v.sz-2]),v.pop_back();
return v.pop_back();
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n,root;
stack <int> sk;
cin >> root,sk.push(root);
while (cin >> n){
vec[sk.top()].pb(n);
if (n) sk.push(n);
while (!sk.em&&vec[sk.top()].sz==2+(sk.top()&1)) sk.pop();
if (sk.em) break;
}
dfs(root),cout << ans;
return 0;
}
```
## 蓋步道
[題目](https://zerojudge.tw/ShowProblem?problemid=j125)
這題就是二分搜加上BFS
單調性:只要小的高度可以走，那麼大的就一定可以
所以我們用這個單調性做二分搜
然後用BFS做每次二分搜時的檢查
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int v[500][500];
int h[500][500];
struct qq{
int x;
int y;
int step;
qq(){x = 1;y = 1; step = 0;}
};
queue<qq> q;
void clear(queue<qq>& q){
queue<qq> empty;
swap(q,empty);
}
int BFS(int hh){
clear(q);
v[1][1] = 1;
qq t;q.push(t);
while(!q.empty()){
qq now = q.front();
q.pop();
if(now.x > n or now.y > n)cout << "test" << '\n';
//cout << "xy" << now.x << ' ' << now.y << '\n';
if(now.x == n && now.y == n){
return now.step;
}
if(now.x < n)
if(abs(h[now.x + 1][now.y] - h[now.x][now.y]) <= hh && !v[now.x + 1][now.y]){
qq tmp;
tmp.x = now.x + 1;tmp.y = now.y;tmp.step = now.step + 1;
v[now.x+1][now.y] = 1;
//cout << "txy" << tmp.x << ' ' << tmp.y << '\n';
q.push(tmp);
}
if(now.y < n)
if(abs(h[now.x][now.y + 1] - h[now.x][now.y]) <= hh && !v[now.x][now.y + 1]){
qq tmp;
tmp.x = now.x; tmp.y = now.y + 1;tmp.step = now.step + 1;
v[now.x][now.y + 1] = 1;
//cout << "txy" << tmp.x << ' ' << tmp.y << '\n';
q.push(tmp);
}
if(now.x > 1)
if(abs(h[now.x-1][now.y] - h[now.x][now.y]) <= hh && !v[now.x - 1][now.y]){
qq tmp;
tmp.x = now.x - 1; tmp.y = now.y;tmp.step = now.step + 1;
v[now.x - 1][now.y] = 1;
//cout << "txy" << tmp.x << ' ' << tmp.y << '\n';
q.push(tmp);
}
if(now.y > 1)
if(abs(h[now.x][now.y - 1] - h[now.x][now.y]) <= hh && !v[now.x][now.y - 1]){
qq tmp;
tmp.x = now.x; tmp.y = now.y - 1;tmp.step = now.step + 1;
v[now.x][now.y - 1] = 1;
//cout << "txy" << tmp.x << ' ' << tmp.y << '\n';
q.push(tmp);
}
}
return -1;
}
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> h[i][j];
}
}
int l = 0, r = 1e6+1;
int m,k;
int anss;
while((r > l)){
m = (l + r) >> 1;
//cout << l <<' '<< m <<' '<< r << '\n';
k = BFS(m);
memset(v,0,sizeof(v));
//cout << k <<'\n';
if(k == -1){
l = m + 1;
}
if(k != -1){
r = m;
anss = k;
}
}
cout << l << '\n' << anss << '\n';
}
// 0 0 1
```
<!--
> 進階教學
```cpp=
#include<bits/stdc++.h>
using namespace std;
int ar[ 302 ][ 302 ];
bool vis[ 302 ][ 302 ];
int N;
int dx[ 4 ] = {0, 0, 1, -1};
int dy[ 4 ] = {1, -1, 0, 0};
struct pnt {
int x, y, len;
pnt( int _x, int _y, int _len ) : x(_x), y(_y), len(_len){} ;
pnt(){} ;
};
int bfs( int m ) {
memset( vis, 0, sizeof(vis) );
queue<pnt> qq;
qq.emplace(1, 1, 0);
while( !qq.empty() ) {
auto a = qq.front(); qq.pop();
if( vis[ a.x ][ a.y ] ) continue;
if( a.x == N && a.y == N )
return a.len;
vis[ a.x ][ a.y ] = true;
for( int i = 0; i < 4; ++i ) {
int nx = a.x + dx[i];
int ny = a.y + dy[i];
if( nx < 1 || nx > N ) continue;
if( ny < 1 || ny > N ) continue;
if( vis[ nx ][ ny ] ) continue;
if( abs(ar[ nx ][ ny ] - ar[ a.x ][ a.y ]) > m ) continue;
qq.emplace( nx, ny, a.len+1 );
}
}
return -1;
}
int main () {
cin >> N;
for( int i = 1; i <= N; ++i )
for( int j = 1; j <= N; ++j )
cin >> ar[i][j];
int l = -1, r = 1e6+1;
while( r-l > 1 ) {
int m = (l+r+1)/2;
int ans = bfs( m );
if( ans == -1 )
l = m;
else
r = m;
}
cout << l+1 << '\n' << bfs(l+1) << '\n';
}
```
>frankie解:
```cpp=
#include <bits/stdc++.h>
#define V vector
using namespace std;
const int N = 1e6, S = 301;
struct path {int x, y, sl, len;};
int mnm, n;
V < V<int> > vec;
void modify(queue <path> &q, const int &x, const int &y, const int &sl, const int &len, const int &lim){
path p;
if (sl <= lim){
p.x = x;
p.y = y;
p.sl = sl;
p.len = len;
q.push(p);
}
}
bool judge(const int &lim) {
V < V<bool> > vst(S,V<bool>(S));
queue <path> q;
path p;
p.x = p.y = p.sl = p.len = 0;
q.push(p);
while (!q.empty()){
int x=q.front().x, y=q.front().y, sl=q.front().sl, len=q.front().len;
q.pop();
if (x == n && y == n){
mnm = len;
return true;
}
if (vst[y][x]) continue;
vst[y][x] = true;
len++;
if (x) modify(q, x-1, y, max( abs(vec[y][x] - vec[y][x - 1]), sl) , len, lim);
if (x != n) modify(q, x+1, y, max( abs(vec[y][x] - vec[y][x + 1]), sl), len, lim);
if (y) modify(q, x, y-1, max( abs(vec[y][x] - vec[y - 1][x]), sl) , len, lim);
if (y != n) modify(q, x, y+1, max( abs(vec[y][x] - vec[y + 1][x]), sl), len, lim);
}
return false;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int l=0, r=-1, len;
cin >> n;
vec.assign(n,V<int>(n));
n--;
for (auto &i: vec) for (int &j: i) cin >> j, r = max(r, j);
for (int mid = (l + r) >> 1; ; mid = (l + r) >> 1)
if (l == mid) break;
else if (judge(mid)) r = mid,len = mnm;
else l = mid;
if (!judge(l)) l++;
cout << l << endl << len;
return 0;
}
```
-->
Sign in with Wallet
Connect another wallet