---
image: https://i.imgur.com/jmQC6SP.png
---
# 20200704 APCS 題目整理與詳解
## 整理者
CSY 教徒們
\CSY 教我/
## 觀念題上半場
### 題型分類
- 運行追蹤：9 題
- 程式填空：5 題
- 程式除錯：3 題
- 效能分析：1 題
- 基礎知識：2 題
### 重要考點
- 邏輯運算子：4 題
- 全域變數：2 題
- 後序運算：2 題
- 搜尋：1 題
- merge：1 題
- GCD：1 題
### 水題
1. x1 = true
`(!x1 || !x2 ) && !x3 == true`
A. x2 True , x3 True
B. x2 True , x3 False
C. x2 False , x3 True
D. x2 False , x3 False
答案：D
### 難題
1. 使用輾轉相除法得到介於 $10^6$ ~ $2 \times 10^6$ 兩數之 GCD（最大公因數），至多需要的次數接近下列何者？
A. 50
B. 500
C. 5000
D. 50000
答案：A
2. 將兩個各項係數皆不爲 $0$ 且依照降冪排列的多項式相加，並去掉其係數爲 $0$ 者。
本題是一題 debug 題，題目大致如下，由於筆者記憶力不好，因此變數名稱與原題稍有出入：
:::spoiler 程式碼
```cpp
typedef struct term {
int power, val;
} poly;
int add(poly a1[],poly a2[],poly a3[],int n1,int n2){
int id1 = id2 = id3 = 0;
while(id1 < n1 && id2 < n2){
if(a1[id1].power == a2[id2].power){
int sum = a1[id1].val + a2[id2].val;
if(sum == 0) continue;
a3[id3].power = a1[id1].power;
a3[id3].val = sum;
id1 = id1 + 1;
id2 = id2 + 1;
}
else if(a1[id1].power > a2[id2].power){
a3[id3].power = a1[id1].power;
a3[id3].val = a1[id1].val;
id1 = id1 + 1;
}
else{
a3[id3].power = a2[id2].power;
a3[id3].val = a2[id2].val;
id2 = id2 + 1;
}
id3 = id3 + 1;
}
while(id1 < n1){
a3[id3].power = a1[id1].power;
a3[id3].val = a1[id1].val;
id1 = id1 + 1;
}
while(id2 < n2){
a3[id3].power = a2[id2].power;
a3[id3].val = a2[id2].val;
id2 = id2 + 1;
}
return id3;
}
```
:::
其實這有點像 merge_sort 中 merge 的過程，在盯了很久後會發現，問題出在這個 continue，在 continue 前並沒有將 idx1 與 idx2 加 1，因此若 $sum = 0$ 時，程式將會進入無窮迴圈，選擇答案中會使 $sum = 0$ 的選項即可。
3. 欲在一個已排序好，大小為 n 的陣列 a[] 搜尋一個值 v 的位置。以下的code ...(a)... 和 ...(b)... 應填入什麼？
A. $i \leq j, (i + j) / 3$
B. $i \leq j, (i + 2 \times j) / 3$
C. $i < j, (i + j) / 2$
D. $i < j, (i + 2 \times j) / 3$
:::spoiler 程式碼
~~~cpp=
int find_value(int a[], int n, int v) {
int i = 0, j = n - 1, k;
while (...(a)...) {
k = ...(b)...;
if (a[k] == v) {
return k;
} else if (a[k] < v) {
i = k + 1;
} else {
j = k - 1;
}
}
return -1
}
~~~
:::
答案：B
這題在考的是二分搜的細節觀念。程式碼中的 $i$ 和 $j$ 分別代表目前解的下界和上界，並且是左閉右閉 $[i, j]$ 的區間。因此如果選了 C 或 D，當 $v == a[n - 1]$ 的時候會找不到。在選項 A 中，有些位置會到不了（例如 $n-1$ 之類的），因此答案為 B。
### 題組
:::spoiler 程式碼
```cpp=
int n = 10000;
for(int i=0,j=0;i<n;i=i+1,j=j+3){
a[i] = j % 20;
}
int cnt = 0;
i = 0;
while(i<n){
if(a[i] == 11){
cnt = cnt + 1;
i = i + /*填空*/;
}
else{
i = i + 1;
}
}
printf("%d\n",cnt);
```
:::
1. 問 $a[20]$
2. 陣列中 11 的個數
3. 如果要讓數到 11 的次數為 2500 在發現 $a[i]==11$ 時，要將 $i$ 增加多少
## 觀念題下半場
### 題型分類
- 運行追蹤：11 題
- 程式填空：1 題
- 程式除錯：5 題
- 效能分析：1 題
- 基礎知識：2 題
### 重要考點
- bubble sort（逆序數對）：3 題
- 極醜 code 閱讀：3 題
- 字串加密與處理：3 題
- queue：2 題
- 整理式子後轉爲等差級數：3 題
### 難題
1. 宣告多個變數 iTotal, iAlpha, iBeta, iGamma 於全域變數，並在多個函式中宣告同名區域變數，並進行相當亂的呼叫，整體 code 長度極長且可讀性極差，甚至需要滾動滑鼠滾輪才能找到各變數的值。
## 題組
1. 將數字由大排到小 code 很醜
:::spoiler 程式碼
```cpp=
int B[10] = {/*1~10 random shuffle*/}
int h(int x){
return x;
}
int g(int x, int y){
return h(y) - h(x);
}
void f(int n){
int tmp, i, j;
for(i = 0; i < n - 1; i++){
for(j = 0; j < n - i - 1; j++){
if(g(B[i], B[j]) > 0){
tmp = B[i];
B[i] = B[j];
B[j] = tmp;
}
}
}
}
```
:::
2. 將數字依 sum of ....... sum of digit 由小排到大
:::spoiler 程式碼
```cpp=
int B[10] = {/*每一種 h(x) 會有兩個*/}
int h(int x){
int sum = 0;
do{
sum = sum + x % 10;
x = x / 10;
}
while(x / 10);
if(sum / 10) return h(sum);
else return sum;
}
int g(int x, int y){
return h(x) - h(y);
}
void f(int n){
int tmp, i, j;
for(i = 0; i < n - 1; i++){
for(j = 0; j < n - i - 1; j++){
if(g(B[i], B[j]) > 0){
tmp = B[i];
B[i] = B[j];
B[j] = tmp;
}
}
}
}
```
:::
## 實作題
題目來源：黃致皓、吳庭安
### p1
#### 題敘
給定二數字 $X, Y$，及多個購物清單，問至少買入各一 $X, Y$ 物之訂單有多少筆？買入一物的定義是，該物品加入購物籃的次數大於被拿出購物籃的次數。
購物清單格式：
每筆以 $0$ 結尾，結尾前的各數字若為正整數 $k$，代表將商品 $k$ 放入購物籃，若為 $-k$ 則代表將 $k$ 拿出。
#### 範例測資
:::spoiler Sample 1
Sample Input 1
```
1 8
5
1 8 0
5 6 0
2 7 0
8 1 0
33 22 0
```
Output 1
```
2
```
:::
#### 範圍
$1 \leq m \leq 100, 1 \leq t \leq 100$
#### 解法
以一個陣列記錄每種物品當前個數，最後判斷兩個物品個數是否都大於 0。
#### Solution Code
:::spoiler Solution
```cpp
//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int a,b,t,tmp,used[105];
int main(){
IOS
cin>>a>>b>>t;
int ans=0;
for(int i=0 ; i<t ; i++){
memset(used,0,sizeof(used));
while(cin>>tmp && tmp){
if(tmp>0)
used[tmp]++;
else
used[-tmp]--;
}
if(used[a]>0 && used[b]>0)
ans++;
}
cout<<ans<<"\n";
return 0;
}
```
:::
:::spoiler Solution (python3)
```python
res = 0
ls = list(map(int , input().strip().split(" ")))
r = int(input().strip())
for i in range(r):
s = list(map(int , (input().strip().split(" "))[:-1]))
for j in s:
if j < 0:
s.remove(abs(j))
if ls[0] in s and ls[1] in s:
res += 1
print(res)
```
:::
### p2
#### 題敘
給定 $n$ 顆六面骰子及 $m$ 筆操作，骰子一開始面向之位置固定（4 在前，1 在上），有三種操作：
- 交換任兩顆骰子
- 其中一顆骰子往前滾一次
- 其中一顆骰子往右滾一次
每筆操作格式如下：
$a$ $b$
若 $b$ 為正，代表將 $a$ $b$ 交換位置。
若 $b = -1$，將編號 $a$ 之骰子向前滾一面。
若 $b = -2$，將編號 $a$ 之骰子向右滾一面。
最後依序輸出每個骰子上方的點數。
一開始骰子：
| |3| | |
|-|-|-|-|
|5|1|2|6|
| |4| | |
:::spoiler 示意圖
:::
#### 範例測資
:::spoiler Sample 1
1 2
1 -2
1 -1
:::
:::spoiler Sample 2
3 3
2 -1
3 -2
3 1
:::
:::spoiler Samples 1&2 示意圖
:::
#### 範圍
$1 \leq n \leq 100, 1 \leq m \leq 100$
#### 配分
|分數|限制|
|:--:|:--:|
|20 %| n = 1 , 操作只有翻滾|
|80 %| 無特別限制|
#### 解法（Solution 1）
直接紀錄每個點數向前與向右轉後的點數為何，每次直接轉移過去即可
#### 解法（Solution 2）
由於對面相加爲 7，因此我們只需儲存其中上、前、右方之數字即可。向右翻轉時，原本的左方（7 - 右方數字）變爲新的上方，而原來的上方變爲新的右方，向前翻轉以此類推。
#### Solution Code
:::spoiler Solution 2
```cpp
#include<bits/stdc++.h>
using namespace std;
struct dice{
int Top;
int Front;
int Right;
};
dice arr[105];
int n,m;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
arr[i] = {1,4,2};
}
for(int i=1,a,b;i<=m;i++){
cin>>a>>b;
if(b==-1){
arr[a].Front = 7 - arr[a].Front;
swap(arr[a].Front,arr[a].Top);
}
else if(b==-2){
arr[a].Right = 7 - arr[a].Right;
swap(arr[a].Top,arr[a].Right);
}
else{
swap(arr[a],arr[b]);
}
}
for(int i=1;i<=n;i++){
cout<<arr[i].Top<<" \n"[i==n];
}
}
```
:::
:::spoiler Solution 3
```cpp
//Suifeng0214
//APCS 20200704 pB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 110;
int arr[MAX][10]; //arr[第幾顆骰子][第幾面]
signed main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= 6; j++){
arr[i][j] = j;
}
}
for (int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
if (b == -1){
int tmp = arr[a][4];
arr[a][4] = arr[a][1];
arr[a][1] = arr[a][3];
arr[a][3] = arr[a][6];
arr[a][6] = tmp;
}else if (b == -2){
int tmp = arr[a][6];
arr[a][6] = arr[a][2];
arr[a][2] = arr[a][1];
arr[a][1] = arr[a][5];
arr[a][5] = tmp;
}else{
swap(arr[a], arr[b]);
}
}
for (int i = 1; i <= n; i++){
cout << arr[i][1]; //輸出朝上的位置><
if (i!=n)cout << " ";
}
}
```
:::
### p3
#### 題敘
環狀迷宮有 $n$ 個房間，依序編號爲 $0$ ~ $n-1$。
玩家初始位置在房間 $0$，且只能依編號 $0,1 ...n-1,0,1$ 的環狀順序走。
第 $i$ 個房間有點數 $P_i$，每次離開房間 $i$，就可獲得 $P_i$ 點數。
逃脫迷宮方法：依序蒐集 $m$ 把鑰匙，第 $i$ 把鑰匙可用點數 $Q_i$ 兌換，保證所有 $Q_i$ 都 $\leq$ $P_i$ 之總和。
每次兌換完，手中的點數就會全部被清空，為了盡快逃出，玩家只要點數夠，就會馬上兌換鑰匙。
最後玩家蒐集完鑰匙後，會停在哪個房間？
:::spoiler Sample
> Sample Input
> ```
> 7 3
> 2 1 5 3 4 5 4
> 8 9 12
> ```
> Sample Output
> ```
> 3
> ```
解釋：
走過 $0,1,2$ 號房間後得到 $8$ 點點數($\ge8$)，於 $3$ 號房間得到第一把鑰匙，點數歸零。
走過 $3,4,5$ 號房間後得到 $12$ 點點數($\ge9$)，於 $6$ 號房間得到第二把鑰匙，點數歸零。
走過 $6,0,1,2$ 號房間後得到 $12$ 點點數($\ge12$)，於 $3$ 號房間得到第三把鑰匙，點數歸零。
最後停在 $3$ 號房間，輸出 $3$。
:::
:::spoiler 示意圖
:::
#### 範圍
$1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 2 \times 10^4$
#### 配分
|分數|限制|
|:--:|:--:|
|20%|$1\leq n,m \leq 100$|
|80%|無特殊限制|
#### 解法
先假設本題是在一個正常序列上，要怎麼去做呢？
題目要求的是找到最小的 x 使得 $a[i] + a[i+1] ..... +\: a[x-1] \ge$ 鑰匙點數
我們可以令前綴和 $s[i] = a[0] + a[1]+ ... +\: a[i]$，接著，問題就轉換成，對於當前的位置 $p$，找到一個最小的位置 $x$，使得 $s[x-1]-s[p-1]\ge$ 鑰匙點數。這個地方由於 $s$ 序列具有單調性，我們可以用二分搜去處理。
那麼在環狀序列上，該如何做呢？
可以發現，若將原序列複製一次，也就是令$a[i+n] = a[i]$，則對於一個 $p$ 找到的最小位置 $x$， $x$ % $n$ 就會是得到這一把鑰匙後，在環上的位置！
且由於題目保證鑰匙點數小於所有房間點數和，$x$ 最大就只會是 $p+n$，因此將原序列複製一次後就相當足夠了。若本題沒有上述限制，其實也只要將需要的鑰匙點數預先 mod 所有房間點數和即可。
複雜度：$O(n + m\: log\:n)$
#### Solution Code
:::spoiler Solution
~~~cpp
//by 8e7
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main() {
int n, m;
cin >> n >> m;
ll room[n], key[m], pref[2 * n];
for (int i = 0;i < n;i++) cin >> room[i], pref[i] = pref[i + n] = room[i];
for (int i = 0;i < m;i++) cin >> key[i];
for (int i = 1;i < 2 * n;i++) {
pref[i] += pref[i - 1];
}
int ind = 0;
for (int i = 0;i < m;i++) {
ll left = ind ? pref[ind - 1] : 0;
ind = (lower_bound(pref, pref + 2 * n, left + key[i]) - pref) + 1;
ind %= n;
}
cout << ind << endl;
}
~~~
:::
### p4
#### 題敘
有 $n$ 條 RNA 病毒，各自擁有一個 RNA 序列，且長度皆為 $m$。
每條的輸入格式為下：
( 自身編號 , 親代編號 , RNA 序列 )
若自身編號等於親代編號則是根源。
其中自身編號為 $1$ ~ $n$
RNA 序列為由 A、U、C、G、@ 組成的字串。@ 為未知的字元，可任意為 A、U、C、G 其中一種。
求所有的親代和子代最小的差距總和。
- 差距定義為兩相鄰節點之基因序列不同位置數量。
:::spoiler Sample 1
Sample Input 1
```
2 3
1 1 AAC
2 1 A@@
```
Sample Output 1
```
0
```
:::
:::spoiler Sample 2
Sample Input 2
```
6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A
```
Sample Output 2
```
1
```
:::
:::spoiler Sample 2 示意圖
```graphviz
digraph hierarchy {
nodesep=1.0
node [color=blue,fontname=Courier,shape=box]
edge [color=Blue, style=dashed]
"1, 1, @"->{"2, 1, @" "3, 1, C" "4, 1, C"}
"2, 1, @"->{"5, 2, A", "6, 2, A"}
}
```
:::
#### 範圍
$1\leq n \leq 1000, 1\leq m \leq 80$
#### 配分
|分數|限制|
|:-:|:-:|
|20 %|無任何 @ 字元，且對於每個非根源節點 $i$，其親代 $j$ 之編號皆小於它|
|40 %|對於每個非根源節點 $i$，其親代 $j$ 之編號皆小於它|
|40 %| 無特別限制|
#### 解法
首先觀察到，每個位置的字元互不相干，因此我們只需要解決長度 = 1 的問題 m 次就好了。
再來，對於一個點的各個子節點所形成的子樹，他們的答案互不相關。也就是說，假設 $A$ 有兩個子樹 $B$、$C$，$B$ 選擇的鹼基是什麼完全不會影響到 $C$ 的最佳選擇，$B$、$C$ 的最佳選擇皆只與其子樹與父節點 $A$ 有關，因此我們考慮使用樹形動態規劃技巧 ( 樹 DP ) 來解決問題。
那要儲存什麼值呢？先以遞迴方式取得 $B$ 子樹的最佳答案，接著直接從 $A$ 進行轉移？這樣做的話會發現，你無法判斷 $A$ 的鹼基與 $B$ 的鹼基是否相同，不知道是否要將答案加一。因此，只儲存單一最佳答案並不能解決此一問題，考慮增加表格維度，如下：
設 $dp[i][j]$ 爲以 $i$ 爲根，且 $i$ 的鹼基編號爲 $j$ 的子樹的最小修改次數，則可對於所有 $i$ 的子節點 $x$ ，枚舉 $x$ 的鹼基編號 $k$ 進行轉移。若 $j \neq k$，則將變異數加一。
轉移式如下：
$dp[i][j] = \Sigma\: \min\limits_{0<k<s} (dp[x][k] + (j\neq k))$ 。
複雜度：$O(s^2 nm)$ $s$ 爲鹼基種類數
可進一步儲存每個點以任意鹼基的最小值 $mn[x]$，如此在轉移時只需使用 $dp[i][j] = min(mn[x]+1,dp[x][j])$ 即可，複雜度降爲 $O(snm)$。（感謝吳邦一教授提醒）
#### Solution Code
:::spoiler Solution1 O(s^2nm)
```cpp
//by emanlaicepsa
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define pb push_back
#define all(n) (n).begin(),(n).end()
using namespace std;
vector<int> E[1005];
string s[1005];
string ord = "AUCG";
ll dp[1005][4],n,m;
void dfs(int x,int c){
for(auto &i:E[x]) dfs(i,c);
for(int i=0;i<4;i++){
if(s[x][c] != '@' && s[x][c] != ord[i]){
dp[x][i] = 1e9;
continue;
}
for(auto &j:E[x]){
ll mn = 1e9;
for(int k=0;k<4;k++){
mn = min(mn,dp[j][k] + (k!=i));
}
dp[x][i] += mn;
}
}
}
signed main(){
IOS;
cin>>n>>m;
for(int i=1,a,b;i<=n;i++){
cin>>a>>b;
cin>>s[a];
if(a!=b)E[b].pb(a);
}
ll ans = 0;
for(int i=0;i<m;i++){
memset(dp,0,sizeof(dp));
dfs(1,i);
ans += *min_element(dp[1],dp[1]+4);
}
cout<<ans<<'\n';
}
```
:::
:::spoiler Solution2 O(snm)
```cpp=
//by emanlaicepsa
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define pb push_back
#define all(n) (n).begin(),(n).end()
using namespace std;
vector<int> E[1005];
string s[1005];
string ord = "AUCG";
ll dp[1005][4],n,m;
ll dp2[1005];
void dfs(int x,int c){
for(auto &i:E[x]) dfs(i,c);
for(int i=0;i<4;i++){
if(s[x][c] != '@' && s[x][c] != ord[i]){
dp[x][i] = 1e9;
continue;
}
for(auto &j:E[x]){
dp[x][i] += min(dp2[j]+1,dp[j][i]);
}
}
dp2[x] = *min_element(dp[x],dp[x]+4);
}
signed main(){
IOS;
cin>>n>>m;
for(int i=1,a,b;i<=n;i++){
cin>>a>>b;
cin>>s[a];
if(a!=b)E[b].pb(a);
}
ll ans = 0;
for(int i=0;i<m;i++){
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
dfs(1,i);
ans += *min_element(dp[1],dp[1]+4);
}
cout<<ans<<'\n';
}
```
:::
Sign in with Wallet
Connect another wallet