# a196: 競賽用hello world
### 提敘
為了怕有一堆人 0 分
所以多了一題這個
(然後你們大部分人真的只對這題，好電 :+1: )
### 考點
基本輸入輸出。
```cpp=
#include<iostream>
using namespace std;
int main() {
cout << "hello, world";
}
```
# 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;
}
```
然後接著就是輸出執行完的程式了，結束。
### 另解
###### 我爽打再打。
# 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);
}
else{
d = min(d - 25, 0);
}
tmp += d;
}
```
然後第二步和第一步差不多(我直接複製上面的所以我要進行下面動作。) :
```cpp=
if(arr[x].F == 0) {
arr[x].F = 1;
.
.
.
arr[x].F = 0; //記得要改回來。
}
```
然後就輸出。
### 另解
###### 我爽打再打。
# b168: Pote Liu 冒險日記 (1)
### 提敘
翻譯 :
:::info
:::spoiler 也因為此處有禁制，所以他必須走到海拔低一點的地方才能離開這裡，遇到前方的海拔高於目前所在位置就向右轉直到轉了一圈。(海拔低一點是劇情需要，不是Pote Liu太菜，他都被封號陰陽陣聖了怎麼會連區區一個小禁制都破除不了。)
最初面朝右，若前進方向數值高於該格，向右轉，直至四周皆大於該格。
:::
:::info
:::spoiler Pote Liu施展請神術發現他竟然沒辦法召喚此處的山神，氣不過的他使用了搬山填海的神通，成功的把山的海拔降低，但是因為消耗的靈氣太大且他不想動用太多的規則之力所以只會有4次成功。(這段話的意思是有40分的簡單題。)
有幾分是在 `int` 範圍。(初階班應該要拿到。)
:::
:::info
:::spoiler Pote Liu身為造化棋聖，所以他可以把路線改成只有一條寬以便他快速離開此地，但是因為這樣會被天道發現而驅趕出此方世界所以他只使用了1次。(因為搬山填海是讓海拔高度降低所以這兩種方法是不同，Pote_Liu不會傻到同時在1筆測資中使用，也就代表除了40分的簡單題以外還有送10分。) (補充，送分不代表它可以無腦拿。)
有一筆是一維陣列。(但他的值我放超過 `long long` ，初階班沒拿到就算了。)
:::
### 考點
轉向，就是二維陣列他的資料該怎麼進行移動。
```cpp=
if (face == 0) {
//進行運算。
}
else{
face = 1;
}
//已此類推，然後連續轉四次都沒有移動就結束。
```
然後第二個重點是大數運算，這也算是一個不小的觀念了，可以去看看別人的講義，以後有機會再上，我這裡稍微的提一下就是轉字串用數學直式的概念處理。
:::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)
:::
# b166 改作文
### 考點
#### string streamstring
反正就判斷作文大小還有最長的字
我的作法是全轉小寫 刪掉除了空格和英文以外的東西
算空格數可以知道作文長度
最長的單字我是用stringstream
```cpp=
stringstream ss(writting);//writing是整篇作文
string word, longest;
while (ss >> word) {
if (word.length() >= longest.length()) longest = word;
}
```
# b181 卡特蘭數
### 考點
#### 陣列
這題說實話也頗水 數學式帶入就AC
```cpp=
/*
for (int i = ?; i < ?; i++) {
for (int j = ?; j <= ?; j++) {
dp[i + 1] = (dp[i + 1] + dp[?] * dp[? - ?]) % ?;
}
}
或是
for (int i = ?; i < ?; i++) {
for (int j = ?; j <= ?; j++) {
dp[i + 1] += (dp[?] * dp[? - ?]) % ?;
dp[i + 1] = dp[i + 1] % ?;
}
}
*/
```
? 自行判斷 要填什麼
# b182 刪刪減減
### 考點
#### sort
這題題序有點刁鑽?! 但只要理解就會知道烏龜就是刪陣列的最小值 反之兔子就是刪陣列的最大值
用上面想法可以衍生出一個通用的結論 但想不到也沒差就按步就班做也會過
用.pop_back & .erase(.begin()) 刪最大最小值
# b183 密碼
### 考點
#### string sort
這題其實只需照著題序裡的密碼分解一步一步做就能過了
第一步是把大小寫字母分別找出來，這步非常的簡單，用ASCII能夠輕鬆判斷，當然也有其他辦法，看你自己的想像
```cpp=
string s; //原字串
string s1,s2; //分別存取大小寫英文字母
vector<int> A; //等等存數字的地方
for(int j = 0;j < 字串總長;j++) {
if(int(s[j]) >= 65 && int(s[j]) <= 90) s1 += s[j];
else if(int(s[j]) >= 97 && int(s[j]) <= 122) s2 += s[j];
```
第二步是把數字都找出來，這個部分稍微難辦一點，需要注意的是$int$是包含負數的，所以請記得要判斷負數
我找數字方式是用$ASCII + StringStream$，每當找到了字元為數字或是'-'的時候，開一個臨時string存起來，然後我們要往這個字元後面繼續搜，看他後面是否也是數字，如果是就把這個數字加在臨時字串最後面如果不是就代表我們已經找到完整的數字，然後利用$StringStream$把臨時陣列轉換成數字，存到陣列裡，遍歷完原字串後把陣列sort就完成了。
```cpp=
else if(s[j] == 45) {
if(int(s[j + 1]) >= 49 && int(s[j + 1]) <= 57) {
int k = 2,index;
string num = "-";
num += s[j + 1];
while(int(s[j + k]) >= 48 && int(s[j + k]) <= 57) num+=s[j + k],k++;
stringstream sst1;
sst1 << num;
sst1 >> index;
A.push_back(index);
j += k - 1;
}
}
else if (int(s[j]) >= 48 && int(s[j]) <= 57) {
int k = 1,index;
string num = "";
num += s[j];
while(int(s[j + k]) >= 49 && int(s[j + k]) <= 57) num+=s[j + k],k++;
stringstream sst2;
sst2 << num;
sst2 >> index;
A.push_back(index);
j += k - 1;
}
```
sort之後輸出大寫->小寫->陣列就完成了!
```cpp=
sort(A.begin(),A.end());
cout << s1 << s2;
for(int i = 0;i < A.size();i++) {
cout << A[i];
}
cout << '\n';
```
# b184 我的字典沒有困難!!!
### 考點
#### str.find()/.insert()/.erase()
這題就是單純考你字串的操作，不過要小心的地方很多，我會分成三個階段解這題
##### 1.找出所有 困難&difficulty 並轉換成 養分&nutrient
作法就是先用.find()找 困難&difficulty
然後通過.erase() + .insert() 替換成養分&nutrient
以下為替換的示範:
```cpp=
string str;
int save;
if(str.find("困難") != string::npos) {
s.insert(s.find("困難"),"養分");
save = s.find("困難");
s.erase(save,4),s.erase(save,2);
}
```
國字為什麼需要兩次的erase呢?
因為中文字在UTF-8編碼中佔3個字元，Big5編碼中佔2個字(ddj用的是UTF-8)因此"困難"的大小是3*2=6。
##### 2.把兩兩相接的 養分&nutrient 轉換成 養分s&nutrients
題目要求我們把連續的 困難&difficulty 轉換成一個 很多養分&nutrients，所以再這個階段我們會初步處理這件事，這階段先把兩個
```cpp=
if(s.find("養分養分") != -1) {
s.insert(s.find("養分養分"),"養分s");
save = s.find("養分養分");
s.erase(save,8),s.erase(save,4);
}
```
題目要求的是"很多養分"但我用的是"養分s"，你們可以想一下為何我不用"很多養分"，畢竟禮拜日要考$APCS$ :)
##### 3. 把兩兩相接的 養分s&nutrients 或是 養分s+養分&nutrients+nutrient 並成 很多養分&nutrient
先把 養分s養分s -> 養分s 還有 養分s養分 -> 養分es，最後把養分es和養分s變成很多養分
```cpp=
if(s.find("養分s養分s") != -1) {
s.insert(s.find("養分s養分s"),"養分s");
save = s.find("養分s養分s");
s.erase(save,10),s.erase(save,4);
}
else if(s.find("養分s養分") != -1) {
s.insert(s.find("養分s養分"),"養分es");
save = s.find("養分s養分");
s.erase(save,9),s.erase(save,4);
}
while(s.find("養分s") != -1 || s.find("養分es") != -1) {
if(s.find("養分s") != -1) {
s.insert(s.find("養分s"),"很多養分");
save = s.find("養分s");
s.erase(save,5),s.erase(save,2);
}
else if(s.find("養分es") != -1) {
s.insert(s.find("養分es"),"很多養分");
save = s.find("養分es");
s.erase(save,6),s.erase(save,2);
}
}
```
過程:
養分養分養分養分養分養分養分養分養分養分養分123養分養分->
養分s養分s養分s養分s養分s養分123養分s->
養分es123養分s->
很多養分123很多養分
以上以中文為例，英文的邏輯也一樣但只要erase一次
# b185 時間線
### 考點
#### sort
這題很簡單，日期綁成一個數字然後sort完輸出就好了。
例: 1939 9 1, 1918 11 11
1939 9 1 -> 19390901, 1918 11 11 -> 19181111
19390901 > 19181111 因此排序後就是
1918 11 11, 1939 9 1
Sign in with Wallet
Connect another wallet