1. 巴士站牌
利用迴圈依序輸入 N 個點，紀錄前一個點的左標並利用 C++ 內建 abs() 計算曼哈論距離即可。
複雜度: O(n)
主要知識: 條件判斷與迴路 (conditional expressions and loop)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int px, py;
cin >> px >> py;
int mx = 0, mn = INT_MAX;
for(int i = 0;i < n-1;i++){
int x, y;
cin >> x >> y;
mx = max(mx, abs(px-x) + abs(py-y));
mn = min(mn, abs(px-x) + abs(py-y));
px = x;
py = y;
}
cout << mx << ' ' << mn << '\n';
}2. 運貨站
這題我們利用二維陣列來模擬哪些格子已經有方塊了。每次放入一個新的方塊，我們要由右至左判斷他會被放到哪裡。這題概念不難，只是實作比較麻煩。我把五個不同方塊寫成五個函式，看起來會比較清楚，建議在考試時也可以這樣，會比較好 debug。細節的部份就請看 Code。
複雜度: O(qc)
主要知識: 條件判斷與迴路 (conditional expressions and loop)，陣列與結構 (arrays and structures)
#include <bits/stdc++.h>
using namespace std;
int r, c;
bool taken[40][60]; // 0 based
int used; // 記錄放了幾格
int no;
void A(int j){
int i = c; // 最右邊開始 i 基準點是一個方塊的最右邊的 index
for(;i >= 0;i--){
if(i == 0 || taken[j][i-1] || taken[j+1][i-1] || taken[j+2][i-1] || taken[j+3][i-1]) break;
// 判斷可不可以往左移一格 如果那些格子已經有方塊就不行
}
// 因為我們上面如果下一格無法放就 break
// i 就是可以放的最左邊
if(i >= c) no ++; // 放不進去
else { // 放進去了，更新表格
taken[j][i] = true;
taken[j+1][i] = true;
taken[j+2][i] = true;
taken[j+3][i] = true;
used += 4;
}
}
void B(int j){
int i = c+2;
for(;i >= 2;i--){
if(i == 2 || taken[j][i-3]) break;
}
if(i >= c) no ++;
else {
taken[j][i] = true;
taken[j][i-1] = true;
taken[j][i-2] = true;
used += 3;
}
}
void C(int j){
int i = c+1;
for(;i >= 1;i--){
if(i == 1 || taken[j][i-2] || taken[j+1][i-2]) break;
}
if(i >= c) no ++;
else {
taken[j][i] = true;
taken[j+1][i] = true;
taken[j][i-1] = true;
taken[j+1][i-1] = true;
used += 4;
}
}
void D(int j){
int i = c+2;
for(;i >= 2;i--){
if(i == 2 || taken[j+1][i-3] || taken[j][i-1]) break;
}
if(i >= c) no ++;
else {
taken[j+1][i] = true;
taken[j+1][i-1] = true;
taken[j+1][i-2] = true;
taken[j][i] = true;
used += 4;
}
}
void E(int j){
int i = c+1;
for(;i >= 1;i--){
if(i == 1 || taken[j][i-1] ||taken[j+1][i-2] || taken[j+2][i-2]) break;
}
if(i >= c) no ++;
else {
taken[j][i] = true;
taken[j+1][i] = true;
taken[j+2][i] = true;
taken[j+1][i-1] = true;
taken[j+2][i-1] = true;
used += 5;
}
}
int main(){
int q;
cin >> r >> c >> q;
while(q--){
char ch;
int j;
cin >> ch >> j;
if(ch == 'A') A(j);
if(ch == 'B') B(j);
if(ch == 'C') C(j);
if(ch == 'D') D(j);
if(ch == 'E') E(j);
/*
建議考生可以用類似這樣的方法 debug
for(int i = 0;i < r;i++){
for(int j = 0;j < c;j++){
cout << taken[i][j] << " \n"[j == c-1];
}
}
*/
}
cout << r * c - used << ' ' << no << '\n';
}3. 石窟探險
- 這題給的輸入沒有給長度，所以要用到 while (cin >> ) 的方法
- 用到圖論和樹的概念，算是第三題中比較難的一題
我們想要先把圖建出來再計算要的答案。題目給的圖有點類似遞迴的概念。我們可以用到 C++ Stack 來解這題。
- 先考慮一個點，我們要等到他連出去的小孩全部走完才可以離開這個點。
- 我們維護一個 stack，裡面按照順序紀錄正在走訪的點們，最上面的點是最新的點，也是我們當前所在的點。
- 當我們加入一個新的點，他會是 stack 最上面的點的小孩，於是，我們把它加入 s.top() 的小孩集合中。
- 如果 s.top() 的小孩已經有 2 or 3 個 (看是奇數還是偶數) ，就代表這個點下面已經走完了，我們就可以離開這個點，把這個點從 stack 移除。
我們可以重複這些操作這樣模擬完整個圖，最後再利用我們存下來的資訊算出答案。
複雜度: O(n)
主要知識: 堆疊 (stacks)，樹狀圖 (tree)，函數呼叫與遞迴 (function call and recursion)，圖形 (graph)
#include <bits/stdc++.h>
using namespace std;
vector <int> G[100005]; // 紀錄每個點的小孩
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
stack <int> s;
int x;
while(cin >> x){
if(s.empty()) s.push(x);
else {
G[s.top()].push_back(x); // 將新的點加入當前點的小孩
if(s.top() % 2 == 1) {
if(G[s.top()].size() == 3) s.pop();
} else {
if(G[s.top()].size() == 2) s.pop();
}
// 判斷當前點是否已經走完
if(x != 0) s.push(x); // 將新的點加入走訪順序
}
}
long long res = 0;
for(int u = 1;u <= 100000;u++){
for(int v : G[u]){
if(v != 0) res += abs(u-v); // 計算所有 pair 的答案
}
}
cout << res << '\n';
}4. 蓋步道
看到表格，又看到只能往上下左右移動，應該會連想到圖論中的 dfs / bfs 吧!
這題要求 最大高度差最小的步道 。
在這種要求最大 X 最小，或是 最小 X 最大，可以透過二分搜 + 檢查的方法做。例如APCS考古題: 基地台
因為這種題目通常會有答案的單調性。用這題當例子，假如我們目前設置最大高度差為 5，並且是有路徑可以走的。那最大高度差是 6 也一定成立，7 也是 ，8 也是。因此，我們可以二分搜最小的那個高度差，在這題利用 bfs 檢查可不可行，找到最好的答案!
複雜度: O(n^2logh)
主要知識: 搜尋 (searching)，圖形 (graph)
#include <bits/stdc++.h>
using namespace std;
int a[305][305];
int vis[305][305];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int n;
int steps;
void bfs(int lim){ // bfs 檢查只用 lim 以下的高度差可不可以走到終點
queue <pair<int,int> > q;
q.push({1, 1});
vis[1][1] = 1;
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
if(x < 1 || x > n || y < 1 || y > n) continue;
for(int d = 0;d < 4;d++){
int nx = x+dx[d], ny = y+dy[d];
if(!vis[nx][ny] && abs(a[nx][ny] - a[x][y]) <= lim) {
q.push({nx, ny});
vis[nx][ny] = vis[x][y] + 1;
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
cin >> a[i][j];
}
}
int l = 0, r = 1e6;
while(l < r){ // 二分搜
int m = (l + r) / 2;
memset(vis, 0, sizeof(vis));
bfs(m);
if(vis[n][n]) r = m, steps = vis[n][n];
else l = m+1;
}
cout << l << '\n' << steps-1 << '\n';
}
發表迴響