# 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 啊 !
### 提敘
對不起沒有重點。
### 考點
因為這題要敘述真的好難敘述，而且難發現規則，所以請看提示的圖片。
還是要感謝 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);
}
```
然後把每一根柱子嘗試當作最矮的高度進行遍歷，就是 高度 $*$ 寬度 取最大值。
Sign in with Wallet
Connect another wallet