# APCS 2024 年 6 月 AA 競程 dreamoon 老師的參考作法
每題都有非常多種可獲得滿分的解法，但由於這是寫給 AA 競程的學員看的，所以會強調每題和課程內容的關聯性。其中，
A, B 兩題只使用語法班教過的知識來寫
C 題使用競程入門班教過的知識來解
D 題則是使用 Level 1 教過的知識來解
## A. [特技表演](https://zerojudge.tw/ShowProblem?problemid=o076)
此題是 Level 0 語法班程度即可做出來的題目，以下提供兩種思路。
### 方法一
此題 $n$ 至多只有 $100$，所以就算是三層 for 迴圈的作法也可以通過。
最暴力的方法就是枚舉所有可能的區間，找出所有嚴格遞減的區間，看哪個長度最長，該長度就是答案，這樣的作法的程式碼如下：
```cpp=
#include<iostream>
using namespace std;
bool is_decresing(int h[], int n) {
for(int i = 1; i < n; i++) {
if(h[i] > h[i - 1]) return 0;
}
return 1;
}
int main() {
int n;
cin >> n;
int h[101];
for(int i = 1; i <= n; i++){
cin >> h[i];
}
int ans = 0;
for(int len = 1; len <= n; len++) {
for(int left = 1; left + len - 1 <= n; left++) {
if(is_decresing(h + left, len)) ans = len;
}
}
cout << ans << '\n';
}
```
### 方法二
在語法版時我們有教過一種技巧是不需要像上個作法那樣使用陣列把所有 h 值儲存下來後才算答案，而是每讀入一個 h 值，就更新一些和答案有關的資訊，例如說，這題需要知道最長遞減區間的長度，那我們只要在迴圈外維護一個變數，代表枚舉到位置 $i$ 時，它的值會是區間右界在位置 $i$ 的最長遞減的區間長度，同時也要維護上個位置的 $h$ 值，這樣我們就能只用一個 for 迴圈解決這題了。
細節請參考程式碼
```cpp=
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
int last_h = 0; // 維護上個位置的 h 值
int len = 0; // 當前右界在位置 i 的最長遞減區間長度
int ans = 0; // 當前已知最長遞減區間長度
for(int i = 1; i <= n; i++){
int h;
cin >> h;
if(h < last_h) { // 若當前 h 值小於上個位置的 h 值，則右界在位置 i 的最長遞減區間長度為上個位置的值加 1
len++;
} else { // 否則為 1
len = 1;
}
if(ans < len) ans = len;
last_h = h;
}
cout << ans << '\n';
}
```
## B. [電子畫布](https://zerojudge.tw/ShowProblem?problemid=o077)
此題在語法班中有個寫法類似的題：[P. 金幣數量 (4 pt)](https://codeforces.com/group/E2QZG7dbgT/contest/489039/problem/P)，而 APCS 考古題也曾經有個類似的題：[APCS202306 P2特殊位置](https://zerojudge.tw/ShowProblem?problemid=k732)。
這兩道類似的題都是要先讀入一個二維陣列，然後要做「找到距離某個格子不超過 r 的那些格子，並做一些事情」這樣的事情好多次。
而要「找到距離某個格子不超過 r 的那些格子」其實只要暴力枚舉所有合法座標，用 if 判斷式檢查就夠了，這是個比較簡單的做法。
而此題也是這樣的題目，每次操作，要找到距離 $(r, c)$ 不超過 $t$ 的所有格子，對這些滿足條件的格子要做的事情就是把格子上的值增加 $x$。
細節請參考以下程式碼。
### 參考程式碼
```cpp=
#include<iostream>
#include<cmath>
using namespace std;
const int SIZE = 20;
int main() {
int H, W, N;
cin >> H >> W >> N;
int a[SIZE][SIZE] = {};
while(N--) {
int r, c, t, x;
cin >> r >> c >> t >> x;
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
if(abs(i - r) + abs(j - c) <= t) a[i][j] += x;
}
}
}
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
cout << a[i][j];
if(j + 1 < W) {
cout << ' ';
} else {
cout << '\n';
}
}
}
}
```
## C. [缺字問題](https://zerojudge.tw/ShowProblem?problemid=o078)
:::danger 警告
此題 zero judge 上的測試資料很弱，網路上有非常多題解是 $O(k^L \times |S|)$ 時間複雜度的作法，這樣的作法理應超時。
:::
### 參考作法
先定義一些參數：給定的字母集大小為 $K$，給定的字串 為 $S$，長度為 $W$，題目另外還給定一個正整數 $L$，此題是在求字典序最小且沒出現過的長度為 $L$ 的子字串。
題目有個限制可以讓我們使用競程入門班以內的知識即可解出，也就是 $K^L \le 6 \times 10^5$ 這個限制，這呼應到競程入門班教過的「觀察到數字範圍很小」。
有了這個限制的話，我們就可以把所有長度為 $L$ 的子字串當作是一個 $K$ 進制的數，給定的字母集就依序對應到數字 $0, 1, 2, \ldots, K - 1$，例如說，字母集若是 $\{a,c,m\}$, $L = 2$，那麼所有字串和十進制數字的對應如下：
aa -> 0
ac -> 1
am -> 2
ca -> 3
cc -> 4
cm -> 5
ma -> 6
mc -> 7
mm -> 8
這部分是對應到競程入門班教過的 $X$ 進制轉換成整數資料型態。
於是問題就變成把 $S$ 所有長度為 $L$ 的子字串對應到整數後，找出最小的沒出現的非負整數，再把該整數轉回字串。
而找到最小的沒出現過的整數正是競程入門班習題：[mex 函數 (5 pt)](https://codeforces.com/group/v6xrkeacMs/contest/497139/problem/D) 在求的東西，只要開個陣列紀錄哪些數字出現過，之後找到此陣列最小的索引值，滿足該索引值位置的值為 $0$，再把此索引值轉換回使用此題的字母集產生的 $K$ 進制字串即可。
### 參考程式碼
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
const int SIZE = 1'000'000;
void solve() {
string alphabet_set;
int L;
string S;
vector<int> appeared(SIZE);
vector<int> to(128);
cin >> alphabet_set >> L >> S;
for(int i = 0; i < SZ(alphabet_set); i++) {
to[alphabet_set[i]] = i;
}
for(int i = 0; i + L <= SZ(S); i++) {
int v = 0;
for(int j = 0; j < L; j++) {
v = v * SZ(alphabet_set) + to[S[i + j]];
}
appeared[v] = 1;
}
int v = 0;
while(appeared[v]) v++;
string ans;
for(int i = 0; i < L; i++) {
ans += alphabet_set[v % SZ(alphabet_set)];
v /= SZ(alphabet_set);
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
solve();
}
```
## D. [最佳選擇](https://zerojudge.tw/ShowProblem?problemid=o079)
先定義一些變數：$sum$ 是 $n$ 個數字的和，原來的 $n$ 個數的奇數數量減去偶數的數量是 $parity\_diff$。
---
此題可以移除的數是兩側的數，處理起來比較麻煩，所以我們可以改成以下問題：
求數字和最小的區間，滿足：
1. 數字和 $\ge sum - k$
2. 區間裡奇數數字數量 - 偶數數字數量 $= parity\_diff$
而對於這種和區間內數字和有關的問題，我們在 Level 1 就常常提到：看到連續和就可以聯想看看轉換成兩個前綴和之差是否思考起來更簡單，並且此題是要求區間內奇數數量和偶數數量的差固定，這樣的概念和 Level 1 的作業：[CF873 B. Balanced Substring](https://codeforces.com/problemset/problem/873/B) 類似，所以我們也可以用類似概念：把前綴和的「奇數數量 - 偶數數量的值」當作 vector 陣列 $prefix\_sum$ 的索引值，也就是說 $prefix\_sum[i]$ 儲存所有滿足 「奇數數量 - 偶數數量的值」為 $i$ 的前綴的前綴和，並且這些前綴和是由小到大放在 vector 裡。有這樣的 vector 陣列之後，只要枚舉區間左界 $l$，，令前 $l-1$ 個數總和為 $s$，「奇數數量 - 偶數數量」為 $d$，那麼就只要在 $prefix\_sum[d + parity\_diff]$ 找到 $\ge max(0, s + sum - k)$ 的最小值即可，這件事可用 lower_bound 解決，也可以用雙指標來做到線性的時間複雜度。
### 易犯錯誤
1. 要小心找 $k$ 的值可能大於輸入給的 $n$ 個數字的和，此時 $sum - k$ 會小於 $0$，每有把它和 $0$ 取 max 的話(也就是說示範程式碼少了第 23 行)，就會找到右界比左界更左邊的區間(這根本不叫區間就是了) 導致答案出錯。
2. 以下示範程式碼若改用 int 是有機會發生整數溢位的(發生在 28 行, 但 zerojudge 上沒有這樣的測資)。
### 參考程式碼
1. lower_bound 寫法
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
using ll = long long;
void solve() {
int n;
ll k;
cin >> n >> k;
vector<vector<ll>> prefix_sum(2 * n + 1);
int parity_diff = 0;
prefix_sum[n].push_back(0);
ll sum = 0;
for(int i = 1; i <= n; i++) {
ll x;
cin >> x;
sum += x;
parity_diff += (x % 2 ? 1 : -1);
prefix_sum[n + parity_diff].push_back(sum);
}
k = max(0ll, sum - k); // 在此行開始變更 k 的意思，變為保留的區間內數字和至少要 k 那麼大
ll mi = sum;
for(int i = 0; i <= 2 * n; i++) {
if(i + parity_diff < 0 || i + parity_diff > 2 * n) continue;
for(ll x: prefix_sum[i]) {
auto it = lower_bound(prefix_sum[i + parity_diff].begin(), prefix_sum[i + parity_diff].end(), x + k);
if(it != prefix_sum[i + parity_diff].end()) mi = min(mi, *it - x);
}
}
cout << sum - mi << '\n';
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
solve();
}
```
2. 雙指標寫法
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
using ll = long long;
void solve() {
int n;
ll k;
cin >> n >> k;
vector<vector<ll>> prefix_sum(2 * n + 1);
int parity_diff = 0;
prefix_sum[n].push_back(0);
ll sum = 0;
for(int i = 1; i <= n; i++) {
ll x;
cin >> x;
sum += x;
parity_diff += (x % 2 ? 1 : -1);
prefix_sum[n + parity_diff].push_back(sum);
}
k = max(0ll, sum - k);
ll mi = sum;
for(int i = 0; i <= 2 * n; i++) {
if(i + parity_diff < 0 || i + parity_diff > 2 * n) continue;
auto &vi = prefix_sum[i + parity_diff];
auto it = vi.begin();
for(int x: prefix_sum[i]) {
while(it != vi.end() && *it < x + k) it++;
if(it != vi.end()) mi = min(mi, *it - x);
}
}
cout << sum - mi << '\n';
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
solve();
}
```
Sign in with Wallet
Connect another wallet