# b151: 在程設班締造出美好的回憶 !(easy version)
### 提敘
已知 $ab=ac$ ，在知道 $a$ 和 $b$ 的情況下，$c$ 等於多少?
### 考點
若 $a,b$ 其一等於 $0$ ，則 $c \in \mathbb{R}$ 。
# b152: 我要成為幾何大師 !
### 提敘
已知 $θ_1$ 求 $θ_2$ 。
### 考點
做兩次[弦切角](https://zh.wikipedia.org/wiki/%E5%BC%A6%E5%88%87%E8%A7%92%E5%AE%9A%E7%90%86)。
# b154: 商高定理好好玩(easy version)
### 提敘
在 $a < b < c$ 且 $a$ 為奇數又 $b,c$ 差 $1$ 時，求 $b,c$ 。
### 考點
自行推導公式可得 : $b =\frac{a^{2}-1}{2} \; , \; c =\frac{a^{2}+1}{2}$ 。
# b155: 《拆彈專家》
### 提敘
大約等於沒東西。
### 考點
和 `a830 排雷` 差不多樣子。
在建好一陣列後，是輸入炸彈位置，要表示炸彈的方式有很多種，我可以用字元、不為 $1$ ~ $8$ 的數(看下面的踩地雷的格子算法。) 或是布林數，為了方便理解(我自己。)，我選擇用布林數。
```cpp=
//在輸入完炸彈後我知道它的座標。
bomb[x][y] = true;
```
踩地雷的格子算法 : 該點的周圍 $8$ 格有 `n` 顆地雷，那麼該格的數字就是 `n` 。反過來說，在地雷的周圍 $8$ 格會 `+1` (如果該格非地雷的話。)，因此我們可以得出以下結論。
```cpp=
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if (!bomb[i][j]) {
arr[i][j]++;
}
}
}
```
在這裡會遇到一個問題，特判邊界，我的炸彈可能是在這陣列的邊界，那麼我依照我上面的執行就會 `RE` ，我有兩種方式來解決這種情況。
第一種 : 擴增陣列大小來迴避，若執行上面之程式，依舊會計算到定義上的邊界，但因為有擴增，所以不會 `RE` 。
```cpp=
vector<vector<int>> arr(m+2, vector<int>(n+2, 0));
vector<vector<bool>> bomb(m+2, vector<bool>(n+2, false));
```
如果說我原本的陣列長這樣(紅色範圍為我實際的 `m,n` 大小。) :
那麼我`+2` 會變成這樣，配合我測資所說的「左上角第一格為 $(1,1)$。」，所以我的變數不需再多進行改變。(原本陣列需在 `x,y` 軸 `-1`。):
第二種 : 進行邊界特判。
```cpp=
// 在迴圈內。
if (i < 0 || i >= m) {
continue;
}
// 還有一個。
if (j < 0 || j >= n) {
continue;
}
```
然後接著就是輸出執行完的程式了，結束。
# b168: Pote Liu 冒險日記 (1)
### 提敘
翻譯 :
最初面朝右，若前進方向數值高於該格，向右轉，直至四周皆大於該格。
有幾分是在 `int` 範圍，有一筆是一維陣列，但他的值我放超過 `long long` 。
### 考點
轉向，就是二維陣列他的資料該怎麼進行移動。
```cpp=
if (face == 0) {
//程式碼。
}
else{
face = 1;
}
//已此類推，連續轉四次都沒有移動就結束。
```
需要特判邊界。(這裡就不寫了在 `b155:《拆彈專家》` 有說過了。)
然後第二個重點是大數運算，這也算是一個不小的觀念了，可以去看看別人的講義，我這裡稍微的提一下就是轉字串用數學直式的概念處理。
:::spoiler 應該是有用的東西 (哪天我完全搞懂再寫寫看。)
[Chu-Ling Ko 的大數運算筆記](https://hackmd.io/@CLKO/r1KtmuMdf?type=view)
[高中生解題系統的 a021. 大數運算 裡面有別人寫的大數加法](https://zerojudge.tw/ShowProblem?problemid=a021)
[number 演算法筆記](https://web.ntnu.edu.tw/~algo/Number.html)
:::
# b167: 差分
### 提敘
如題，就是差分。
### 考點
差分。
不放程式碼跟解講了，就完全是[講義](https://hackmd.io/@Cm2WYhkESReDzk7RvyH3Ww/SkUCY8nqC/https%3A%2F%2Fhackmd.io%2F%40PoteLiu%2FByR87A2Y1e)的東西，然後改變一下輸出的方式。
# b170: Pote Liu 冒險外傳 (1)
### 提敘
已知起點求邊界。
### 考點
根據題目敘述，宇宙是會一直變大的，所以你找不到他**向外擴**的邊界，但是你反過來想想，起點的後面是什麼。
然後我發現測資有點大所以此題會有需要用到IO優化。
```cpp=
int main() {
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//程式碼。
}
```
# b175: 到大安森林公園跳哥薩克舞
### 提敘
取重點:
小劉贏的時候加: $(q−p)∗0.05+25$ ，若 $≤0$ 則加 $1$ 。
小劉輸的時候加: $(q−p)∗0.05−25$ ，若 $≥0$ 則扣 $0$ 。
### 考點
這題我是想考 `vector` 加 `pair` ，但單純的用傳統陣列一樣可以解。
首先是宣告。
```cpp=
vector<pair<int, int>> arr(n);
```
就這樣，結束。
然後要套入公式，會分為兩種狀況，我不需要小李就有最大值和我需要小李才有最大值。
為何?
公式下去的值有四種可能，`+1` 、 `-0` 、 加符合公式的值、減符合公式的值，如此便有機會在某時間的暫時最大值碰到了減符合公式的值然後變的超小。若我在需要小李的情況皆遇到此問題，那麼不需要小李反而有機會才是最大值。
所以第一步，不需要小李的情況 :
```cpp=
//當然有更好的寫法只是我習慣這樣。
#define F first
#define S second
for(int y = 0; y < n; y++) {
int d = (arr[y].S - tmp) / 20;
if(arr[y].F == 1){
d = max(d + 25, 1); //我這裡是用max跟min當然也可以用if進行判斷。
}
else{
d = min(d - 25, 0);
}
tmp += d;
}
```
然後第二步和第一步差不多(我直接複製上面的所以我要進行下面動作。) :
```cpp=
if(arr[x].F == 0) {
arr[x].F = 1;
//程式碼。
arr[x].F = 0; //記得要改回來。
}
```
然後就輸出。
# 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$ 。
然後你就把二維陣列的值建好了，接下來就是判斷輸入的該點需不需要躲避，結束。
# 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] ;
tmp = max(tmp + val, val) ;
ans = max(ans, tmp) ;
}
}
}
```
# 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 ;
}
}
```
然後你就可以做第一次的前綴和，代表把每一格的變化量累積成目前的傾斜。
而第二次前綴和是代表把傾斜累積成高度。
最後在遍歷所有高度，找出最大值。
###### 這題真的超漂亮的。
# 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);
}
```
然後把每一根柱子嘗試當作最矮的高度進行遍歷，就是 高度 $*$ 寬度 取最大值。
# b197: Pote Liu 冒險外傳 (2)
### 提敘
經典的空間分割，平常在寫數學應該也會遇到。
### 考點
考的是遞迴，我給了很多項，所以你就算不會寫也應該會把通式求出來吧。
啊我就不放遞迴式了，放了就等於給 $AC \; code$。
###### 然後我還是很想去故宮南院，下次到南部應該是畢旅，不知道有沒有機會。
# 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) ;
```
然後就可以輸出了。
# b204: 分子生物學的中心法則 (2)
### 提敘
就是在說 DNA 如何轉錄。
### 考點
同下，不過 $A→T$ 變成 $A→U$。
如果你好奇為什麼是同下，只是因為我當時是反過來做的。
所以這就是水題，因為跟上面那題一樣，你解一題可以拿兩題分數，超賺。
# 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$。
# 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$ 。
Sign in with Wallet
Connect another wallet