20200704 APCS 題目整理與詳解

整理者

CSY 教徒們
\CSY 教我/

觀念題上半場

題型分類

運行追蹤：9 題
程式填空：5 題
程式除錯：3 題
效能分析：1 題
基礎知識：2 題

重要考點

邏輯運算子：4 題
全域變數：2 題
後序運算：2 題
搜尋：1 題
merge：1 題
GCD：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

難題

使用輾轉相除法得到介於
$10^{6}$ ~
$2 \times 10^{6}$ 兩數之 GCD（最大公因數），至多需要的次數接近下列何者？

A. 50
B. 500
C. 5000
D. 50000

答案：A

將兩個各項係數皆不爲

0

且依照降冪排列的多項式相加，並去掉其係數爲

0

者。

本題是一題 debug 題，題目大致如下，由於筆者記憶力不好，因此變數名稱與原題稍有出入：

程式碼

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，因此若

s u m = 0

時，程式將會進入無窮迴圈，選擇答案中會使

s u m = 0

的選項即可。

欲在一個已排序好，大小為 n 的陣列 a[] 搜尋一個值 v 的位置。以下的code …(a)… 和 …(b)… 應填入什麼？
A.

i \leq j, (i + j) / 3

i \leq j, (i + 2 \times j) / 3

i < j, (i + j) / 2

i < j, (i + 2 \times j) / 3

程式碼














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。

題組

程式碼
















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);

問
$a [20]$
陣列中 11 的個數
如果要讓數到 11 的次數為 2500 在發現
$a [i] == 11$ 時，要將
$i$ 增加多少

觀念題下半場

題型分類

運行追蹤：11 題
程式填空：1 題
程式除錯：5 題
效能分析：1 題
基礎知識：2 題

重要考點

bubble sort（逆序數對）：3 題
極醜 code 閱讀：3 題
字串加密與處理：3 題
queue：2 題
整理式子後轉爲等差級數：3 題

難題

宣告多個變數 iTotal, iAlpha, iBeta, iGamma 於全域變數，並在多個函式中宣告同名區域變數，並進行相當亂的呼叫，整體 code 長度極長且可讀性極差，甚至需要滾動滑鼠滾輪才能找到各變數的值。

題組

將數字由大排到小 code 很醜

程式碼






















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;
            }
        }
    }
}

將數字依 sum of … sum of digit 由小排到大

程式碼





























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

拿出。

範例測資

Sample 1

Sample Input 1

Output 1

範圍

1 \leq m \leq 100, 1 \leq t \leq 100

解法

以一個陣列記錄每種物品當前個數，最後判斷兩個物品個數是否都大於 0。

Solution Code

Solution

//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;
}

Solution (python3)

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

示意圖

範例測資

Sample 1

1 2
1 -2
1 -1

Sample 2

3 3
2 -1
3 -2
3 1

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

Solution 2

#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];
	}
}

Solution 3

//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}

之總和。

每次兌換完，手中的點數就會全部被清空，為了盡快逃出，玩家只要點數夠，就會馬上兌換鑰匙。

最後玩家蒐集完鑰匙後，會停在哪個房間？

Sample

Sample Input
7 3
2 1 5 3 4 5 4
8 9 12
Sample Output
3

解釋：

走過

0, 1, 2

號房間後得到

8

點點數(

\geq 8

)，於

3

號房間得到第一把鑰匙，點數歸零。

走過

3, 4, 5

號房間後得到

12

點點數(

\geq 9

)，於

6

號房間得到第二把鑰匙，點數歸零。

走過

6, 0, 1, 2

號房間後得到

12

點點數(

\geq 12

)，於

3

號房間得到第三把鑰匙，點數歸零。

最後停在

3

號房間，輸出

3

。

示意圖

範圍

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] \geq

鑰匙點數

我們可以令前綴和

s [i] = a [0] + a [1] + . . . + a [i]

，接著，問題就轉換成，對於當前的位置

p

，找到一個最小的位置

x

，使得

s [x - 1] - s [p - 1] \geq

鑰匙點數。這個地方由於

s

序列具有單調性，我們可以用二分搜去處理。

那麼在環狀序列上，該如何做呢？

可以發現，若將原序列複製一次，也就是令

a [i + n] = a [i]

，則對於一個

p

找到的最小位置

x

，

x

n

就會是得到這一把鑰匙後，在環上的位置！

且由於題目保證鑰匙點數小於所有房間點數和，

x

最大就只會是

p + n

，因此將原序列複製一次後就相當足夠了。若本題沒有上述限制，其實也只要將需要的鑰匙點數預先 mod 所有房間點數和即可。

複雜度：

O (n + m l o g n)

Solution Code

Solution

//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 其中一種。
求所有的親代和子代最小的差距總和。

差距定義為兩相鄰節點之基因序列不同位置數量。

Sample 1

Sample Input 1

2 3
1 1 AAC
2 1 A@@

Sample Output 1

Sample 2

Sample Input 2

Sample Output 2

Sample 2 示意圖

範圍

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

的鹼基是否相同，不知道是否要將答案加一。因此，只儲存單一最佳答案並不能解決此一問題，考慮增加表格維度，如下：

設

d p [i] [j]

爲以

i

爲根，且

i

的鹼基編號爲

j

的子樹的最小修改次數，則可對於所有

i

的子節點

x

，枚舉

x

的鹼基編號

k

進行轉移。若

j \neq k

，則將變異數加一。

轉移式如下：

d p [i] [j] = Σ min_{0 < k < s} (d p [x] [k] + (j \neq k))

。

複雜度：

O (s^{2} n m)

s

爲鹼基種類數

可進一步儲存每個點以任意鹼基的最小值

m n [x]

，如此在轉移時只需使用

d p [i] [j] = m i n (m n [x] + 1, d p [x] [j])

即可，複雜度降爲

O (s n m)

。（感謝吳邦一教授提醒）

Solution Code

Solution1 O(s^2nm)

//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';
}

Solution2 O(snm)
















































//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';
}

20200704 APCS 題目整理與詳解

整理者

觀念題上半場

題型分類

重要考點

水題

難題

題組

觀念題下半場

題型分類

重要考點

難題

題組

實作題

p1

題敘

範例測資

範圍

解法

Solution Code

p2

題敘

範例測資

範圍

配分

解法（Solution 1）

解法（Solution 2）

Solution Code

p3

題敘

範圍

配分

解法

Solution Code

p4

題敘

範圍

配分

解法

Solution Code

Read more

台大暑期先修課程抵免申請教學