# APCS 2023 十月份題解
如果各位有好好上課應該能寫出前一兩題
## [P1 機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)
### Subtask 1: $n = 3$
n = 3 的情況下不需要迴圈，我們開三個變數 food1, food2, food3 分別代表食物的位置，接著統計在左邊的有幾個、在右邊的有幾個，以及左邊 / 右邊的食物哪個多就輸出哪個，最後判斷最左邊／最右邊的食物。
程式能力需求：`I/O` `變數` `條件式`
### Subtask 2: 無其他限制
n 不是固定的，所以我們要開迴圈讀入每個食物的位置。
開一個變數 food 記錄當前食物的位置。接著開兩個變數 left, right，每次讀入食物的位置就判斷在左邊還是在右邊，加上去，以及 maxl, maxr 代表目前食物中最左邊、最右邊的。如果左邊比右邊多，那就輸出左邊有幾個食物、最左邊的食物。
程式能力需求: `I/O` `變數` `迴圈` `條件式`
#### 參考題解
```cpp=
#include <iostream>
using namespace std;
int main() {
int x, n;
cin >> x >> n;
int left = 0, right = 0, maxl = x, maxr = x;
int food;
for (int i = 0; i < n; i++) {
cin >> food;
if (food < x) {
left = left + 1;
if (food < maxl) {
maxl = food;
}
}
else {
right = right + 1;
if (food > maxr) {
maxr = food;
}
}
}
if (left > right) cout << left << ' ' << maxl;
else cout << right << ' ' << maxr;
}
```
## [P2 卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)
### Subtask 1: $n = 1$
n = 1 代表卡牌是一直線的，應該不難發現如果目前卡裡還存在可以取出的卡，那麼就取出，因為必須要取出才能給下一對可能存在的卡機會。
至於如何實作「取出」？
首先我們考慮如何記錄那些卡在卡堆中的情況：我們可以用一個一維陣列記錄每個卡牌的號碼，如果它被用過了那麼就將它設成 -1
拿範例測資來說：
- 陣列 card{0, 2, 3, 3, 0, 2, 5, 5}
- 拿掉 3
- 陣列 card{0, 2, -1, -1, 0, 2, 5, 5}
所以，我們開兩層迴圈：外層跑 m/2 次，因為最多有 m/2 對牌要移除
接著在內層尋找牌對，令兩個變數左牌、右牌 left, right，一開始令 left = 0，right = 1，left, right 不斷增加，如果右牌遇到 -1 就要一直向右找直到不是 -1，如果兩張牌相同就將它們設成 -1，接著繼續尋找下一個牌對
一樣拿範測來說
```
{0, 2, 3, 3, 0, 2, 5, 5}
l r
l r
l r 兩張牌相等，將它們設成 -1，break
{0, 2,-1,-1, 0, 2, 5, 5}
l r 從頭開始找
l r 右邊的牌是 -1，要繼續向右邊找到不是 -1 的牌
l r
l r 兩張牌不相等
...(下略)
```
要小心的是 right 在跑 while 迴圈時可能會超過 index，因此要特別判斷，總之這題實作要很注重細節
程式能力需求：`迴圈` `陣列` `模擬`
### Subtask 2: 無其他限制
和第一題思路類似，只是現在直的方向也要檢查了
#### 參考題解
```cpp
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int card[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> card[i][j];
}
}
int score = 0;
for (int t = 0; t < m * n / 2; t++) {
for (int i = 0; i < n; i++) {
for (int left = 0, right = 1; right < m; left = right, right = left + 1) {
while (card[i][right] == -1 && right < m) right++;
if (right >= m) break;
if (card[i][left] == card[i][right]) {
score += card[i][left];
card[i][left] = -1;
card[i][right] = -1;
}
}
}
for (int i = 0; i < m; i++) {
for (int left = 0, right = 1; right < n; left = right, right = left + 1) {
while (card[right][i] == -1 && right < n) right++;
if (right >= n) break;
if (card[left][i] == card[right][i]) {
score += card[left][i];
card[left][i] = -1;
card[right][i] = -1;
}
}
}
}
cout << score;
}
```
## [P3 搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
先講，這題的東西還沒教，不會非常正常
### Subtask 1: 沒有 X 水管
老實說我還真想不到這有什麼用，有這個 subtask 的特殊解的歡迎補充(?
### Subtask 2: 無其他限制
如果學過圖論應該一看就知道這是圖論題吧，看你想要怎麼處理而已
如果你會 SCC ，那很好，請用你的 SCC，只是你大概會被當毒瘤而且不會過。
為什麼不會過呢？如果你天真地把水管指向那當作有向邊，那會出現：
```
HI
IH
```
現在看出來為什麼不會過了嗎？因為忍者龜根本爬不過去，那條邊根本不存在。
回到正題，這題主要有兩種做法：DFS 和 DSU (併查集)
但是難不在 DFS 和 DSU ，難在建圖 (惱)。
用兩層迴圈吃圖進來，對於一個點 (x, y) 我們判斷上一排 (x, y - 1) 是否有向下連的邊，以及左邊的點 (x - 1, y) 有沒有向右連的邊
接著依照 (x, y) 對應到的字母判斷有沒有向上或向左邊的邊，如果兩個部分有對到就建邊。
至於如何不用寫一大堆 if 判斷連出去的方向呢？
第一個方法：對每個字母建表，這方法雖然比寫一堆 if 好，但也沒好到哪去
第二個方法：把那些可以向上連的字母存成一個陣列 / 字串、向下左右連同理，每次用迴圈掃過去看這個字母是不是存在於有向上下左右連的字母裡頭。可能類似這樣：
```cpp=
bool is_in(char c, const char s[], int size = 4) {
for (int i = 0; i < size; i++)
if (c == s[i]) return true;
return false;
}
...
if (is_in(graph[i][j], "XILJ") && is_in(graph[i - 1][j], "XIF7"))
add_edge({i, j}, {i - 1, j});
if (is_in(graph[i][j], "XHJ7") && is_in(graph[i][j - 1], "XHFL"))
add_edge({i, j}, {i, j - 1});
```
接著判斷每個連通塊裡面有幾個可以用的點，用一般 DFS(跑過去，戳到點就把這個連通塊的答案 +1) 或者用 DSU 都行
需求程式能力：`圖論` `DFS` `DSU`
#### 參考題解
by DSU
```cpp=
#include <iostream>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::pair;
using std::vector;
struct DSU {
vector<vector<pair<int, int>>> master;
vector<vector<int>> component;
int MAX = 1;
DSU(int m, int n) {
master.resize(m, vector<pair<int, int>>(n));
component.resize(m, vector<int>(n, 1));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
master[i][j] = {i, j};
}
const pair<int, int>& find(const pair<int, int>& target) {
#define x first
#define y second
if (master[target.x][target.y] == target) return target;
return master[target.x][target.y] = find(master[target.x][target.y]);
}
void combine(pair<int, int> a, pair<int, int> b) {
a = find(a), b = find(b);
if (a == b) return;
master[b.x][b.y] = a;
component[a.x][a.y] += component[b.x][b.y];
MAX = std::max(component[a.x][a.y], MAX);
}
int max() {
return MAX;
}
};
bool is_in(char c, const char s[], int size = 4) {
for (int i = 0; i < size; i++)
if (c == s[i]) return true;
return false;
}
int main() {
std::ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
DSU pipe(n, m);
vector<char> up(m, '0'); // 上一排
char left = 0; // 左邊
bool empty = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c != '0') empty = false;
if (is_in(c, "XILJ") && is_in(up[j], "XIF7"))
pipe.combine({i, j}, {i - 1, j});
if (is_in(c, "XHJ7") && is_in(left, "XHFL"))
pipe.combine({i, j}, {i, j - 1});
up[j] = c;
left = c;
}
left = '0';
}
if (empty) cout << 0;
else cout << pipe.max();
}
```
## [P4 投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
### Subtask 1: $k = 0, n\leq2000$
記錄前綴和(這樣就可以 O(1) 求區間和)，跑兩層迴圈枚舉進場時間、出場時間，對每個區間和取 Max
複雜度：$O(n^2)$
需求能力: `前綴和` `枚舉`
### Subtask 2: $k = 0$
最大區間和問題，聽說這題的做法有人叫反悔 greedy ？
我不知道那叫什麼，反正：
- 令 dp[i] 是以 i 為尾的最大後綴和
- dp[i+1] = max(dp[i] + a[i], 0)
轉移式在幹嘛？假設之後的後綴要考慮 dp[i] 時，如果 dp[i] < 0 一定比 dp[i] = 0 來得差，所以如果後綴出現負數時就不要取了
答案就會是 dp[i] 裡面最大的，因為你會發現 dp[i] 代表的是以 i 為右界的最大區間和
複雜度： $O(n)$
需求能力：`DP` `greedy`
### Subtask 3: 無其他限制
一樣考慮 dp：
- 令 dp[i][j] 是以 i 為尾、使用 j 面金牌的最大後綴和
- dp[i][0] = max(dp[i-1][0] + a[i] , 0)
- dp[i][j] = max(dp[i-1][j-1], dp[i-1][j] + a[i])
第一個轉移式很顯然，就是 subtask 2 的延伸
第二個轉移式分別代表在這格使用金牌以及不使用金牌的情況
所以跑兩層迴圈過去，一路上更新 dp[i][j] 就結束了，也可以寫成滾動形式。
複雜度：$O(nk)$
需求能力：`DP`
#### 參考題解
不滾動版本
```cpp=
#include <iostream>
using namespace std;
const int MAX_N = 2e5;
int dp[MAX_N][21];
int a[MAX_N];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
int ans = 0;
cin >> a[0];
dp[0][0] = max(a[0], 0);
for (int i = 1; i < n; i++) {
cin >> a[i];
dp[i][0] = max(dp[i - 1][0] + a[i], 0);
ans = max(ans, dp[i][0]);
}
for (int i = 1; i <= k; i++) {
dp[0][i] = max(0, dp[0][0]);
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j] + a[i]);
ans = max(ans, dp[i][j]);
}
}
cout << ans;
}
```
滾動版本
```cpp=
#include <iostream>
using namespace std;
int dp[21];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
int cur, pre, pre1;
int ans = -1;
for (int i = 0; i < n; i++) {
cin >> cur;
pre = dp[0];
dp[0] = max(0, dp[0] + cur);
ans = max(ans, dp[0]);
for (int j = 0; j < k; j++) {
pre1 = dp[j + 1];
dp[j + 1] = max(pre, dp[j + 1] + cur);
ans = max(ans, dp[j + 1]);
pre = pre1;
}
}
cout << ans;
}
```
Sign in with Wallet
Connect another wallet