APCS 11110 (實作題)
===
https://drive.google.com/drive/folders/1XLeCHTzrrf1Io9wZ2IPWAJylZp2ZeDyr
[toc]
:::info
**TODO**:
- 講解題目
- 題目標題
- 題目意思
- 輸入輸出例子
- 子題分數範圍 & 時間限制
- 題目敘述
- 至少寫三個 sample testcase
- 說明 sample testcase
- 生測資
- assert 輸入輸出範圍
- 說明每筆測試資料要測試什麼 case
- 上架 Zerojudge
- 題目敘述
- 測試資料
:::
## P1 巴士站距離 ???sec
:::info
:::
### 題目
:::info
輸入座標範圍 [-100, 100]
subtask
- 50%
- 50%
:::
第一題 給 n 個二維座標（4<=n<=100）
求第 i 個和第 i+1 個座標的曼哈頓距離的最大&最小值
有
平面上有 $n$ 個巴士站，第 $i$ 個巴士站的位置可以用座標點 $(x_i, y_i)$ 來表示。
兩個巴士站之間行進的時間是這兩個巴士站座標的曼哈頓距離。曼哈頓距離的定義如下：
對於兩個座標點 $(x_1, y_1)$ 與 $(x_2, y_2)$，兩點之間曼哈頓距離的為 $|x_1-x_2| + |y_1 - y_2|$。
你今天要從的巴士站 $1$ 坐車到巴士站 $n$，中間依序經過巴士站 $2, 3, 4, \cdots, (n-1)$。
請計算過程中相鄰兩站的行進時間的 **最大值** 與 **最小值**。
### 輸入格式
第 1 行有一個正整數 $n$ 表示路程中總共會經過幾個巴士站
在輸入的第 $2$ 行到第 $n+1$ 行，每行有兩個整數標示巴士站的座標。
嚴格的說，輸入第 $i+1$ 行的兩個數字依序是 $x_i$ 和 $y_i$。
子題配分：
$(60\%)$：$n = 4 $ 且 $-100 \leq x_i, y_i \leq 100$
$(60\%)$：$2 \leq n \leq 100$ 且 $-100 \leq x_i, y_i \leq 100$
### 輸出格式
在一行輸出兩個整數並以空格分開。
第一個整數表示相鄰兩站的行進時間的**最大值**。
第二個整數表示相鄰兩站的行進時間的**最小值**。
**sample 1**
```
Inpuuuuuuuuuut 1
4
1 1
1 3
4 5
2 6
```
```
Outpuuuuuuuuut 1
5 2
```
**sample 2**
```
Inpuuuuuuuuuut 2
3
1 2
-1 -1
1 3
```
```
Outpuuuuuuuuut 2
6 5
```
### note
#### 範例 1
#### 範例 2
### 子題
#### 1-10
(60%)
./gen 4 1
./gen 4 2
./gen 4 3
./gen 4 4
./gen 4 5
./gen 4 6
./gen 4 7
./gen 4 8
./gen 4 9
./gen 4 10
#### 11
4
100 100
-100 -100
0 0
0 0
#### 12
4
-100 100
100 -100
3 3
-3 -3
#### 13-20
./gen 100 13
./gen 100 14
./gen 100 15
./gen 100 16
./gen 100 17
./gen 100 18
./gen 100 19
./gen 100 20
## P2 運貨站 ???sec
:::info
task 1: 只有 OOO 的
task 2: 圖片上排三種
task 3:
:::
### 題目
第二題 奇怪的模擬題 有 n 個可以分為五種不同形狀的東西 依序推進一個 R*C 的倉庫裡 等等補形狀 R<=30 C<=50 n<=200
一開始都在右邊，每次給一個東西的右上角的 y 座標，要往左邊推，直到不同移動為止。
輸出有幾個格子沒有被填滿
### 輸入格式
R C N
A y1
### 輸出格式
**sample 1**
```
Inpuuuuuuuuuut 1
```
5 4 5
B 1
B 2
B 4
B 2
B 4
```
Outpuuuuuuuuut 1
11 2
剩下 11 個格子2個物件不能放進去
[0, 0] ~ [R-1, C-1]
```
**sample 2**
```
Inpuuuuuuuuuut 2
```
```
Outpuuuuuuuuut 2
```
### note
#### 範例 1
#### 範例 2
```cpp=
#include <bits/stdc++.h>
using namespace std;
int r, c;
array<int, 5> Ly = {3, 0, 1, 1, 2}, Lx = {0, 2, 1, 2, 1};
array<array<int, 34>, 54> D;
int push(int x, int y, int t){
for(; x; x--){
if(t == 0 && (D[x][y] || D[x][y - 1] || D[x][y - 2] || D[x][y - 3])) break;
else if(t == 1 && D[x][y]) break;
else if(t == 2 && (D[x][y] || D[x][y - 1])) break;
else if(t == 3 && (D[x][y] || D[x + 2][y - 1])) break;
else if(t == 4 && (D[x][y] || D[x][y - 1] || D[x + 1][y - 2])) break;
}
x++;
if(x + Lx[t] > c) return 1;
if(t == 0) D[x][y] = D[x][y - 1] = D[x][y - 2] = D[x][y - 3] = 1;
else if(t == 1) D[x][y] = D[x + 1][y] = D[x + 2][y] = 1;
else if(t == 2) D[x][y] = D[x][y - 1] = D[x + 1][y] = D[x + 1][y - 1] = 1;
else if(t == 3) D[x][y] = D[x + 1][y] = D[x + 2][y] = D[x + 2][y - 1] = 1;
else D[x][y] = D[x][y - 1] = D[x + 1][y] = D[x + 1][y - 1] = D[x + 1][y - 2] = 1;
return 0;
}
signed main(){
int n, y, up = 0, sum = 0;
char t;
cin >> r >> c >> n;
for(int i = 1; i <= n; i++){
cin >> t >> y, y += 1 + Ly[t - 'A'];
up += push(c, y, t - 'A');
}
for(int i = 1; i <= c; i++){
for(int j = 1; j <= r; j++){
sum += !D[i][j];
cout << D[i][j] << " ";
}
cout << "\n";
}
cout << sum << " " << up << "\n";
return 0;
}
```
#### sample 1
```
3 4 3
B 0
B 0
B 1
```
```
6 1
```
#### sample 2
```
5 6 3
C 3
D 4
A 4
```
```
18 0
```
#### sample 3
```
5 6 3
E 5
E 4
D 2
```
```
16 0
```
##### note
```
0 1 0 0 0 0
1 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0
1 1 0 1 0 0
1 1 1 1 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 1 0 0 0 0
1 1 0 1 0 0
1 1 1 1 0 0
0 0 1 1 1 0
0 0 1 1 1 0
16 0
```
#### sample 5
```
5 6 6
C 4
A 4
E 5
E 5
A 5
B 5
```
##### note
```
put C at 4
0 0 0 0 0 0
1 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
put A at 4
0 0 0 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
put E at 5
0 0 0 0 1 0
1 1 1 1 1 0
1 1 1 1 1 0
0 0 1 0 0 0
0 0 1 0 0 0
put E at 5 (failed)
0 0 0 0 1 0
1 1 1 1 1 0
1 1 1 1 1 0
0 0 1 0 0 0
0 0 1 0 0 0
put A at 5
0 0 0 0 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 1 0 0 1
0 0 1 0 0 0
put B at 5 (failed)
0 0 0 0 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 1 0 0 1
0 0 1 0 0 0
13 2
```
### 子題
(20%)
./gen 1 20 40 200 1
./gen 1 20 40 200 2
./gen 1 20 40 200 3
./gen 1 30 50 200 81
(40%)
./gen 2 30 50 200 4 ~ 11
(40%)
## P3 石窟探險 ???sec
:::info
序列長度 10^6
:::
編號 0 是死路
編號 [0, 100000]
石室數量不超過 [100000]
深度不超過 40
Time Limit Python 3s other 1s
第三題 現在有一棵樹，偶數號節點有兩個邊，奇數號節點有三個邊，有人從根開始依序走左（中）右三條邊做DFS 然後給你走完的序列（0代表走下去的是死路）要你算每個節點與子節點的差的絕對值總和
深度 < 40
### 題目
### 輸入格式
2 0 0 0
### 輸出格式
**sample 1**
```
Inpuuuuuuuuuut 1
```
2 6 0 8 14 0 0 0 10 0 4 0 0
```
Outpuuuuuuuuut 1
26
```
**sample 2**
```
Inpuuuuuuuuuut 2
5 2 10 0 0 0 8 0 0 17 0 0 0 0 6 0 0
```
```
Outpuuuuuuuuut 2
29
```
### note
#### 範例 1
#### 範例 2
### 子題
```cpp=
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int p = 0, sum = 0;
vector<int> V;
int DFS(){
int u = V[p++], v;
if(!u) return 0;
for(int i = 0; i < 2 + (u % 1); i++){
v = DFS();
if(v) sum += abs(u - v);
}
return u;
}
signed main(){
int v;
while(cin >> v) V.pb(v);
DFS();
cout << sum << "\n";
return 0;
}
```
p3 generator
```cpp=
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
const int M = 100005;
vector<int> g[M];
deque<int> que;
void push(int x) {
que.push_back(x);
int i = rand() % que.size();
swap(que[i], que.back());
}
int pop() {
assert(que.size() > 0);
int x = que.front();
que.pop_front();
return x;
}
int root;
void dfs(int x) {
if (x != root) cout << ' ';
cout << x;
if (x == 0) return;
assert((int)g[x].size() == 2 + x % 2);
for (int v : g[x]) {
dfs(v);
}
}
int main() {
srand(clock());
vector<int> p;
for (int i = 1; i <= 100000; i++) p.push_back(i);
std::random_device rd;
std::mt19937 rg(rd());
shuffle(p.begin(), p.end(), rg);
push(p[0]);
push(p[0]);
if (p[0] % 2) push(p[0]);
int n = 1000 - rand() % 2;
for (int i = 1; i < n; i++) {
int u = p[i];
int par = pop();
g[par].push_back(u);
// cout << "par(" << u << ")=" << par << endl;
push(u);
push(u);
if (u % 2) push(u);
}
for (int i = 0; i < M; i++) {
while ((int)g[i].size() < 2 + i % 2) {
g[i].push_back(0);
}
shuffle(g[i].begin(), g[i].end(), rg);
}
root = p[0];
dfs(root);
return 0;
}
```
## P4 蓋步道 ???sec
:::info
子題配分？
n 的大小
Python 4s
C++ Java 1s
20%, n<=10, 高度 value <=10
20%, n<=300, 高度 value <=1000
60%, n<=300, 高度 <= 10^6
:::
### 題目
第四題 給一個 n\*n 的表格，表格上有不大於 1e6 的數字，然後你要找一條從左上走到右下的最短路徑，並讓該路徑上相鄰兩數的差的絕對值的最大值最小
### 輸入格式
n
matrix
### 輸出格式
**sample 1**
```
4
9 4 3 2
5 9 8 10
3 3 2 8
6 3 3 4
```
```
Outpuuuuuuuuut 1
```
**sample 2**
```
Inpuuuuuuuuuut 2
```
```
Outpuuuuuuuuut 2
```
:::danger
TODO p4 輸入移除行尾空格
:::
### note
我發現我給你的測資忘了輸出路徑長
#### 範例 1
#### 範例 2
### 子題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
using pii = pair<int, int>;
int bfs(int M, auto &vec) {
int n = vec.size();
auto vis = vector<vector<int>>(n, vector<int>(n, -1));
vis[0][0] = 0;
queue<pii> q;
q.emplace(0, 0);
while (q.size()) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 or nx >= n or ny < 0 or ny >= n)
continue;
if (vis[nx][ny] != -1)
continue;
if (abs(vec[x][y] - vec[nx][ny]) > M)
continue;
vis[nx][ny] = vis[x][y] + 1;
q.emplace(nx, ny);
}
}
return vis[n - 1][n - 1];
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
auto vec = vector<vector<int>>(n, vector<int>(n));
for (auto &vv : vec)
for (auto &v : vv)
cin >> v;
int L = -1, R = 1e6 + 5;
while (R - L > 1) {
int M = (L + R) / 2;
(bfs(M, vec) != -1 ? R : L) = M;
}
cout << R << '\n';
cout << bfs(R, vec) << '\n';
}
```
Sign in with Wallet
Connect another wallet