---
# System prepended metadata

title: 13th初階班下學期期末考題解
tags: [程設班考試]

---

# b167: 差分
### 提敘
如題，就是差分。

### 考點 
差分。

不放程式碼跟解講了，就完全是[講義](https://hackmd.io/@Cm2WYhkESReDzk7RvyH3Ww/SkUCY8nqC/https%3A%2F%2Fhackmd.io%2F%40PoteLiu%2FByR87A2Y1e)的東西，然後改變一下輸出的方式。

# b197: Pote Liu 冒險外傳 (2)
### 提敘
經典的空間分割，平常在寫數學應該也會遇到。

### 考點
考的是遞迴，我給了很多項，所以你就算不會寫也應該會把通式求出來吧。

啊我就不放遞迴式了，放了就等於給 $AC \; code$。

###### 然後我還是很想去故宮南院，下次到南部應該是畢旅，不知道有沒有機會。

# b205: 分子生物學的中心法則 (1)
### 提敘
就是在說 DNA 如何複製。

### 考點
其實我覺得我這題跟 `文字獄系列` 沒什麼差，只是你找到起點後要開始進行轉換，然後要記得最後要把字串反轉。

找到起點跟終點。
```cpp=
if(dna.find(oric) != string::npos && dna.find(ter) != string::npos){
    start = dna.find(oric) ;
    finish = dna.find(ter) ;
}
```

至於為什麼要用到 `string::npos` ，請去看[講義](https://hackmd.io/@Cm2WYhkESReDzk7RvyH3Ww/SkUCY8nqC/https%3A%2F%2Fhackmd.io%2F%40PoteLiu%2FBJZZ_x93R#find)。

接下來我的作法是把該段字串複製下來。
```cpp=
string target = "" ;
for (int i = start ; i < finish + ter.length() ; i++) {
    target += dna[i] ;
}
```

然後開始轉換，一樣再建一個字串然後進行判斷，我就不放了，再放乾脆直接給 $AC \; code$。

# b204: 分子生物學的中心法則 (2)
### 提敘
就是在說 DNA 如何轉錄。

### 考點
同上，不過 $A→T$ 變成 $A→U$。

所以這就是水題，因為跟上面那題一樣，你解一題可以拿兩題分數，超賺。

# b176: Pote Liu 冒險日記 (2)
### 提敘
好，這題的確題序有點長，因為我在出這題的時候是剛放寒假很閒。

他要你輸入一個二維陣列，然後再進行一些判斷。

### 考點
本題有提到一個名為**曼哈頓距離**的東西。
如果你有玩過 Mincraft 就知道他就是水的流動方法。
如果你有寫歷屆的 APCS 題目的話，你會知道這東西就是 [APCS 2024 6月的第二題 -- 電子畫布](https://zerojudge.tw/ShowProblem?problemid=o077)。

你會發現他的值是向外遞減，所以你可以知道我的邊界如下。

```cpp=
xg - g ;
yg - g ;
```

不過這樣你只能拿到最外圍的，所以很明顯你需要遍歷這個二維陣列，所以你會得到這個。

```cpp=
nxi = max(0, xg - g) ;
nxf = min(m, xg + g + 1) ;
nyi = max(0, yg - g) ;
nyf = min(n, yg + g + 1) ;
```

`nxi` 和 `nxf` 確定要遍歷的 `x` 範圍，不能超出界限 `[0, m)`。

`nyi` 和 `nyf` 確定要遍歷的 `y` 範圍，不能超出界限 `[0, n)`。

接著就在迴圈遍歷，曼哈頓距離公式是 $d(x,y) = |x_{1}-x_{2}|+|y_{1}-y_{2}|$ 。

把每一點跟 `(xg , yg)` 比，再把值放到陣列裡，記得值最小最小只會是 $1$ 。

然後你就把二維陣列的值建好了，接下來就是判斷輸入的該點需不需要躲避，結束。

# b207: 功德成聖啦 !
### 提敘
有 $n$ 間房子連在一起，一直往前走，每一個編號為 $i$ 的房間有 $p_i$ 個量的功德。

要分 $m$ 次把他的境界升到金仙中期，每次要蒐集 $q_i$ 個量的功德，從第一個進去的房間走到第 $(t+1) \; mod \; n$ 個房間，問最後會在哪裡。

### 考點
首先你會發現旁邊的時間被壓成 $0.1s$，你會知道這看起來是需要一些特殊的方法來做。

然後你看到他的配分分成兩個，還是特別奇怪的數字($2∗10^5$)，就更加確定了。

根據內容敘述會發現他要用到陣列的和，這代表你要做前綴和。

做完之後你驚訝的發現他具有**單調性**，又看到他在詢問位置，所以你知道你需要做二分搜。

```cpp=
int left = 0 , right = n ;
while(left < right){
	int middle = (left + right) / 2 ;
	if(target > pre[middle]) {
		left = middle + 1 ;	
	}
	else {
		right = middle ;
	}
}	
ans = left ;
```

最後記得要把 $ans \; mod \; n$ 。

# b203: 分子生物學的中心法則 (3)
### 提敘
就是在說 mRNA 如何轉譯。

### 考點
比較麻煩的一點是需要建表，可以用 `vector` 配 `pair` 但我是用 `unordered_map` (只是因為方便一點)

避免各位打到不爽我在這放表。(可能有其他方式但我只有這樣做。)
```cpp=
vector<pair<string, string>> codonlist = {
        {"AAA", "000001"}, {"AAU", "000010"}, {"AAC", "000011"}, {"AAG", "000100"},
        {"AUA", "000101"}, {"AUU", "000110"}, {"AUC", "000111"}, {"AUG", "001000"},
        {"ACA", "001001"}, {"ACU", "001010"}, {"ACC", "001011"}, {"ACG", "001100"},
        {"AGA", "001101"}, {"AGU", "001110"}, {"AGC", "001111"}, {"AGG", "010000"},
        {"UAA", ""}, {"UAU", "010001"}, {"UAC", "010010"}, {"UAG", ""},
        {"UUA", "010011"}, {"UUU", "010100"}, {"UUC", "010101"}, {"UUG", "010110"},
        {"UCA", "010111"}, {"UCU", "011000"}, {"UCC", "011001"}, {"UCG", "011010"},
        {"UGA", ""}, {"UGU", "011011"}, {"UGC", "011100"}, {"UGG", "011101"},
        {"CAA", "011110"}, {"CAU", "011111"}, {"CAC", "100000"}, {"CAG", "100001"},
        {"CUA", "100010"}, {"CUU", "100011"}, {"CUC", "100100"}, {"CUG", "100101"},
        {"CCA", "100110"}, {"CCU", "100111"}, {"CCC", "101000"}, {"CCG", "101001"},
        {"CGA", "101010"}, {"CGU", "101011"}, {"CGC", "101110"}, {"CGG", "101111"},
        {"GAA", "110000"}, {"GAU", "110001"}, {"GAC", "110010"}, {"GAG", "110011"},
        {"GUA", "110100"}, {"GUU", "110101"}, {"GUC", "110110"}, {"GUG", "110111"},
        {"GCA", "111000"}, {"GCU", "111001"}, {"GCC", "111010"}, {"GCG", "111011"},
        {"GGA", "111100"}, {"GGU", "111101"}, {"GGC", "111110"}, {"GGG", "111111"}
    };
```

然後步驟也是一樣，找到起點，開始**一格一格**跑，不是三格三格。

建一個字串放編好的字串，一格一格編直到找到終點。

關於找終點，這裡有一個好用的函式。
```cpp=
string codon = mRNA.substr(i, 3) ;
```

然後就可以輸出了。

# b195: 你就是我們班的 Spy 啊 !
### 提敘
對不起沒有重點。

### 考點
因為這題要敘述真的好難敘述，而且難發現規則，所以請看提示的圖片。

![image](https://hackmd.io/_uploads/ryJLgvc1gx.png)
還是要感謝 chrislaiisme，這題也是在他每日一題的程式裡發現的。

我覺得這題真的很精妙，首先你看完圖片會發現他有規律($2m$)，因此你開的陣列會是這樣。
```cpp=
vector<int> arr(m * 2 + 1 , 0) ;
```

你會有一個問題是該如何轉向，從他轉向是轉**某一段**的陣列可以發現，他就是要改變某一段的值，所以你可以想到要做差分，只需要改變重要的點，其他中間會透過前綴和累積出來。

```cpp=
while(n--){
    int p ;
    char d ;
    cin >> p >> d ;
    height += p ;

    if(p == 0) d = 'U' ;
    if(p == m) d = 'D' ;

    if(d =='U'){
        arr[0] ++ ;
        arr[m-p] -= 2 ;
        arr[m-p+m] += 2 ;
    }
    else if (d =='D'){
        arr[0] -- ;
        arr[p] += 2 ;
        arr[p+m] -= 2 ;
    }
}
```

然後你就可以做第一次的前綴和，代表把每一格的變化量累積成目前的傾斜。

而第二次前綴和是代表把傾斜累積成高度。

最後在遍歷所有高度，找出最大值。

###### 這題真的超漂亮的。

# b188: Pote Liu 冒險日記 (3)
### 提敘
找二維中最大子矩陣和。

### 考點
如果你寫過 Vandrin 的最大區間和，你就會發現其實這題他非常像，只是變成二維了。

所以他的做法就是先把二維陣列用前綴和壓成一維陣列。

```cpp=
for (int i = 1 ; i <= n ; i++){
    for (int j = 0 ; j < m ; j++){
        cin >> pre[i][j] ;
        pre[i][j] += pre[i-1][j] ;
    }
}
```

最外層兩個迴圈是固定位置，然後看成一維陣列做最大區間和。

```cpp=
for (int i = 1 ; i <= n ; i++ ){
    for (int j = i ; j <= n ; j++){
        dp = pre[j][0] - pre[i - 1][0] ;
        for (int k = 1 ; k < m ; k++) {
            val = pre[j][k] - pre[i - 1][k] ;
            dp = max(dp + val, val) ;
            ans = max(ans, dp) ;
        }
    }
}
```

# b196: 成為合格商人的第一課
### 提敘
找出一個可以以最小的損失賺到最多錢的方法。

### 考點
如果看不懂的話，畫出來你就會發現，這就是最大矩形面積， `stack` 經典題目。(啊我上課問你們要不要講好幾次都說不要。)

所以你要從左找比自己矮的右邊 ; 從右找比自己矮的左邊。

用 `stack` 從左到右掃，如果 `stack` 頂端比現在的高度高或一樣就 `pop` ，因為這個比自己高，不能當界線。

右邊同理，這裡不放了。
```cpp=
for (int i = 0; i < n; i++) {
    while (!stk.empty() && heights[stk.top()] >= heights[i]) {
        stk.pop();
    }
    left[i] = stk.empty() ? 0 : stk.top() + 1;
    stk.push(i);
}
```

然後把每一根柱子嘗試當作最矮的高度進行遍歷，就是 高度 $*$ 寬度 取最大值。