## APCS 二級分難度
### n361. 數字旅館 (hotel)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=n361)
這題的重點是 "根據房號得知在幾號大樓"，所以主要是 if
再來補充幾個細節 :
第一個是 "如果同時滿足多種可能,則房間在編號最小的大樓"
這裡只要我們把 if-else if-else 對應的編號順序修成由小到大
不過這題**剛好就是按照樓層編號給的條件**，所以只要跟著他給的順序即可
第二個是**完全平方數的判斷**，一個完全平方數 $x $代表他是 $n\times n$
所以可以先求出 $n$，然後再看 $n\times n == x$
這裡要用到兩個內建函式: sqrt(x), pow(x, 2)
sqrt 是取 $x$ 的 $0.5$ 次方，比如 sqrt(49) == $7$、sqrt(48) == $6.9282$
pow 是求 $x$ 的 $y$ 次方，比如 pow(x, 2) == $x^2$
因為 sqrt 求出來可能是浮點數，所以再用 int() 轉換成整數
最後 `pow(int(sqrt(x)), 2) == x` 就是判斷完全平方數的條件式
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, tmp ;
cin >> n ;
for (int i=0;i<n;i++) {
cin >> tmp ;
if (tmp % 3 == 0 && tmp % 2 == 0)
cout << "1 " ; // 大樓 1
else if (tmp % 3 != 0 && tmp % 2)
cout << "2 " ; // 大樓 2
else if (pow(int(sqrt(tmp)), 2) == tmp || (tmp % 2 == 0 && tmp % 7 != 0))
cout << "3 " ; // 大樓 3
else
cout << "0 " ; // 都沒有
}
return 0 ;
}
```
### n362. 質數遊戲 (Primes)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=n362)
這題概念很簡單，就是做到兩件事
1. 給一數字 $n$，求兩數字 $a,\ b$ 使 $a\times b == n$
2. 問 $a,\ b$ 是否"皆"為質數
第一個可能比較少見，不過這裡一樣用暴力的方式，把 $2\sim$ sqrt(n) 的數字都**試過一遍**
```cpp=
for (int i=2;i<=sqrt(n);i++) // 找哪兩數相乘
if (n % i == 0) // 找到數字能整除 i
a = i, b = n / i ;
```
這樣寫似乎會出現一種情況，如果 $a,\ b$ 有很多組，那怎麼知道哪一組才是要判斷的
所以這裡改成找到一次就判斷一次會比較好，如果已經確定兩者都是質數就**輸出並結束程式**
```cpp=
#include<bits/stdc++.h>
using namespace std ;
bool isprime(int n) { // 判斷質數
if (n % 2 == 0 && n != 2) // n 是 2 的倍數
return false ;
if (n > 3) { // 列舉因數的可能
for (int i=3;i<=sqrt(n);i+=2)
if (n % i == 0) // 有其他因數(不是質數)
return false ;
}
return true ; // 是質數
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, a, b ;
cin >> n ;
for (int i=2;i<=sqrt(n);i++) { // 列舉所有可能
if (n % i == 0) { // 找到因數了
a = i, b = n / i ;
if (isprime(a) && isprime(b)) { // 都是質數
cout << a << ' ' << b ;
return 0 ;
}
}
}
cout << "0 0" ;
return 0 ;
}
```
#### 進階優化
但是從數學的角度來看的話，如果 $a,\ b$ 都是質數，那代表只能找到一組($1,3$、$3,1$ 看做相同)
因為兩者相乘是 $n$，也就是 $a,\ b$ 都是 $n$ 的**因數**，一般在對數字做**因數分解**時都是用**短除法**
短除法過程中除出來的每個數字跟除數都是 $n$ 的因數，看圖會比較好理解
在這個例子中至少可以知道 $420$ 的因數有 $2、3、5、7、21、105、210$ 等等
把最上面那層遮住，$n$ 變成 $210$，就會發現 $210$ 的因數也是 $420$ 的因數
舉個例子，如果 $210$ 可以被 $7$ 整除，那 $420$ 也可以被 $7$ 整除
最後就可以知道如果 $a,\ b$ 都是質數(因數只有 $1$ 跟自己)，那 $n$ 的因數就是 $1、a、b、n$
也就是說如果找到兩組以上的 $a,\ b$ 就代表一定不是質數
不過要注意，如果只有一組也不代表一定是質數，因為會出現 $a=x, b=x^2$ 的情況
### a251. 假費波那契數
[題目連結](https://zerojudge.tw/ShowProblem?problemid=a251)
看完題目可以整理幾個重點
1. 對於數字 $S_i$ ($i > 4$) 定義為：$S_i = S_{i-4} + S_{i-1}$
2. 給定數值 $N$ (奇數)，試問數列中 $N$ 個數的中位數(需排列的第 $\frac{N+1}{2} 項$)
3. $0\le S_1, S_2, S_3, S_4\le5$，所有數字皆為整數
所以題目只需要將 $N$ 個數值都求出來，最後排序完在求中位數就可以了
但是這題還有一個優化空間，就是如果從重點一跟重點三可以推出
假設要求 $S_5$，會是 $S_4 + S_1$，也就是說，$S_5\ge S_4$
後面的數字也可以以此類推，最後的數列只需考慮前四項的大小，之後的數值只會**越來越大或相同**
所以搭中位數落在第四項以後，就可以推到中位數即可，不須推出 $N$ 項數值
在 $N$ 數值較大的時候，這個方法比較明顯，但這題 $N$ 最大 $19$，所以用最直覺的方式就可以了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int t, n ;
cin >> t ;
while (t--) { // t 筆測資
vector<int> s(25, 0) ;
cin >> n ;
cin >> s[0] >> s[1] >> s[2] >> s[3] ; // 輸入數值
for (int i=4;i<=n;i++)
s[i] = s[i-4] + s[i-1] ; // 計算到 n 項
sort(s.begin(),s.begin()+n) ; // 排序求中位數
cout << s[(n+1)/2-1] << '\n' ;
}
return 0 ;
}
```
#### 模擬解法
前面有稍微提到，在數值很大的情況(本題無)下，推到第 $N$ 項會浪費時間跟空間
所以這裡詳細介紹利用模擬找規律的技巧解題，在題目中有說到題目給定的數字都是正整數或是 $0$
也就是說 $S$ 數列推出來的數字也只會是正整數或 $0$，所以可以得到下面的結論
* $S_5 = S_4+S_1， S_5\ge S_4, S_1$
* $S_6 = S_5+S_2， S_6\ge S_5, S_1，S_6\ge S_5, S_4, S_2, S_1$
* $S_7 = S_6+S_3， S_7\ge S_6,S_5,S_4,S_3,S_2,S_1$
$S_7$ 之後不論怎麼推都是不嚴格遞增的數列，所以不須排序也可以得知中位數
換句話說，$S$ 數列排序後會是 sort($S_1\sim S_6$)$, S_7,...,S_n$，最後可以整理成兩種情況
1. $N >= 13$，中位數 $S_{(n+1)/2}$ 在 $S_7$ 後或是 $S_7$ 本身
2. $N < 13$，中位數 $S_{(n+1)/2}$ 在前 $6$ 項，所以需要排序
第一種情況推到中位數就可以了，第二種情況跟之前一樣，主要在 $N$ 值極大的情況下會比較有效率
```cpp=
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int t, n ;
cin >> t ;
while (t--) {
vector<int> s(4,0) ;
cin >> n ;
cin >> s[0] >> s[1] >> s[2] >> s[3] ; // 輸入數值
if (n >= 13) {
for (int i=4;i<=((n+1)/2-1);i++)
s.push_back(s[i-4] + s[i-1]) ; // 計算到 n 項
cout << s[(n+1)/2-1] << '\n' ;
}
else {
for (int i=4;i<=n;i++)
s[i] = s[i-4] + s[i-1] ; // 計算到 n 項
sort(s.begin(),s.begin()+n) ; // 排序求中位數
cout << s[(n+1)/2-1] << '\n' ;
}
}
return 0 ;
}
```
### g111. B.復仇之戰（revenge）
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g111)
看完題目大概可以知道要求刪除的點是奇數點
因為刪除完後兩兩合併，也就是說點的左右兩邊都有偶數個點，所以奇數點才符合
至於最直覺的方式大概是，先把所有點之間的數值記錄下來，然後每個奇數點都去推過一遍
找距離最小值就可以知道答案了，但是這樣的複雜度會跑到 $O(N^2)$，很明顯太大了
所以如果要快速的找到答案就要看規律，如下圖所示，假設有五個軍隊與其間距
最後結合規律可以推出以下結論
* 刪掉點 $1$ 的其他長度總和為 $L\ (B+D)$
* 刪掉點 $3$ 的其他長度總和為 $L + A - C\ (A+D)$
* 刪掉點 $5$ 的其他長度總和為 $L + A - B + C - D\ (A+C)$
也就是說，因為我們只需要比較奇數點的長度總和，所以我們可以把 $L$ 當作基準點($0$)
所以只要找新增的數值中較小的就可以了，點 $1$ 是 $0$，點 $3$ 是 $a-b$，點 $5$ 是 $a+c$
在圖中的例子點 $1$ 是 $0$，點 $3$ 是 $-4$，點 $5$ 是 $-7$，最後就可以推知要刪除點 $5$
最後知道規律後，在實作前要注意幾個點
1. 需要加入奇數點到偶數點(例:A、C) 的數值，需要刪除偶數點到奇數點(例:B、D) 的數值
2. 在跑過字串的時候要記錄點之間的距離才能計算
3. 每次遇到奇數點時要判斷一次新增的數值大小
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, idx = 1, dis = 0, sum = 0, i, num = -1, minn = 0 ;
// idx 答案、dis 點之間距離、sum 新增數值總和、num 目前的點編號
bool odd = true ; // 判斷是否為奇數
string s ;
cin >> n >> s ;
for (i=0;i<n;i++) { // 找到第一個點位置
if (s[i] == 'p')
break ;
}
for (i=i;i<n;i++) {
if (s[i] == 'p') { // 遇到點
if (odd) { // 奇數點
sum -= dis ;
num += 2 ;
if (sum < minn) { // 比較新增數值大小
minn = sum ;
idx = num ;
}
}
else // 偶數點
sum += dis ;
odd = !odd ; // 偶變奇、奇變偶
dis = 0 ; // 重製距離
}
else
dis++ ;
}
cout << idx ;
return 0 ;
}
```
### g308. pB. 跳跳布朗尼(Brownie)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e787)
題目看完就知道三個重點
1. 每個格子上都有一個數字 $x$，$x$ 是要傳送到的座標
2. 傳送座標只能使用一次，且傳送會一直進行直到走到 "曾經走過的位置"
3. 有些位置上有布朗尼，經過該位置就可以吃到布朗尼
最後只要根據這些特點寫出對應的程式碼就可以了
比如第一點，在原本座標 $t$ 時對應的數值是 $x[\ t\ ]$，所以如果要更新座標就可以寫成 `t = x[t]`
第二點要求走到 "曾經走過的點" 時要停止行動，所以可以直接用一個陣列表示點是否被走過
最後一點只要記得在傳送前判斷是否有布朗尼就可以了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
int n, t, idx, ans = 0 ; // ans 是有幾個布朗尼
cin >> n >> t ;
vector<int> x(n,0) ;
vector<int> y(n,0) ;
vector<bool> gone(n,false) ; // 走過的點
for (int i=0;i<n;i++)
cin >> x[i] ;
for (int i=0;i<n;i++)
cin >> y[i] ;
while (!gone[t]) {
ans += y[t] ; // 判斷有無布朗尼
gone[t] = true ; // 設成走過
t = x[t] ; // 更新座標
}
cout << ans ;
return 0 ;
}
```
#### 跳跳布朗尼-延伸
在原本的題目要求上，問起點從哪裡開始能吃到最多
在這延伸的題目上可以使用最暴力的方式，也就是枚舉
只要把 $t$ 改成所有點，並且重製 gone 跟 ans
最後只要比較哪個點當作起點數值最大即可
### e787. b2.尋寶地圖(Map)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e787)
看完題目後知道有矩陣 $A$ 跟轉換表 $B$，根據轉換表 $B$ 可以改變 $A$ 的元素
只要行列相加是奇數就轉換($0,1$ 互換)，最直覺的方式就是在判斷每點的時候往上下左右相加
但是這樣的等於說每個位置都需要 $n\times m$ 次的計算，如果可以是先把每行跟每列的元素相加好
最後記得要刪除重疊的元素，也就是目前的格子，就會是行列相加的結果
根據這個結果就可以對矩陣 $A$ 作轉換，並輸出矩陣 $A$
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0) ;
int n, m ;
cin >> n >> m ;
vector<int> r(m,0) ; // 第 i 直行的總和
vector<int> c(n,0) ; // 第 i 橫列的總和
vector<vector<int>> A(n,r) ;
vector<vector<int>> B(n,r) ;
for (int i=0;i<n;i++) // 輸入藏寶圖
for (int j=0;j<m;j++)
cin >> A[i][j] ;
for (int i=0;i<n;i++) { // 輸入轉換圖
for (int j=0;j<m;j++) {
cin >> B[i][j] ;
r[j] += B[i][j] ; // 計算行
c[i] += B[i][j] ; // 計算列
}
}
// 轉換跟輸出一起就可以了，因為矩陣 A 的元素互不干涉
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
// 判斷是否可以作轉換
if ((c[i] + r[j] - B[i][j]) % 2 == 1) {
// 作轉換
A[i][j] = (A[i][j] + 1) % 2 ;
}
cout << A[i][j] << ' ' ;
}
cout << '\n' ;
}
return 0 ;
}
```
### f148. 2. 定向越野 (Orienteering)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f148)
看完題目後可以找出兩個重點
1. 要找小寫字母的位置座標
2. 如果字母數量小於 $N$ 就輸出 "Mission fail."
這兩個重點都可以在輸入資料時找出來，把小寫字母順序當成 index，透過 ASCII 把字母轉成數字
然後一邊記錄輸入的字母數量，如果輸入完成後字母數量 $<\ N$，就輸出 "Mission fail."
最後採用 struct 去一邊記錄有哪些字母在地圖中，一邊記錄它們的座標
```cpp=
#include<bits/stdc++.h>
using namespace std ;
struct loc { // get 為是否有此字母
bool get = false ;
int x = -1, y = -1 ;
};
char maps[11][11] = {} ;
loc have[26] = {} ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int h, w, n, idx = 0, getnum = 0 ;
cin >> h >> w >> n ;
for (int i=0;i<h;i++) {
for (int j=0;j<w;j++) {
cin >> maps[i][j] ;
if (maps[i][j] != '0') { // 發現字母
getnum++ ;
idx = maps[i][j] - 'a' ; // 字母轉數字
have[idx].get = true ;
have[idx].x = i, have[idx].y = j ; // 記錄座標
}
}
}
if (getnum < n) cout << "Mission fail." ; // 字母數量不夠多
else {
for (int i=0;n>0;i++) {
if (have[i].get) {
cout << have[i].x << ' ' << have[i].y << '\n' ;
n-- ; // 減 n 直到達到題目要求(N)
}
}
}
return 0 ;
}
```
#### 進階
題目改成矩陣內會有大小寫英文和數字 $0$，並且輸入的第二行整數 $N$ 範圍改成 $1\le N\le45$
並且 $N$ 必為偶數，輸出在原本的基礎上還需考慮三點
1. 以 "AabBCDcdef" 為例，輸出要以 $x$ 個大寫座標 + ($x+1$) 個小寫座標做組合
2. 假如當中大寫座標或是小寫座標的數量不滿足第一點則視為任務失敗
### k514. P2.解藥 (Medicine)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k514)
題目看完後大概可以找出兩個重點
1. 給的是"比例"，不是數量
2. 四個比例中有一個一定是 $1$ => 可作為比例的基準點
所以根據這兩點可以制定出解題策略，如果比例都符合，就可以做成解藥
比例如果要符合，先看哪個**材料比例**是 $1$，假設有一個比例為 $3:1:2:7$
那我們就從第二項的材料數量下手，假設此時第二項**材料包份量**分別為 $5,3,7,2,1$
第一項比例對應的數量就必須是 $15,9,21,6,3$，其他項也可以這樣解
最後就知道是否能夠湊出**對應比例**的藥材
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int per[4] , num[4][11] ;
// 輸入比例、輸入包裝
int main() {
int n, idx = -1, ans = 0 ;
bool have = false ; // 有沒有符合的
for (int i=0;i<4;i++) {
cin >> per[i] ;
if (per[i] == 1)
idx = i ; // 基準點
}
cin >> n ;
for (int i=0;i<4;i++) {
for (int j=0;j<n;j++) {
cin >> num[i][j] ;
}
}
for (int i=0;i<n;i++) {
int small = num[idx][i], cnt = 1 ; // 基準點、符合比例的數量
for (int j=0;j<4;j++) {
if (j == idx) continue ; // 遇到基準點
for (int k=0;k<n;k++) {
if (num[j][k] == small * per[j]) { // 符合比例
cnt++ ;
break ;
}
}
}
if (cnt == 4) { // 四個都符合
have = true ;
ans = small ;
}
}
if (have) { // 有找到
for (int i=0;i<4;i++) {
cout << ans*per[i] << ' ' ;
}
}
else // 未找到
cout << -1 ;
return 0 ;
}
```
#### 進階
更改題目要求，改為 $a,b,c,d$ 不一定有 $1$，且可能會有多組輸出(照題目給定順序輸出)
解析 :
其實實際上這題的概念是**確保藥材數量符合比例**，且不論比例數字為多少
都會是正整數，也就是說，可以直接**用比例去互推**，比如 $7:3$，在整數的範圍內是 $7n:3n$
所以最後前面甚至**不需要找基準點**(也可說第一項恆為基準點)，只需用**第一項去推出所有項**
推的方式可以用類通分的方法，如果 $a \times 3 == b\times7$，那代表 $a:b = 7:3$，由此可推出所有項
至於多組輸出只要紀錄**哪些第一項能找出符合比例份量**，用一維陣列，最後程式碼會如下
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int per[4] , num[4][11], ans[11] ;
// 比例、份量、第 i 組有幾格符合
int main() {
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n ;
bool have = false ; // 有沒有答案
for (int i=0;i<4;i++)
cin >> per[i] ;
cin >> n ;
for (int i=0;i<4;i++)
for (int j=0;j<n;j++)
cin >> num[i][j] ;
for (int i=0;i<n;i++) {
int pt = num[0][i] ; // 基準點
ans[i] = 1 ;
for (int j=1;j<4;j++) {
for (int k=0;k<n;k++) {
if (num[j][k] * per[0] == pt * per[j]) { // 類通分
// cout << pt << ": " << num[j][k] << '\n' ;
ans[i]++ ; // 第 i 個第一項能找出符合比例份量+1
break ; // 找到了就結束第 j 項往第 j+1 項找
}
}
}
}
for (int i=0;i<n;i++) {
if (ans[i] == 4) {
int one = num[0][i] / per[0] ; // 假定比例為 1
for (int j=0;j<4;j++)
cout << one * per[j] << ' ' ; // 假定比例後直接乘
cout << '\n' ;
have = true ;
}
}
if (!have) // 沒找到
cout << -1 << '\n' ;
return 0 ;
}
```
### m581. 狼人殺 (Werewolves)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m581)
首先說明一下題目的概念
1. 場上每個人都有三個職業(不重要)，其中一個是狼人
2. 如果遊戲順利結束，會有**兩種可能**(狼人贏或輸)
3. 如果遊戲中有人被重複淘汰就**輸出字串**並**結束遊戲**
所以輸出也是會有**三種可能**，也就是第二點跟第三點說的
第一點當中可以知道，**每個人都有三個職業**，其中**狼人比較重要**，所以可以用一維陣列紀錄
第二點，狼人輸的條件是**狼人全部被淘汰**，所以用一個**題目外的數字**代表淘汰
比如我下方使用 $-2$，因為職業只有 $-1、0、1$ 三個，最後只要看**還有沒有狼人**($-1$)
第三點，**重複淘汰的檢查**可以在淘汰人的時候**多用一個 if 判斷**這個人是否已經被淘汰了
最後做個流程整理
1. 輸入每個人的職業
2. 根據輸入淘汰人
3. 如果重複淘汰就輸出 "Wrong" 並結束遊戲
4. 淘汰完檢查狼人是否活著
5. 狼人活著就是狼人贏，反之好人贏
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, x ;
cin >> n ;
vector<int> man(n+1) ; // 每個人的職業
for (int i=1;i<=n;i++) // 輸入職業
cin >> man[i] ;
while (cin >> x && x != 0) { // 淘汰人
if (man[x] == -2) { // 已經被淘汰了
cout << "Wrong" ;
return 0 ;
}
man[x] = -2 ; // 淘汰
cin >> x ;
}
for (int i=1;i<=n;i++) {
if (man[i] == -1) { // 狼人贏
cout << "Werewolves" ;
return 0 ;
}
}
cout << "Townsfolk" ; // 狼人輸
return 0 ;
}
```
### m397. 烤肉 (BBQ)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m397)
先整理題目的概念
店家共收 $n$ 元，總共有 $m$ 串，一串分別為 $x$ 跟 $y$ 元
因為不知道分別有幾串，但是知道總共有幾串，所以就把所有可能列出來
假設現在有 $5$ 串，$x = 5、y =10$
如果所有可能中都沒有 $n$，代表店家收錯錢了
列出所有可能的辦法就是使用迴圈，因為兩個肉串會分別是 $0\sim m$
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, x, y, ans = -1 ; // ans 是最後找出的豬肉串數
cin >> n >> m >> x >> y ;
for (int i=0;i<=m;i++) {
if (x*i+y*(m-i) == n) // 店家收的錢正確
ans = i ; // 紀錄有幾串豬肉
}
if (ans == -1) // 收錯錢
cout << "-1 -1" ;
else // 輸出正確的串數
cout << ans << ' ' << m-ans ;
return 0 ;
}
```
### m398. 超市排隊 (Supermarket)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m398)
這題概念也不難，只要**分別把每一個櫃台的花費時間都計算出來**
最後在做**比較**就可以了，不過這裡還是稍微講解一下，題目有說兩點
1. 每一個商品需要花 $3$ 秒結帳
2. 每兩個顧客之間會保持固定的距離,這段距離需走 $2$ 秒
這個第二點比較重要，因為可能有人沒看清楚 "**保持固定的距離**"
意思就是當某個人結帳完後，後面的人移動**總共只需要**花 $2$ 秒
舉個例子，如果總共有 A、B、C、D 四個人，當 A 結帳完後
B 移動到 A 原本的位置只要花 $2$ 秒，C 移動到 B 原本的位置也只要花 $2$ 秒
這樣總共花費的時間還是 $2$ 秒，因為他們都是**一起移動**的
再來就是資料儲存可以用二維陣列
因為有三個櫃台，每個櫃台分別有 $a、b、c$ 個人，所以陣列大小就是 $A[3][N]$
還有 $N$ 會變動，所以用 vector 會比較方便
最後用一個題目範圍外的數字去找最少花費時間即可
這題題目範圍外數字比較繁瑣，最多有 $100$ 個人、一個人商品最多有 $500$ 項
所以排隊時間最大應該是 $3\times100\times500+99\times2$，也就是商品花費時間 + 移動花費時間
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int a, b, c, tmp ;
cin >> a >> b >> c ;
vector<int> num = {a,b,c} ; // 每個櫃台的人數
vector<int> v[3] ; // 二維陣列
for (int i=0;i<3;i++) { // 輸入資料
for (int j=0;j<num[i];j++) {
cin >> tmp ;
v[i].push_back(tmp) ;
}
}
int idx, cost = 3*100*500+100*2 ; // 櫃台編號、最少花費時間
for (int i=0;i<3;i++) { // 比較三個櫃台
tmp = 0 ; // 此櫃台花費時間
for (int j=0;j<num[i];j++)
tmp += v[i][j]*3+2 ;
tmp -= 2 ; // 第一個人直接在櫃台不須移動
if (tmp < cost) {
cost = tmp ;
idx = i ;
}
}
cout << idx+1 << ' ' << cost ;
return 0 ;
}
```
不過這題放在二級分，因為還可以**再優化**，原本是輸入然後計算跟比較
因為這題是輸入完一個櫃檯的數據後在輸入下一個
所以可以**把三個步驟放在一起**，變成輸入+計算+比較
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int a, b, c, tmp, cost = 3*100*500+100*2, idx, input ;
cin >> a >> b >> c ;
vector<int> num = {a,b,c} ; // 每個櫃台的人數
for (int i=0;i<3;i++) {
tmp = 0 ;
for (int j=0;j<num[i];j++) { // 輸入
cin >> input ;
tmp += input*3+2 ; // 計算
}
tmp -= 2 ; // 第一個人不需移動
if (tmp < cost) { // 比較
cost = tmp ;
idx = i ;
}
}
cout << idx+1 << ' ' << cost ;
return 0 ;
}
```
### m582. 書房 (Study)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m582)
這題就是給第 $i$ 個書架上有什麼設計稿，最後再**依據設計稿編號順序輸出書架編號**
簡單來講可以先看下圖，藍色底就是**設計稿編號**，橘色底就是**書架編號**
因為要按照設計稿編號順序去輸出書架順序，所以要輸出的就是 $3\ 2\ 9$
至於實際的過程當中，**按照設計稿編號順序**很像是陣列當中的 **index**
所以用一個**一維陣列去儲存對應的書架順序**即可
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, tmp ;
cin >> n >> m ;
vector<int> v(m) ; // 依設計稿編號順序的書架編號
for (int i=0;i<n;i++) { // 輸入
cin >> tmp ;
if (tmp > 0) // 有設計稿編號
v[tmp-1] = i+1 ;
}
for (int i=0;i<m;i++) // 輸出
cout << v[i] << ' ' ;
return 0 ;
}
```
### m583. 精靈王國 (Kingdom)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m583)
這題就跟前面的跳跳布朗尼一樣，都是用傳送然後 index 變成當下 index 對應的值
所以也不需要過多解說，就是注意要有一個值先記錄 $A[idx]$ 然後才能修改
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int k, idx, tmp, ans = 0, now ; // ans 最大傳送點數量
cin >> k ;
vector<int> v(k+1) ;
for (int i=1;i<=k;i++)
cin >> v[i] ;
for (int i=1;i<=k;i++) {
idx = i ;
now = 0 ; // idx 目前位置，now 目前傳送點數量
if (v[idx] > 0) {
while (v[idx] > 0) { // 傳送
tmp = v[idx] ; // 需要 tmp 不然 idx 會影響到下一行
v[idx] = 0 ;
idx = tmp ;
now++ ;
}
}
ans = max(ans, now) ; // 比較目前跟之前最大
}
cout << ans ;
return 0 ;
}
```
### m801. 鏡像對稱 (Mirror)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m801)
這題的考點只有兩個
1. 判斷迴文是否成立
2. 判斷輸入字串是否在題目給定範圍內
迴文判斷很值得寫，因為觀念題常常出現，自己寫過後會比較能理解邏輯
迴文就是不論正反序都一樣，比如: "我為人人，人人為我" 等等
也就是說如果一個字串的長度是 len，那就是 $s[0] == s[len-i-1]$
並且因為一次判斷兩個位置，所以範圍只要到**最中間**就可以了
再來說說第二點，題目有先給定有那些大寫英文是 ok 的
這裡可以用兩種辦法，第一就是在**遇到任何字元時都跑一遍題目給定的**
也就是說如果目前是 "A"，那就一個個看題目給定的有沒有 "A"
第二種辦法就是利用字元的 ASCII 搭配陣列，因為英文字母只有 $26$ 個
所以只需要先用**一維陣列紀錄哪些字母在題目範圍內**，然後判斷迴文時+陣列判斷
簡單來說，第一種就是**用時間換取空間**，第二種就是**用空間換取時間**
因為這裡**要花費的空間不大**，所以我採用第二種
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int a[26] = {0} ; // ASCII
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
string s1, s2 ;
s1 = "AHIMOTUVWXY" ; // 題目給定範圍
for (int i=0;i<11;i++)
a[s1[i]-'A'] = 1 ;
cin >> s2 ;
int len = s2.size() ;
for (int i=0;i<=len/2;i++) { // 迴文
// 判斷回文、是否再題目給定範圍內
if (!(s2[i] == s2[len-i-1] && a[s2[i]-'A'])) {
cout << "No" ;
return 0 ;
}
}
cout << "Yes" ;
return 0 ;
}
```
### n630. 電影院 (Cinema)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=n630)
這題是時間處理的問題，先整理幾個重點
1. 題目會給定多個電影開始時間(已排序)與現在時間
2. 要**預留** $20$ 分鐘，所以現在時間要 $+20$ 分鐘
3. 找**最早能看**的電影時間，如果都不行就輸出 "Too Late"
在輸入電影時間的時候當然可以用**二維陣列**，但在這裡用 struct，根據**個人喜好**選擇即可
比較重要的是第二點，因為預留時間代表**現在時間產生變化**
假設現在是 $03:45$，那預留後就會變成 $04:05$
所以可能**不只是分鐘改變**而已，小時同樣可能會因為**進位**而產生變化
再來就是使用 for 迴圈去對每個電影時間做判斷，有兩種可能
1. 小時不一樣 => 如果電影時間比較大就代表一定能看到 ($3:20$ vs. "5:10")
2. 小時一樣、分鐘不一樣 => 電影時間比較大代表一定能看到 ($11:20$ vs. "11:21")
如果最後都沒找到就直接輸出 "Too Late"，要注意輸出時間時要用格式化輸出
因為 hr:min 是 xx:yy，所以 $4:1$ 要寫成 $04:01$，詳細的看[這篇](https://)
```cpp=
#include<bits/stdc++.h>
using namespace std ;
struct times {
int h, m ; // hr、min
};
times mov[1005] ; // 電影時間
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, nh, nm ;
cin >> n ;
for (int i=0;i<n;i++)
cin >> mov[i].h >> mov[i].m ; // 輸入電影開始時間
cin >> nh >> nm ; // 目前時間
nm += 20 ; // 預留 20 min
if (nm >= 60) // 預留後可能會進入下一小時
nh += 1, nm %= 60 ;
// nh += nm/60, nm %= 60 ; // 等價於第 21、22 行
for (int i=0;i<n;i++) {
if (mov[i].h > nh || (mov[i].h == nh && mov[i].m >= nm)) { // 找到了
cout << setw(2) << setfill('0') << mov[i].h << ' ' ; // 格式化輸出
cout << setw(2) << setfill('0') << mov[i].m ; // 格式化輸出
return 0 ;
}
}
cout << "Too Late" ;
return 0 ;
}
```
### n631. 撲克 (Poker)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=n631)
先說幾個重點
1. 題目把撲克牌改成 $1\sim 52$ 的編號
2. 要找兩個東西，一是目前能湊幾副**完整**牌組，二是如果要**用完**所有牌，還需幾張牌
先說第一點，因為改成數字編號後就可以用陣列儲存每個牌的數量
這樣可以很方便的銜接到第二點，第二點的一找幾副**完整**牌組
這裡舉一個小例子先幫助理解，假設編號只到 $5$
藍色格子就是目前有的牌，很明顯只能**湊出一組** $1,2,3,4,5$
所以就可以知道**各牌數的最小值**就是能湊幾組，如果要湊二組，那還要補一個 $1$
如果要湊三組(全部補完)，那就要補 $1,1,2,3,5$，也就是橘色格子的總數
所以**全部補完所需的牌數**就是整個區塊-藍色區塊，整個區塊是底 $\times$ 高
在這裡底就是**編號數量**，高就是**各牌數的最大值**，藍色區塊是題目給的牌數，也就是 $n$
在這個範例中就是 $5\times 3-n$，從上面可知 "各牌數的最大/小值" 都需要計算
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int card[52] = {0} ; // 編號 index 的牌有幾張
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, tmp, out = 0 ; // out 是還需補幾張
cin >> n ;
for (int i=0;i<n;i++) {
cin >> tmp ;
card[tmp-1]++ ; // 該編號的牌數 +1
}
int minc = 521, maxc = 0 ; // 牌數的最小值跟最大值
for (int i=0;i<52;i++) {
minc = min(minc, card[i]) ;
maxc = max(maxc, card[i]) ;
}
out = maxc*52 - n ; // 還須補幾張
cout << minc << ' ' << out ;
return 0 ;
}
```
### b964. 1. 成績指標
[題目連結](https://zerojudge.tw/ShowProblem?problemid=b964)
這題有三個東西需要輸出，假設及格分數為 $60$
1. 將成績由小到大輸出
2. 找出"最高"的"不及格"分數(**找不到**輸出best case)
3. 找出"最低"的"及格"分數(**找不到**輸出worst case)
因為這三個東西只有 $2、3$ 比較有關連，所以第一可以拉出來單獨做處理
第一點直接用 sort 就可以了，搭配矩陣或是 vector 很方便
第二點可以在輸入成績時使用，因為要找出最高的不及格分數，就是要**比較所有的不及格分數**
所以在輸入成績時**直接判斷及不及格**，然後再去比較**先前**的不及格分數跟**目前**的不及格分數
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[21] ;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n ;
cin >> n ;
int num_max = -1, num_min = 101 ; // 最高不及格、最低及格
for (int i=0;i<n;i++) {
cin >> A[i] ;
if (A[i] >= 60) // 及格
num_min = min(num_min, A[i]) ; // 比較
else // 不及格
num_max = max(num_max, A[i]) ; // 比較
}
sort(A,A+n) ; // 排序
for (int i=0;i<n;i++)
cout << A[i] << ' ' ; // 由小到大輸出
cout << '\n' ;
if (num_max != -1) // 找到最高不及格分數
cout << num_max << '\n' ;
else // 都及格
cout << "best case\n" ;
if (num_min != 101) // 找到最低及格分數
cout << num_min << '\n' ;
else // 都不及格
cout << "worst case\n" ;
return 0 ;
}
```
### c294. APCS-2016-1029-1三角形辨別
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c294)
題目有兩個要求
1. 照順序輸出三個數字(由小到大)
2. 輸出三角形類型或是無法構成
跟上題一樣可以切分題目邏輯，但先排序數字可以幫助第二項的計算
先排序三個數後，就可以知道三數中最大值(也就是 $c$ ) 是多少，至於 $a, b$ 的順序**不重要**
再來就是用 if 去根據題目給定的條件判斷，要注意如果三角形**不能構成**
就**不需要**判斷三角形的種類
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[3] ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
cin >> A[0] >> A[1] >> A[2] ; // 輸入三個數
sort(A,A+3) ; // 排序三個數
for (int i=0;i<3;i++)
cout << A[i] << ' ' ;
cout << '\n' ;
int a = A[0], b = A[1], c = A[2] ;
if ((a+b) <= c) // 無法構成三角形
cout << "No" ;
else {
int a2 = a*a, b2 = b*b, c2 = c*c ;
if ((a2+b2) < c2) // 鈍角
cout << "Obtuse" ;
else if ((a2+b2) == c2) // 直角
cout << "Right" ;
else // 銳角
cout << "Acute" ;
}
return 0 ;
}
```
### c290. APCS 2017-0304-1秘密差
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c290)
題目要求的就是一個數字中，(奇數位數字-偶數位數字) 的絕對值
這題可以用 ASCII 去解，如果要將一個小於 $10$ 的數字字元**轉換成一個整數**
可以用 `數字字元 - '0'` 因為數字字元的 ASCII 會如下
假設 $0$ 的 ASCII 是 $67$，那 $1$ 的就是 $68$，後面以此類推
小於 $10$ 的整數才**可以被轉換**，但是如果是 $10$，那就是字串了，不能用字元的 ASCII 去解
最後只要用 abs 去**取絕對值**，或是判斷計算結果有沒有 $< 0$ 也可以
最後我們可以把題目給定的**整數當成字串**，去計算當中的字元轉換成數字後的總合
在計算**兩者差的絕對值**就可以得到答案
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
string s ;
cin >> s ;
int odd_n = 0, even_n = 0, len = s.size() ;
// 奇數位總和、偶數位總和、字串長度
for (int i=0;i<len;i++) {
if (i % 2 == 0) // 偶數位
even_n += s[i] - '0' ;
else // 奇數位
odd_n += s[i] - '0' ;
}
cout << abs(odd_n-even_n) ; // 輸出秘密差(絕對值)
return 0 ;
}
```
### c461. apcs 邏輯運算子 (Logic Operators)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c461)
解這題之前要知道 C++ 的一個程式特性(Python 當中也有)
如果把整數放到判斷式當中當作 bool 值，$0$ 以外的值都是 true，$0$ 是 false
所以前面的兩個整數 $a,b$ 不需要如下方程式碼來轉換成數字型態的 bool ( $0,1$ )
```cpp=
if (a != 0)
a = 1 ;
if (b != 0)
b = 1 ;
```
至於第三個數本身就只有 $0,1$ **兩種可能**，所以**可以直接**當 bool 值放到判斷式中
舉個例子，假設 `a = 3, b = 0, c = 1`，那在做 OR 運算時就可以如下
`(a || b) => true => if ((a || b) == c)`
AND 運算也可以如此，所以最後就剩下 XOR 運算了
這裡先介紹最暴力的情況，也就是把**四種情況**都在判斷式當中，用 if-else if-else 區分
這樣就會寫起來很簡單，如下列程式碼 (ans 是第三個數)
```cpp=
if (a && b && (ans == 0)) // a 不為 0 且 b 不為 0
cout << "XOR\n" ;
else if (a && !b && (ans == 1)) // a 不為 0 且 b 為 0
cout << "XOR\n" ;
else if (!a && b && (ans == 1)) // a 為 0 且 b 不為 0
cout << "XOR\n" ;
else if (!a && !b && (ans == 0)) // a 為 0 且 b 為 0
cout << "XOR\n" ;
```
但是實際上如果對於邏輯比較好的或是仔細觀察會發現規律，XOR 可以用 AND 跟 OR 表示
XOR 定義是當兩者相同就是 false，不同就是 true，用四種情況說明(T 是true, F 是 false)
1. `a = 1, b = 1` AND : T, OR : T, XOR : F
2. `a = 1, b = 0` AND : F, OR : T, XOR : T
3. `a = 0, b = 1` AND : F, OR : T, XOR : T
4. `a = 0, b = 0` AND : F, OR : F, XOR : F
可以看出來，當 AND 跟 OR 的結果一樣時， XOR 就是 F，反之同證
所以程式碼就可以寫成如下
```cpp=
if (!((a && b) == (a || b)) == ans)
cout << "XOR\n" ;
```
但這樣似乎太過於複雜(不直觀)了，從結果還可以推出一個想法，就是 $a, b$ 改成 bool 值後
如果 `a != b` 就代表 true，也就是兩者相同 => flase，兩者不同 true
至於整數變成 bool 就把整數修成 $0,1$ 即可，最後就可以簡寫成下方程式碼片段
```cpp=
if (a > 0) a = 0 ; // 替換成類似 bool
if (b > 0) b = 0 ; // 替換成類似 bool
if ((a != b) == ans)
cout << "XOR\n" ;
```
要注意只要 AND OR XOR 都不符合就要輸出 IMPOSSIBLE
可以用 bool 值去判斷**有沒有任何一個**邏輯判斷符合
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int a, b, ans ; // 不可直接用 bool 會錯誤
bool any = false ; // 有任何一種邏輯正確
cin >> a >> b >> ans ;
// cout << a << ' ' << b << ' ' << ans << '\n' ;
if (a > 0) a = 1 ; // 替換成類似 bool
if (b > 0) b = 1 ; // 替換成類似 bool
// AND 判斷
if ((a && b) == ans) {
cout << "AND\n" ;
any = true ;
}
// OR 判斷
if ((a || b) == ans) {
cout << "OR\n" ;
any = true ;
}
// XOR 判斷(四種情況暴力解)
if (a && b && (ans == 0)) { // a 不為 0 且 b 不為 0
cout << "XOR\n" ;
any = true ;
}
else if (a && !b && (ans == 1)) { // a 不為 0 且 b 為 0
cout << "XOR\n" ;
any = true ;
}
else if (!a && b && (ans == 1)){ // a 為 0 且 b 不為 0
cout << "XOR\n" ;
any = true ;
}
else if (!a && !b && (ans == 0)) { // a 為 0 且 b 為 0
cout << "XOR\n" ;
any = true ;
}
// XOR 判斷(邏輯解)
if (!((a && b) == (a || b)) == ans) {
cout << "XOR\n" ;
any = true ;
}
// XOR 判斷(最簡解)
if ((a != b) == ans) {
cout << "XOR\n" ;
any = true ;
}
if (!any) // 三個邏輯都不吻合
cout << "IMPOSSIBLE\n" ;
return 0 ;
}
```
不直接用 bool 儲存 $a, b, ans$ 的原因是連續輸入 bool 值，第一個值不是 $1,0$ ，後續會出錯
### e286. 籃球比賽
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e286)
這題在APCS實作第一級中也是特別簡單的，因為要做的只有兩點
1. 主客分數的計算跟輸出
2. 判斷主隊最後**贏、輸或平手**
因為分數都是固定四節兩場，所以用 for 迴圈就可以直接計算完了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int win1 = 0, win2 = 0 ; // 主/客隊贏幾場
for (int j=0;j<2;j++) {
int a = 0, b = 0, tmp ; // 主隊分數、客隊分數
for (int i=0;i<4;i++) { // 輸入主隊分數
cin >> tmp ;
a += tmp ;
}
for (int i=0;i<4;i++) { // 輸入客隊分數
cin >> tmp ;
b += tmp ;
}
cout << a << ':' << b << '\n' ; // 輸出計算結果
if (a > b) // 主隊分數較高
win1++ ;
else // 客隊分數較高
win2++ ;
}
if (win1 == win2) // 平手
cout << "Tie" ;
else if (win1 == 2) // 主隊贏
cout << "Win" ;
else
cout << "Lose" ; // 客隊贏
return 0 ;
}
```
### f579. 1. 購物車
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f579)
這題就只有三個流程
1. 輸入要觀察的商品編號
2. 從**正負**商品編號來看那些商品被拿起/被放下
3. 判斷有幾個人**同時**買了要題目給定的兩個商品
題目說在一個人的購物流程中，會**拿商品**跟**放商品**，直到遇到 $0$ 才結束
所以可以用下方的方式來判斷**是否輸入完畢**
```cpp=
while (cin >> now)
if (now == 0) // 遇到 0 了所以結束了
break ;
```
再來就是用 IF 判斷有沒有拿到/放下題目給定的商品，最後在購物流程結束
就可以判斷有沒有**同時買下**題目給定的商品
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int a, b, n, ans = 0 ;
cin >> a >> b >> n ;
for (int i=0;i<n;i++) {
int num_a = 0, num_b = 0, now ; // a, b 拿的數量
while (cin >> now) {
if (now == 0)
break ;
if (now == a) // 拿了 a 商品
num_a++ ;
else if (now == -a) // 放了 a 商品
num_a-- ;
else if (now == b) // 拿了 b 商品
num_b++ ;
else if (now == -b) // 放了 b 商品
num_b-- ;
}
if (num_a > 0 && num_b > 0) // 都有拿
ans++ ;
}
cout << ans ;
return 0 ;
}
```
### f312. 1. 人力分配
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f312)
這題也是很簡單，只有用到極值跟迴圈而已，題目給定了兩個公式
* $y_1 = a_1 \times x_1^2 + b_1 \times x_1 + c_1$
* $y_2 = a_2 \times x_2^2 + b_2 \times x_2 + c_2$
因為要找出所有分配方式的收益最大值，所以用最暴力的方式就可以了
只要把工廠 $1$ 中分配 $0\sim n$ 個，看看個別收益是多少
所以用迴圈來一一計算跟判斷就可以了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int a1, b1, c1, a2, b2, c2, n, ans = INT_MIN ;
cin >> a1 >> b1 >> c1 ;
cin >> a2 >> b2 >> c2 ;
cin >> n ;
for (int i=0;i<=n;i++) { // 從 0 個員工到 n 個
int y1 = a1*i*i + b1*i + c1 ;
int y2 = a2*(n-i)*(n-i) + b2*(n-i) + c2 ;
ans = max(y1+y2, ans) ;
}
cout << ans ;
return 0 ;
}
```
### f605. 1. 購買力
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f605)
題目給 $n$ 個商品最近 $3$ 天的價格，依據條件購買，問**購買的商品數量**以及**費用總和**
所以輸入 $n$ 個商品的時候，還要一邊計算商品的費用，跟紀錄價格**最高**與**最低**的數值
後面用 IF 判斷式就可以知道最大值跟最小值差有沒有 $\ge d$，也就是要不要購買此商品
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, d, cost = 0, num = 0, now ;
// cost 是所有商品花費總額、num 是購買數量
cin >> n >> d ;
for (int i=0;i<n;i++) {
int max_n = -1, min_n = 101, sum = 0 ;
// 價格最高、價格最低、單一商品三天價格總和
for (int j=0;j<3;j++) {
cin >> now ;
sum += now ; // 單一商品價格總和新增
max_n = max(max_n, now) ; // 找最高價格
min_n = min(min_n, now) ; // 找最低價格
}
if (max_n-min_n >= d) { // 差值超過 d(可以購買)
num++ ;
cost += sum/3 ; // 購買價格是平均值
}
}
cout << num << ' ' << cost ;
return 0 ;
}
```
### g275. 1. 七言對聯
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g275)
這題是相對比較複雜的題目，因為有三個條件跟兩個一維陣列
不過這題跟之前的題目一樣，都是用 IF 判斷式 + 迴圈就可以解決了
如果硬要說有甚麼容易錯的，就是在**輸入資料時**可能是從 $0$ 開始
所以看到第 $1$ 個字其實是 index $0$ 的位置
在下方採用的方法是**直接擴充陣列的大小**，然後從 $1$ 開始輸入資料
這樣就可以很直覺的把題目描述跟 index 結合起來
下方的程式碼有些使用 for 迴圈來精簡程式碼，只需要記得一個條件只會違反(輸出)一次
加上 break 就可以在輸出後跳出迴圈
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[3][8] ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n ;
cin >> n ;
for (int i=0;i<n;i++) { // n 對對聯
for (int j=1;j<=2;j++) // 方便理解，從 1 開始輸入
for (int k=1;k<=7;k++) // 方便理解，從 1 開始輸入
cin >> A[j][k] ;
bool have = false ; // 是否違反任一個規則
for (int j=1;j<=2;j++) { // A: 每一句二四不同二六同
if (A[j][2] == A[j][4] || A[j][2] != A[j][6]) {
cout << 'A' ;
have = true ;
break ; // 只要有一句違反就全部違反(只輸出一次)
}
}
if (A[1][7] != 1 || A[2][7] != 0) { // B: 仄起平收
cout << 'B' ;
have = true ;
}
for (int k=2;k<=6;k+=2) { // k = 2, 4, 6 ， C: 上下相對
if (A[1][k] == A[2][k]) {
cout << 'C' ;
have = true ;
break ; // 只要有一格違反就全部違反(只輸出一次)
}
}
if (!have) // 三個規則都遵守
cout << "None" ;
cout << '\n' ;
}
return 0 ;
}
```
### g595. 1. 修補圍籬
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g595)
這題也是比較簡單的題目，只要一維矩陣 + for 迴圈 + IF 判斷式
不過這裡有一個小技巧可以介紹，就是**提前修補範圍邊界**
因為題目中說道斷掉的圍籬有可能位於最左/右邊
一般情況下要在 IF 判斷式當中**加入其他條件**才可以**避免出錯**
但是其實可以**虛構**一個**不存在的邊界**，比如這題就可以**往左右邊延伸一格**
並且題目說是找**左右側的最小值**，所以虛構的邊界只要**比題目定義的最大值還大**即可
如果在二維陣列當中用這個方法，那就是不需要判斷 $(x,y)$ 有沒有超出範圍
可以用一個題目**不存在的值**去補充邊界(例如 $-1$)，所以這題也不難
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int h[105] ; // 圍籬高度
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, sum = 0 ; // sum 是修補的高度總和
cin >> n ;
h[0] = 101, h[n+1] = 101 ; // 虛構修補邊界
for (int i=1;i<=n;i++) // 因虛構邊界移動位置從 1 開始
cin >> h[i] ;
for (int i=1;i<=n;i++) {
if (h[i] == 0) { // 遇到損壞的圍籬
h[i] = min(h[i-1], h[i+1]) ; // 這行可省略，題目沒要求
sum += h[i] ; // 新增修補高度總和
}
}
cout << sum ;
return 0 ;
}
```
### h026. 202001_1 猜拳
[題目連結](https://zerojudge.tw/ShowProblem?problemid=h026)
這題是 APCS 實作第一題當中最複雜的題目，因為如果用 if 去描述猜拳
尤其題目是給定 $0,2,5$ 三個數字，整體程式會變得比較**複雜**且很**容易寫錯**
所以在這裡利用陣列的方式(用 map 解決更輕鬆但不常用的別用)去輕鬆解決
只要在陣列當中利用 index **對應位置**放入會贏/輸的拳即可，如下所述
舉例來說，因為 $0$ 是石頭 $5$ 是布，所以陣列可以這樣寫 `A[0] = 5 ;`
這樣就可以**快速解決**題目敘述中的**兩個考點**，假設妹妹出 $S$、哥哥出 $F$
1. 判斷猜拳誰贏，只要看是 `F == A[S]` 還是 `S == A[F]` 即可
2. 如果妹妹連續兩輪出了一樣的拳，下一輪哥哥就會出打敗妹妹前兩輪的拳
剩下就是要注意因為有可能出現妹妹**兩輪出同樣拳**的可能性
所以至少要記錄妹妹的**前兩個拳**，或是像我一樣用**矩陣儲存**所有拳
還有要記得儲存結束猜拳時的回合數(除非平手就用 $N$ )
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int sis[11] ; // 妹妹準備的拳
int wins[6] = {5,-1,0,-1,-1,2} ; // 對手出 idx，要出 ws[idx] 才能贏
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, f, round, bwin = 2 ;
// round 是在第幾輪結束 bwin 0 是哥贏 1 是哥輸 2 是平手
cin >> f >> n ;
for (int i=0;i<n;i++) {
cin >> sis[i] ;
cout << f << ' ' ;
if (i >= 1) { // 可能有連續兩輪出同樣的拳
if (f == wins[sis[i]]) { // 哥哥贏了
round = i+1 ;
bwin = 0 ;
break ; // 結束猜拳
}
else if (sis[i] == wins[f]) { // 妹妹贏了
round = i+1 ;
bwin = 1 ;
break ; // 結束猜拳
}
if (sis[i] == sis[i-1])
f = wins[sis[i]] ; // 連續兩輪出同樣的拳
else
f = sis[i] ; // 否則跟妹妹上一輪一樣
}
else {
if (f == wins[sis[i]]) { // 哥哥贏了
round = i+1 ;
bwin = 0 ;
break ; // 結束猜拳
}
else if (sis[i] == wins[f]) { // 妹妹贏了
round = i+1 ;
bwin = 1 ;
break ; // 結束猜拳
}
f = sis[i] ; // 只能跟妹妹上一輪出一樣的拳
}
}
if (bwin == 0) // 哥哥贏了
cout << ": Won at round " << round ;
else if (bwin == 1) // 妹妹贏了
cout << ": Lost at round " << round ;
else // 平手
cout << ": Drew at round " << n ;
return 0 ;
}
```
### h081. 1. 程式交易
[題目連結](https://zerojudge.tw/ShowProblem?problemid=h081)
這題是比較簡單的模擬題，整段程式只需要實現**兩個功能**，也就是買入/賣出股票
再加上 for 迴圈跟 if 判斷式就可以完成整段程式，但是要注意的點有三個
1. 第一個時間點"一定"會買入股票 => 最初的 x = 第一個時間點的價格
2. 買進需要 `y >= (x+D)` 賣出需要 `y <= (x-D)` => if 判斷式
3. 持有股票才能賣出，無持有股票才能買進 => 用 bool 值判斷
最後就剩下計算買賣的利潤，跟**最後還持有**股票就**不計入**成本跟利潤當中
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, D, x, y, sum = 0, have = true ; // y: 當前價格
// x: 當前購入/賣出價格 sum: 利潤總和 have: 是否持有股票
cin >> n >> D ;
cin >> x ; // 在第一個時間點買進股票
for (int i=1;i<n;i++) { // 已經過一個時間點了
cin >> y ;
if (y >= (x+D) && have) { // 利潤足夠，賣出
sum += y-x ; // 更新利潤
have = false ; // 改成未持有股票
x = y ; // 更新賣出價格
}
else if (!have && y <= (x-D)) {
have = true ; // 改成持有股票
x = y ; // 更新購入價格
}
}
cout << sum ;
return 0 ;
}
```
### i399. 1. 數字遊戲
[題目連結](https://zerojudge.tw/ShowProblem?problemid=i399)
要判斷眾數的數量跟從大到小(去除重複)輸出，完全不複雜但可以講很多
在判斷眾數時可以用陣列儲存，其實不只是數字，字母數量也可以用**陣列儲存**
假設要找一個字串中的字母出現次數，就可以用 ASCII 去儲存字母**出現的次數**
所以比較出現過的數字在陣列當中的值，就可以知道眾數數量，比如輸入 $6,6,6$
`A[10] = {0,0,0,0,0,0,3,0,0,0} ;` 就可以知道 $6$ 出現 $3$ 次，其他的數都比較小
可能最直觀的比較方式是用**迴圈**一個個比較，但是因為只要比較**出現過的數字**
所以可以在數字出現時，一邊紀錄再一邊同時比較，最後可能會如下面所示
```cpp=
cin >> tmp ;
A[tmp] += 1 ; // 紀錄
P = max(A[tmp], P) ; // 比較
```
當然 C++ 有一個非常好用的運算，就是可以比較前先 $\pm1$，那程式會更精簡
```cpp=
P = max(++A[tmp], P) ; // 在比較之前先 +1
```
再來就是怎麼去除重複元素的輸出，並且從大到小，在這邊簡單介紹幾個方法
1. 前面存數字數量的陣列拿來用 => for 迴圈從 9 到 1 看有沒有
2. 用 C++ 預設排序(由小到大)後的元素從後往前輸出
3. 存到 set 裡面然後從後方輸出
第三項因為 set 是 STL 的東西，所以在這裡不贅述，第一項也是比較直觀的
所以我們重點放在第二項，上面的敘述沒有講到該如何去除重複元素
但是你只要仔細想想就知道，不論數字範圍是甚麼，只要重複元素就會在一起
```
{1,1,2,3,3,4,5,5,5,6,6}
0 1 2 3 4 5 6 7 8 9 10 (index)
```
上面就是一個很標準排序後的陣列，如果從最後面開始輸出，先輸出 $6$ ( index $10$ )
再來跑到 index $9$ 的時候就會遇到重複的數字，這時候只要判斷前一個數字跟現在數字**是否相同**
如果從後往前看的話，重複的數字前一個必定是一樣的數字，比如 index $6,7$ 的前一個 index $8$
所以最後只要判斷**前一個元素跟現在元素是否相同**就可以決定是否要輸出該元素了
當然這個方法只能在已經排序的陣列使用，使用 set 則會一次解決排序+去除重複
順便補充第一項方法的程式碼，用 for 迴圈 + if 判斷即可，如下所示
```cpp=
for (int i=9;i>=0;i--)
if (A[i] > 0) // 該數字有出現
cout << A[i] << ' ' ;
```
最後就剩下整段程式碼，會用 set 的人還是建議看過我講的**兩個方法**，算是**基礎加強**
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[3] ; // 三個數字
int num[10] = {0} ; // num[idx] 表示 idx 出現幾次
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int P = 0 ; // 出現最多次的數字個數
for (int i=0;i<3;i++) {
cin >> A[i] ;
P = max(++num[A[i]], P) ; // 在比較之前先 +1
}
sort(A,A+3) ; // 排序
cout << P << ' ' << A[2] << ' ' ; // 先輸出 P 跟最大的元素
for (int i=1;i>=0;i--)
if (A[i] != A[i+1]) // 只要前一個跟現在相同(重複元素)就不輸出
cout << A[i] << ' ' ;
return 0 ;
}
```
### i428. 1. 巴士站牌
[題目連結](https://zerojudge.tw/ShowProblem?problemid=i428)
這題也只要 for 迴圈 + 比大小就可以了，因為曼哈頓距離是兩個座標之間
也就是說總共只有 $n-1$ 個曼哈頓距離，所以可以先輸入一個座標
後面透過**輸入**跟**更新**座標的方式去計算不同的曼哈頓距離
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, x, y, nx, ny, n_max = 0, n_min = 1001 ;
// x y 前座標 nx ny 目前座標 n_max 是最大值 n_min 是最小值
cin >> n ;
cin >> x >> y ; // 要先有一個座標
for (int i=1;i<n;i++) { // 已經有輸入一個座標
cin >> nx >> ny ;
int sum = abs(x-nx) + abs(y-ny) ; // 計算曼哈頓距離
n_max = max(sum, n_max) ; // 更新最大值
n_min = min(sum, n_min) ; // 更新最小值
x = nx, y = ny ; // 更新前座標
}
cout << n_max << ' ' << n_min ;
return 0 ;
}
```
### j605. 1. 程式考試
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j605)
這題也不難，主要細節要求要注意而已，題目要求如下
1. 多個提交紀錄，有 $-1$ 就是嚴重錯誤
2. 要記錄第一次獲得最高分的時間點跟最高分
3. 最後總分有公式計算，要用最高分去計算
4. 如果總分是負數就輸出 $0$
因為公式當中有嚴重錯誤的次數，所以記得用變數紀錄次數
再來因為除了最高分外，還要記錄時間點，所以不能用 max，要用 if
最後記得輸出前套入公式，如果結果是負數就輸出 $0$
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, se = 0, score = 0, t, s, time = 0 ;
// se 是嚴重錯誤次數 score 是總分 time 是時間點
cin >> n ;
for (int i=0;i<n;i++) {
cin >> t >> s ;
if (s == -1) // 嚴重錯誤
se++ ;
else {
if (s > score) { // 比較分數
score = s ; // 更新最高分數
time = t ; // 更新時間點
}
}
}
score = score - n - se*2 ; // 分數最後計算
if (score < 0) // 負數則計為 0
cout << 0 ;
else
cout << score ;
cout << time ; // 第一次獲得最高分的時間點
return 0 ;
}
```
### k731. 1. 路徑偵測
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k731)
這題不難，但是有一個東西可以延伸講，首先先說明**幾個題目重點**
1. 僅會垂直或水平方向移動
2. 初始方向向"右"
3. 左轉、右轉、迴轉的個數分別為多少
題目給定多個座標，所以**最直觀**的方式就是用 if 判斷式，根據四個方向判斷**轉彎方向**
而且如果用座標的方式去理解，如果新的座標 $>$ 原本座標 $nx > x$，那就是向東
其他方向也可以依據**這個方式**判斷，但是如果你要寫 if 去判斷轉彎
那一個方向至少要寫**三個**，也就是說要寫 $12$ 個 if 判斷才能**包含所有轉彎的可能**
但是如果用"數字"表示方向，整個過程會變得很簡單，首先我們把東方當作 $0$
接下來順時針設定數字，最後會得到 東: $0$，南: $1$，西: $2$，北: $3$
從方位來看，就知道 數字 $+1$ 是右轉，反過來說，新的方向 $-$ 舊的方向 $= 1$ 也是右轉
但是在方向是北邊的時候會出現錯誤，因為 $3+1=4$，已經超出定義的範圍了
所以這時候**取餘數**就出現了，如果 `(舊座標 +1) % 4 == 1` 就是右轉
迴轉跟左轉也可以用相同的概念去解，最後會得到下列三個式子，新方向 nto、舊方向 to
```cpp=
(to+1)% 4 == nto // 右轉了
(to+2)% 4 == nto // 迴轉了
(to+3)% 4 == nto // 左轉了
```
當然反過來的邏輯也是正確的，一樣可以從新座標回推轉彎方向
```cpp=
(nto+1)% 4 == to // 左轉了
(nto+2)% 4 == to // 迴轉了
(nto+3)% 4 == to // 右轉了
```
最後我用陣列儲存各種轉彎的次數，因為輸出比較方便，只要不要搞混就可以
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int ans[3] = {0} ; // 左轉、右轉、迴轉
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, x, y, nx, ny, to = 0, nto ; // nto 是下一個方向
// 目前座標(x,y) 下一個座標(nx,ny) to 是方向 0,1,2,3
cin >> n ;
cin >> x >> y ; // 初始方向向右(to = 0)
for (int i=1;i<n;i++) { // 已經有一個座標 所以i = 1
cin >> nx >> ny ; // 新座標
if (nx > x)
nto = 0 ; // 新方向 東(x 變大)
else if (ny < y)
nto = 1 ; // 新方向 南(y 變小)
else if (nx < x)
nto = 2 ; // 新方向 西(x 變小)
else if (ny > y)
nto = 3 ; // 新方向 北(y 變大)
// cout << nto << '\n' ;
if (to == (nto+1)%4) // 左轉
ans[0]++ ;
else if (to == (nto+2)%4) // 迴轉
ans[2]++ ;
else if (to == (nto+3)%4) // 右轉
ans[1]++ ;
to = nto, x = nx, y = ny ; // 更新方向跟座標
}
for (int i=0;i<3;i++)
cout << ans[i] << ' ' ; // 照題目輸出
return 0 ;
}
```
### m370. 1. 機械鼠
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m370)
這題也不難，整理一下題目重點
1. 老鼠一開始在定點，且只會往一個方向直行
2. 求老鼠往哪邊吃比較多 => 左邊跟右邊食物數量比較
3. 同時求老鼠往左右(方向根據點 $2$ )最後位置(距老鼠最遠)
因為從頭到尾老鼠不會轉彎，所以只需要知道老鼠一開始往左還是往右就可以了
不需要去模擬老鼠的行動軌跡，根據點 $2$，只用 if 就可以判斷食物位置(左或右)
同時記錄**左(右)邊食物數量**跟**左右邊個別距離老鼠最遠的位置**
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int x, n, nl = 0, nr = 0, nmin = 101, nmax = -101 ;
// nl 老鼠左邊的食物數量，nr 老鼠右邊的食物數量
// nmin 最左邊的食物位置 nmax 最右邊的食物位置
cin >> x >> n ;
for (int i=0, tmp;i<n;i++) {
cin >> tmp ;
if (tmp > x) // 在老鼠右邊
nr++ ;
else // 在老鼠左邊
nl++ ;
nmax = max(nmax, tmp) ; // 更新最大值
nmin = min(nmin, tmp) ; // 更新最小值
}
if (nr > nl) // 右邊比較多
cout << nr << ' ' << nmax ;
else // 左邊比較多
cout << nl << ' ' << nmin ;
return 0 ;
}
```
### m931. 1. 遊戲選角
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m931)
這題要求第二名的能力值會相對第一名**更複雜一點**，但是也不難
只要先**判斷好第一名**，那第二名其實就是**其餘人的第一名**
所以這裡用多個變數表示**第一名跟第二名的數據**
再配合 if 判斷式就可以結束了，這邊幫各位整理一下新數據的可能
1. 新能力值是當前最大的(當第一名) => 原本的第一名**變成**第二名
2. 新能力值比第一名小但比第二名大 => 新數據**取代**原本的第二名
3. 新能力值比第一、二名都小 => 前兩名沒變動(跳過)
所以根據三種可能寫出對應的部分即可(第三種可以不寫)
不過可能有人想用 sort 去比較，這個就需要**自訂義比較函式**
在這邊淺淺的提一下，數值用 陣列 + pair 或是 vector + pair 都可以
用 cmp 函式表示比較函式，在當中寫入能力值的公式就可以了，程式碼如下
```cpp=
#define P pair<int,int>
#define FF first
#define SS second
bool cmp1(P p1, P p2) {
int power1 = p1.FF*p1.FF + p1.SS*p1.SS ; // p1 的能力值
int power2 = p2.FF*p2.FF + p2.SS*p2.SS ; // p2 的能力值
return power1 > power2 ; // 由大到小排序
}
P powers[21] ; // 放入每個人的數值 {a, d}
```
當然這是非常偷懶的作法，因為這題是問第二名，所以用第一種方法**不會太複雜**
我還是推薦要把第一種作法的**思路釐清**，對於基礎比較有幫助
完整程式碼如下，再根據需求自己作**刪減片段**、**輸出觀察**等等
```cpp=
#include<bits/stdc++.h>
using namespace std ;
#define P pair<int,int>
#define FF first
#define SS second
bool cmp1(P p1, P p2) {
int power1 = p1.FF*p1.FF + p1.SS*p1.SS ; // p1 的能力值
int power2 = p2.FF*p2.FF + p2.SS*p2.SS ; // p2 的能力值
return power1 > power2 ; // 由大到小
}
P powers[21] ; // 放入每個人的數值 {a, d}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, fa = -1, fd = -1, sa, sd, a, d ;
int first = -1, second = -1 ;
// first 最大的能力值，second 第二大的能力值
// fa,fd 最大(能力值)數值 sa, fa 第二大(能力值)數值
cin >> n ;
for (int i=0;i<n;i++) {
cin >> a >> d ;
int power = a*a + d*d ; // 新的能力值
if (power > first) { // 新的第一名
second = first, first = power ; // 原本第一名變第二名
sa = fa, sd = fd ;
fa = a, fd = d ; // 更新數值
}
else if (power > second) { // 新的第二名
second = power ; // 更新能力值
sa = a, sd = d ; // 更新數值
}
}
// for (int i=0;i<n;i++) { // 排序解法(先放入陣列)
// cin >> a >> d ;
// powers[i] = {a,d} ;
// }
// sort(powers, powers+n, cmp1) ;
// sa = powers[1].FF, sd = powers[1].SS ;
cout << sa << ' ' << sd ;
return 0 ;
}
```
## APCS 三級分難度
### m800. 辦公室 (Office)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m800)
題目解析 :
首先要把題目的概念先搞清楚，一個人的工作表現會因為四周的人改變
改變的方式是"前後左右超過一半的人"工作分數比他高，**他的工作分數就變高**
反之亦然，不過這裡還有一個重點，就是改變是發生在**明天的最開始**
比如下面圖片的例子，如果改變發生在**同一天**，就會出現**錯誤**
最左邊的圖是起始圖，因為藍色格子的四周都比他低，所以他會 $-1$
如果是**同一天改變**的話，遇到橘色格子時四周是 $3,4,1$，所以橘色格子"不會"有改變
但是如果是正確的流程(明天才改變)，遇到橘色格子時四周是 $4,4,1$，所以會 $+1$
其他就是基本的遍歷跟運算，整理幾個重點
1. 要兩個陣列紀錄今天跟改變後(明天最開始)的工作分數
3. 前後左右人數要看**自己是否在最邊邊**
4. 每天結束後要記得更新，也就是前面說的 "明天的最開始"
5. 分數改變是指如果該位置 $+1$，總分數改變就 $+1$，反之亦然
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int mm[4][2] = {0,1,0,-1,1,0,-1,0} ; // 四周
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
// ans 是改動的數字總和
int h, w, k, ans = 0 ;
cin >> h >> w >> k ;
vector<int> Gtd[h], Gtm[h] ; // 今天/明天的辦公室
for (int i=0;i<h;i++) { // 紀錄最開始的工作分數
for (int j=0, tmp;j<w;j++) {
cin >> tmp ;
Gtd[i].push_back(tmp), Gtm[i].push_back(tmp) ;
}
}
for (int p=0;p<k;p++) { // 總共有 k 天
for (int i=0;i<h;i++) {
for (int j=0;j<w;j++) {
// 工作分數比較高/低、此人的工作分數、附近的人數
int b = 0, s = 0, now = Gtd[i][j], bs = 0 ;
for (int idx=0;idx<4;idx++) { // 四周
// 四周人的 x y
int nx = i+mm[idx][0], ny = j+mm[idx][1] ;
if (nx >= 0 && nx < h && ny >=0 && ny < w) {
// 在範圍內才是人
bs++ ; // 四周的人數
// 工作分數比他高
if (Gtd[nx][ny] > now) b++ ;
// 工作分數比他低
if (Gtd[nx][ny] < now) s++ ;
}
}
// 超過一半的人工作分數比他高
if (b > bs/2) ans++, Gtm[i][j]++ ;
// 超過一半的人工作分數比他低
if (s > bs/2) ans--, Gtm[i][j]-- ;
}
}
// 明天的最開始
for (int i=0;i<h;i++)
for (int j=0;j<w;j++)
Gtd[i][j] = Gtm[i][j] ;
}
cout << ans ;
return 0 ;
}
```
### m802. 填字遊戲 (Puzzle)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m802)
題目解析 :
其實這提到最後也就只有兩個錯誤情況
1. 單字**超出題目規定範圍**
2. 單字的**字母與該格衝突**
超出規定範圍比較簡單，就計算目前位置座標 + 字串長度 看會不會超過即可
第二點就是要在**填入英文字母** $C$ 的同時去**判斷該格是空的**還是 $C$
如果都不是代表產生衝突了，也是錯誤，不過這題最重要的是 $x$ 跟 $y$ 的位置
因為這題跟平常不一樣，$y$ 是代表上下，所以要用 $v[y][x]$
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, x, y, len ;
char c ;
string s ;
cin >> n >> m ;
vector<char> ctmp(n+1,' ') ;
vector<vector<char>> v(n+1,ctmp) ; // n*n 的空格
for (int i=0;i<m;i++) {
cin >> c >> s >> x >> y ;
len = s.size() ; // 字串長度
if (c == 'V') { // 由上到下
if (y+len > n) { // 超出範圍
cout << "No" ;
return 0 ;
}
for (int j=0;j<len;j++) { // 填入字母與判斷是否有錯
if (v[y+j][x] == ' ' || v[y+j][x] == s[j])
v[y+j][x] = s[j] ;
else {
cout << "No" ;
return 0 ;
}
}
}
else { // 由左到右
if (x+len > n) { // 超出範圍
cout << "No" ;
return 0 ;
}
for (int j=0;j<len;j++) { // 填入字母與判斷是否有錯
if (v[y][x+j] == ' ' || v[y][x+j] == s[j])
v[y][x+j] = s[j] ;
else {
cout << "No" ;
return 0 ;
}
}
}
}
cout << "Yes" ;
return 0 ;
}
```
### k398. 密室逃脫 (Escape)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k398)
題目解析 :
這題有幾個重點，題目敘述中都有出現
1. 會照 右、下、左、上 的順序進行
2. 有一行數字代表要走的步數
3. 撞到牆壁就停止
4. 走過的路徑都用 '*'，沒走過都用 ' . '
要達到第一點很簡單，只要用之前講過的二維陣列儲存 dx、dy 並且搭配數字代表方向即可
第二點由於數字間沒有空格，所以可以用字元轉成數字的方式解決，我是採用字串，也是同樣道理
第三點跟一般遇到邊界的情況一樣，只要遇到邊界就停止繼續並且結束這個方向
第四點我透過將地圖預設成沒走過的情況來解決問題，接下來就是關於細節的打磨
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int mm[4][2] = {0,1, 1,0, 0,-1, -1,0} ;
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int r, c ;
cin >> r >> c ;
vector<char> tmp(c, '.') ; // 預設地圖為沒走過
vector<vector<char>> maps(r, tmp) ;
string s ; // 要走的步數
cin >> s ;
maps[0][0] = '*' ; // 最左上角一定走過
int x = 0, y = 0, n = s.size() ;
for (int i=0;i<n;i++) { // 可以一次找出步數與方向
for (int j=0;j<s[i]-'0';j++) {
x += mm[i%4][0], y += mm[i%4][1] ;
if (x == r || x == -1 || y == c || y == -1) { // 遇到邊界
x -= mm[i%4][0], y -= mm[i%4][1] ; // 退回一步
break ;
}
maps[x][y] = '*' ; // 走過
}
}
for (int i=0;i<r;i++) { // 輸出元素
for (int j=0;j<c;j++)
cout << maps[i][j] ;
cout << '\n' ;
}
return 0 ;
}
```
### APCS-2016/06 b965. 第 2 題 矩陣轉換
[題目連結](https://zerojudge.tw/ShowProblem?problemid=b965)
題目解析 :
這題看完題目後大致可以先整理成三個重點
1. 會給**已經轉換後**的矩陣
2. 給定的轉換順序是從前到後，所以逆推需要反轉順序
3. 最後需要輸出最開始矩陣的列、行和所有元素
至於轉換中的細節一樣要用反推的邏輯去思考，比如旋轉題目是說順時針轉 90 度
但在實際的過程中我們要用逆時針轉 90 度去反推上一個矩陣，而翻轉就沒有正推或反推的差異
剩下翻轉和旋轉的細節建議自己用頭腦去想，畫出來能更快找到規律
不過按照現在實作題的難度，很可能會給順逆時針的旋轉跟上下左右的翻轉，所以如果已經理解原理，並且通過的人，可以順便把剩下兩種寫出來
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0) ;
cin.tie(0), cout.tie(0) ;
int r, c, m, t ;
while (cin >> r >> c >> m) { // 3 2 3
vector<int> k(m,0) ;
vector<int> tmp(11,0) ;
vector<vector<int>> A1(11,tmp) ; // 反推前的矩陣
vector<vector<int>> A2(11,tmp) ; // 反推後的矩陣
for (int i=0;i<r;i++)
for (int j=0;j<c;j++)
cin >> A1[i][j] ;
for (int i=0;i<m;i++)
cin >> k[i] ; // 0 是旋轉 1 是翻轉
reverse(k.begin(),k.end()) ; // 逆推需反轉順序
for (auto it:k) {
if (it == 0) { // 逆時針旋轉 90 度
for (int i=0;i<c;i++) {
for (int j=0;j<r;j++) {
A2[i][j] = A1[j][c-i-1] ;
}
}
A1 = A2 ;
t = r ;
r = c ;
c = t ;
}
else { // 上下翻轉
for (int i=0;i<r;i++) {
for (int j=0;j<c;j++) {
A2[r-i-1][j] = A1[i][j] ;
}
}
A1 = A2 ;
}
}
cout << r << ' ' << c << '\n' ; // 輸出行列
for (int i=0;i<r;i++) {
for (int j=0;j<c-1;j++) {
cout << A1[i][j] << ' ' ;
}
cout << A1[i][c-1] << '\n' ; // 嚴格規定輸出
}
}
return 0 ;
}
```
### c291. APCS 2017-0304-2小群體
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c291)
題目解析 :
這是跳跳布朗尼的變化版，也要考慮走過(已有小群體)的人，剩下只要從頭判斷共有幾個小群體
其實跟前面的精靈王國也有異曲同工之妙，但是這題是問有幾個小群體
因為是早期的題目，難度太低，放現在可能在後面問編號 $x$ 所在的小群體有哪些人
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
int n, ans = 0, idx = 0, t ;
cin >> n ;
vector<int> num(n,0) ;
vector<bool> gone(n,false) ; // 判斷已走過(有群體的)
for (int i=0;i<n;i++)
cin >> num[i] ;
while (n > idx) {
// cout << idx << ' ' ;
t = idx ;
if (!gone[t]) { // 判斷是否有群體了
ans++ ;
gone[t] = true ;
while (!gone[num[t]]) { // 去找現在群體所有人
gone[num[t]] = true ;
t = num[t] ;
}
}
idx++ ;
}
cout << ans ;
return 0 ;
}
```
### c292. APCS2017-0304-3數字龍捲風
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c292)
題目解析 :
這題很明顯是要看走訪順序的規律，首先整理關於方向的三點
1. 方向用數字代表 ( $0:$ 左、$1:$ 上、$2:$ 右、$3:$ 左)
2. 走完特定格數後往順時針轉 $90$ 度，也就是數字 $+1$
3. 因為數字只有在 $0\sim3$ 中，所以要取餘
從這三點可以解決轉向的問題了，但是**格子的規律**還沒走完
如果先不考慮上下左右的影響，把各個方向的走的格數**寫成一個陣列**，會如下
{$1,1,2,2,3,3,...,n-1,n-1,n-1$} 也就是說，數字會從 $1\sim n-1$ 都跑兩次，$n-1$ 會多一次
所以只要把次數跟轉向都搞清楚就可以了，下方的程式碼用到兩個技巧
1. 使用 $mm[\ i\ ]$ 儲存方向為 $i$ 時的 $dx$ 跟 $dy$
2.
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int maps[50][50] ;
int mm[4][2] = {0,-1,-1,0,0,1,1,0} ; // 方向改數字
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, to ;
cin >> n >> to ; // 陣列大小、方向
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
cin >> maps[i][j] ; // 儲存陣列
int x = n/2, y = n/2 ; // 中心點
cout << maps[x][y] ;
for (int i=1;i<n;i++) { // 數字從 1~n-1
for (int j=0;j<2;j++) { // 每個數字重複兩次
for (int k=0;k<i;k++) { // 走的格數
x = x+mm[to][0], y = y+mm[to][1] ;
cout << maps[x][y] ;
}
to = (to+1) % 4 ; // 走完格數後轉向
}
}
for (int i=0;i<n-1;i++) {
x = x+mm[to][0], y = y+mm[to][1] ; // 最後的 n-1 要再走一次
cout << maps[x][y] ;
}
return 0 ;
}
```
### c295. APCS-2016-1029-2最大和
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c295)
題目解析 :
看完題目後大致可以知道兩點
1. 題目要求在群中的最大值，這可以在輸入數字的時候就判斷
2. 要求輸出各群中的最大值中所有可以整除各群最大值總和的數字
所以第一點只要在輸入數值時順便計算即可
至於第二點要用到各群最大值，也就是說各群最大值要儲存起來，最後才能用
還有因為題目是嚴格輸出，所以不能直接輸出數字跟空格
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
int n, m, max_num = 0, tmp, num = 0 ;
bool have = false ;
cin >> n >> m ;
vector<int> r1(m,0) ;
vector<vector<int>> A(n,r1) ; // 數值
vector<int> ans ; // 各群選出的最大值
vector<int> out ; // 輸出的答案
for (int i=0;i<n;i++) {
tmp = 0 ;
for (int j=0;j<m;j++) {
cin >> A[i][j] ;
tmp = max(tmp, A[i][j]) ; // 找出群中最大值
}
ans.push_back(tmp) ;
max_num += tmp ; // 各群最大值總和
}
cout << max_num << '\n' ;
for (int i=0;i<n;i++) {
if (max_num % ans[i] == 0) {
out.push_back(ans[i]) ; // 放入答案
have = true ;
num++ ;
}
}
if (!have)
cout << -1 ;
else {
for (int i=0;i<num-1;i++) {
cout << out[i] << ' ' ;
}
cout << out[num-1] ;
}
return 0 ;
}
```
### c462. apcs 交錯字串 (Alternating Strings)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c462)
這題最直覺的方式就是從頭跑字串然後去找最長的交錯字串
但是這樣的複雜度會變很大 $O(n^2)$，所以可以先找到大寫跟小寫的連續數量
比如 "AAaaBBBcccc"，就是 $2,\ 2,\ 3,\ 4$，假設此時 $k = 2$
最長的交錯字串會是 "AAaaBB"，從例子可以發現，如果當下連續數量 $== k$
那就可以繼續找下一個大(小)寫，但是如果連續數量 $> k$，那麼先前的交錯字串只能結束
然後再開啟新的交錯字串，在例子當中就是遇到 "BBB"，前面的 "AAaa" 遇到 "BBB" 後會變成 "AAaaBB"，然後停止
而新的交錯字串就是 "BB"，最後再遇到 "cc"，組成 "BBcc"，但長度還是比較小，所以不是答案
最後做個總結 :
1. 統計字串中連續大(小)寫數量
2. 連續數量 $== k$，就代表字串長度 $+k$，且可以繼續接字串(AA 遇到 aa)
3. 連續數量 $> k$，就代表字串長度 $+k$，只能開新的字串 (AAaa 遇到 BBB)
4. 連續數量 $< k$，就代表字串長度不變，也不能開新的字串(AAaa 遇到 B)
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, len, num = 1 ;
bool last_big = false, out = false ; // 先前字母是大寫
string s ;
vector<int> sbnum ;
cin >> n >> s ;
len = s.size() ; // 字串長度
if (s[0]-'A' < 26)
last_big = true ; // 判斷 s[0] 是大寫還是小寫
for (int i=1;i<len;i++) { // 判斷連續數量
if (last_big && (s[i]-'A') < 26) // 上一個跟現在都大寫
num++ ;
else if (last_big) { // 現在是小寫
sbnum.push_back(num) ;
if (num >= n) // 至少有一個交錯字串
out = true ;
num = 1 ;
last_big = false ;
}
else if (!last_big && (s[i]-'A') > 26) // 上一個跟現在都小寫
num++ ;
else { // 現在是大寫
sbnum.push_back(num) ;
if (num >= n)
out = true ;
num = 1 ;
last_big = true ;
}
}
sbnum.push_back(num) ; // 最後的連續大/小寫
if (num >= n)
out = true ;
if (!out) { // 缺少足夠連續字母 => 不可能有交錯字串
cout << 0 ;
return 0 ;
}
int max_num = 0, now_num = 0 ;
for (int i:sbnum) { // 判斷連續數量跟 n 的關係
// cout << i << ' ' ;
if (i == n) now_num += n ; // 目前的交錯字串可以直接往下
else if (i > n) { // 目前的交錯字串結束，新開一個交錯字串
max_num = max(max_num, now_num+n) ;
now_num = n ;
}
else { // 目前的交錯字串結束，但字母數量不夠開新的交錯字串
max_num = max(max_num, now_num) ;
now_num = 0 ;
}
}
max_num = max(max_num, now_num) ; // 最後的比較
cout << max_num ;
return 0 ;
}
```
### e287. 機器人的路徑
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e287)
題目敘述後大概可以整理幾個重點
1. 起點是圖中最小值的位置，可以在存圖的過程中判斷
2. 只能往上下左右走，並且要前往**最小且沒走過**的數值
3. 判斷走過可以利用 **bool 陣列**或是直接把點**數值改成範圍外的值**
4. 總和值相加要在點數值**更改之前**
而一直走可以用 bool 判斷，有走到新點就可以繼續走，如果**位置不變就停止**
最後實作上就剩下一些小細節要注意而已，比如避免無限迴圈等等
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int mm[4][2] = {-1,0,1,0,0,-1,0,1} ; // 上下左右
int maps[105][105] = {} ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, maxn = INT_MAX, sx, sy, ans = 0 ;
cin >> n >> m ;
for (int i=0;i<n;i++) { // 存圖並找到最小值位置
for (int j=0;j<m;j++) {
cin >> maps[i][j] ;
if (maps[i][j] < maxn) { // 找最小值位置
maxn = maps[i][j] ;
sx = i, sy = j ;
}
}
}
while (true) { // 走到直到沒有路
int fx = sx, fy = sy ;
ans += maps[sx][sy] ; // 走過路的值總和
maps[sx][sy] = -1 ; // 設成走過
maxn = INT_MAX ;
for (int i=0;i<4;i++) {
int nx = sx + mm[i][0], ny = sy + mm[i][1] ;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] != -1 && maps[nx][ny] < maxn) {
maxn = maps[nx][ny] ;
fx = nx, fy = ny ;
}
}
if (sx == fx && sy == fy) break ;
sx = fx, sy = fy ; // 確定前往的方向
}
cout << ans << '\n' ;
return 0 ;
}
```
### g276. 2. 魔王迷宮
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g276)
(建議先用紙筆模擬過一遍對照輸出，才能確定自己的理解是否正確)
這題特別難實作，我把題目敘述拆分成多個步驟方便理解題目的意思
題目當中同一個動作是同時發生的，比如移動，就是所有魔王一起移動
可能有些人還是抓不太到，在這邊先說魔王消失的條件
1. 踩到炸彈(並非當回合放下的)
2. 離開題目規定的區域
炸彈消失的條件只有**被魔王踩到**，且在同一位置的炸彈全部消失
最後把題目敘述拆成多個步驟
1. 魔王放下炸彈 -> 移動
2. 根據條件判斷+刪除魔王 + 判斷炸彈消失
3. 刪除炸彈
4. 從步驟 $1$ 開始重複執行直到沒有魔王
5. 判斷地圖上還剩多少"格"有炸彈(炸彈數量不重要)
根據題目敘述，我們大概可以知道需要幾個陣列或 vector 儲存資料
考慮到要判斷魔王座標跟炸彈座標，每一個魔王的**座標**都需要儲存，魔王**移動的值**也需要儲存
而炸彈的座標可以用二維 bool 陣列上的點表示，用來表示**有沒有炸彈**
但是魔王就**不適合**放在二維陣列上了，因為魔王要**頻繁地移動**
最後還需要一個陣列表示**哪個座標上的炸彈要消失**
因為在判斷魔王消失的時候，多個魔王踩到同一位置炸彈**都必須消失**
所以如果把炸彈消失跟魔王消失放在一起會導致同位置上**其餘魔王存活**
這也是為什麼上述的步驟需要將 $3,4$ 拆開
至於被踩到的炸彈可以在炸彈的二維陣列上多加一個狀態
表示已經被消失了，避免 vector 重複丟入同個座標
或是用一個 set 儲存座標，也有避免重複計算的特性
最後計算炸彈數的方式直接用二維 bool 陣列計算就可以了
這題的難點在於模擬的情況比較複雜，而且要注意的細節很多
所以在寫到一半時，適時地輸出數值看看很重要
我基本上在每個步驟上都加入一個輸出方便觀察 + debug
```cpp=
#include<bits/stdc++.h>
using namespace std ;
#define P pair<int,int>
#define FF first
#define SS second
struct bm {
bool have = false ; // 是否有炸彈
bool live ; // 炸彈是否還在
};
bm maps[105][105] = {} ; // 放炸彈 + 表示炸彈狀態
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, k, r, c, s, t ;
vector<P> kloc ; // 魔王位置
vector<P> kmm ; // 魔王移動
cin >> n >> m >> k ;
vector<bool> klive(k, true) ; // 魔王的存活
for (int i=0;i<k;i++) { // 輸入
cin >> r >> c >> s >> t ;
kloc.push_back({r,c}) ;
kmm.push_back({s,t}) ;
}
while (true) {
bool brk = true ; // 判斷是否沒有魔王
for (int i=0;i<k;i++) { // 步驟 1
if (!klive[i])
continue ;
brk = false ;
// cout << i << ": " ;
int x = kloc[i].FF, y = kloc[i].SS ;
int mx = kmm[i].FF, my = kmm[i].SS ;
maps[x][y].have = true ; // 放下炸彈
maps[x][y].live = true ;
kloc[i].FF = x+mx ; // 移動
kloc[i].SS = y+my ;
// cout << "from " << x << ',' << y << '\n' ;
}
if (brk) break ;
vector<P> boom ;
for (int i=0;i<k;i++) { // 步驟 2
if (!klive[i])
continue ;
int x = kloc[i].FF, y = kloc[i].SS ;
if (x < 0 || x >= n || y < 0 || y >= m) {
klive[i] = false ;
// cout << i << " out : " << x << ',' << y << '\n' ;
}
else if (maps[x][y].have) {
if (maps[x][y].live) { // 炸彈還未放入刪除
boom.push_back({x,y}) ; // 放入刪除
maps[x][y].live = false ; // 設成已刪除
}
klive[i] = false ; // 魔王死掉
}
}
for (P it:boom) // 步驟 3
maps[it.FF][it.SS].have = false ;
}
int ans = 0 ;
for (int i=0;i<n;i++) {// 步驟 4
for (int j=0;j<m;j++) {
// cout << maps[i][j].have << ' ' ;
if (maps[i][j].have)
ans++ ;
}
// cout << '\n' ;
}
cout << ans ;
return 0 ;
}
```
### g596. 2. 動線安排
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g596)
這題也是比較複雜的題目，我會用舉例+拆步驟的方式講解，先抓一下題目重點
1. 木樁有加入( $t=0$ )跟拔除( $t=1$ )的動作
2. 加入木樁 $A$ 時會向上下左右找木樁 $B$，如果有就拉一條線在 $A,B$ 之間
3. 如果新加入的木樁在線上，就把該位置的線"**全部**"清除，再加入木樁並按照點 $2$ 拉線
4. 拔除木樁時，木樁上的線也要被拔除
5. 木樁要放的位置一定沒有木樁，要拆木樁的位置一定有木樁
點 $1$ 跟點 $2$ 都不難理解，但點 $3$ 可能會讓某些人產生誤會，如下所示
| 木樁A | 線 1 | 線 1 | 線 1 | 木樁B |
|:----:|:----:|:----:|:----:|:----:|
| 1 | 2 | 3 | 4 | 5 |
假如木樁 $A$ 跟木樁 $B$ 中間已經有線 $1$，這時候要加入木樁 $C$ 到 $3$ 的位置
那勢必線 $1$ 就要被拆除，然後才可以加入木樁 $C$ 並進行下一步的拉線
| 木樁A | 空 | 空 | 空 | 木樁B |
|:----:|:----:|:----:|:----:|:----:|
| 1 | 2 | 3 | 4 | 5 |
| 木樁A | 線 3 | 木樁C | 線 2 | 木樁B |
|:----:|:----:|:----:|:----:|:----:|
| 1 | 2 | 3 | 4 | 5 |
如圖所示，我故意**用編號來區分不同線**，線 $1$ 在 $A,B$ 之間，線 $2$ 在 $B,C$ 之間，線 $3$ 在 $A,C$ 之間
所以如果在加入木樁 $C$ 之前把木樁 $B$ 拔除，那所有連著木樁 $B$ 的線，也就是線 $1$，**全都要被拆除**
但如果是在加入木樁 $C$ 之後才拔除木樁 $B$，那**只需要**拔除線 $2$ 即可
這樣的差異會導致結果不同，要注意**拔線時的策略**，不過可以簡化流程
假設有一個木樁的**上下左右一格**有線方向指向到木樁，那一定跟木樁連線
同時代表此木樁在那個方向**有另外一個木樁**跟它連線
而且在加入木樁時也不必先拆線再加入，因為雖然我上面用編號區分線的不同
但只是為了說明拔除木樁時怎麼拆線，實際在題目中不需要刻意區分，直接覆蓋即可
最後再說一下連線的概念，因為可以**上下左右連線**，所以線可能是橫的也可能是直的
也有可能同一格橫的直的都有，所以最後地圖會有**五種**情況 : 空、木樁、橫線、直線、橫直線
遇到加入木樁的情況，拆分步驟
1. 先在該位置設立木樁
2. 往上下左右找木樁，如果找到就開始拉線
3. 拉線時考慮橫直線的可能性
遇到拆除木樁的情況；拆分步驟
1. 先拆除該位置的木樁
2. 確定上下左右有正確方向的線後就開始找木樁
3. 拆線時要考慮橫直線拆成橫線或直線，不可直接全拆
最後在每次執行之後都要跑過整個地圖計算有線或木樁的格數
還有程式碼當中有些小技巧可以拿去用
在找木樁的時候因為不會超過地圖範圍，所以可以用 for 迴圈設定範圍
就不需要用 while 迴圈重複判斷範圍條件了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
char maps[100][100] ; // . - | + @ 空 橫 直 橫直 木樁
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, h, r, c, t, ans = 0, now ;
cin >> n >> m >> h ;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
maps[i][j] = '.' ; // 先將場地初始化
for (int k=0;k<h;k++) {
cin >> r >> c >> t ;
if (t == 0) { // 加入木樁
maps[r][c] = '@' ;
int x = -1, y = -1 ;
for (int i=r+1;i<n;i++) { // 向下找木樁
if (maps[i][c] == '@') { // 找到了
x = i, y = c ;
break ;
}
}
if (x != -1) { // 找到了
for (int i=r+1;i<x;i++) { // 考慮橫直線
if (maps[i][y] == '.')
maps[i][y] = '|' ;
else if (maps[i][y] == '-')
maps[i][y] = '+' ;
}
}
x = -1, y = -1 ;
for (int i=r-1;i>=0;i--) { // 向上找木樁
if (maps[i][c] == '@') {
x = i, y = c ;
break ;
}
}
if (x != -1) {
for (int i=r-1;i>x;i--) { // 考慮橫直線
if (maps[i][y] == '.')
maps[i][y] = '|' ;
else if (maps[i][y] == '-')
maps[i][y] = '+' ;
}
}
x = -1, y = -1 ;
for (int i=c+1;i<m;i++) { // 向右找木樁
if (maps[r][i] == '@') {
x = r, y = i ;
break ;
}
}
if (y != -1) {
for (int i=c+1;i<y;i++) { // 考慮橫直線
if (maps[r][i] == '.')
maps[r][i] = '-' ;
else if (maps[r][i] == '|')
maps[r][i] = '+' ;
}
}
x = -1, y = -1 ;
for (int i=c-1;i>=0;i--) { // 向左找木樁
if (maps[r][i] == '@') {
x = r, y = i ;
break ;
}
}
if (y != -1) {
for (int i=c-1;i>y;i--) { // 考慮橫直線
if (maps[r][i] == '.')
maps[r][i] = '-' ;
else if (maps[r][i] == '|')
maps[r][i] = '+' ;
}
}
}
else if (t == 1) {
maps[r][c] = '.' ;
int x = -1, y = -1 ;
if (r+1 < n && (maps[r+1][c] == '|' || maps[r+1][c] == '+')) {
for (int i=r+1;i<n;i++) { // 向下找木樁
if (maps[i][c] == '@') {
x = i, y = c ;
break ;
}
}
for (int i=r+1;i<x;i++) { // 考慮橫直線
if (maps[i][c] == '+')
maps[i][c] = '-' ;
else if (maps[i][c] == '|')
maps[i][c] = '.' ;
}
}
if (r-1 >= 0 && (maps[r-1][c] == '|' || maps[r-1][c] == '+')) {
for (int i=r-1;i>=0;i--) { // 向上找木樁
if (maps[i][c] == '@') {
x = i, y = c ;
break ;
}
}
for (int i=r-1;i>x;i--) { // 考慮橫直線
if (maps[i][c] == '+')
maps[i][c] = '-' ;
else if (maps[i][c] == '|')
maps[i][c] = '.' ;
}
}
x = -1, y = -1 ;
if (c+1 < m && (maps[r][c+1] == '-' || maps[r][c+1] == '+')) {
for (int i=c+1;i<m;i++) { // 向右找木樁
if (maps[r][i] == '@') {
x = r, y = i ;
break ;
}
}
for (int i=c+1;i<y;i++) { // 考慮橫直線
if (maps[r][i] == '+')
maps[r][i] = '-' ;
else if (maps[r][i] == '-')
maps[r][i] = '.' ;
}
}
if (c-1 >= 0 && (maps[r][c-1] == '-' || maps[r][c-1] == '+')) {
for (int i=c-1;i>=0;i--) { // 向左找木樁
if (maps[r][i] == '@') {
x = r, y = i ;
break ;
}
}
for (int i=c-1;i>y;i--) { // 考慮橫直線
if (maps[r][i] == '+')
maps[r][i] = '-' ;
else if (maps[r][i] == '-')
maps[r][i] = '.' ;
}
}
}
now = 0 ;
for (int i=0;i<n;i++) { // 計算當下數量
for (int j=0;j<m;j++) {
// cout << maps[i][j] << ' ' ;
if (maps[i][j] != '.')
now++ ;
}
// cout << '\n' ;
}
ans = max(ans, now) ;
}
cout << ans << '\n' << now ;
return 0 ;
}
```
### f313. 2. 人口遷移
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f313)
首先要釐清題目的意思，人口的遷移順序是如下所述
所有城市人口離開 $\rightarrow$ 所有人口進入城市
所以程式碼的順序應該是，先記錄那些城市"將要"有人口進入，那些城市減少多少人口
因為如果直接把遷移的人口加進去，會導致該城市等等判斷時遷移的人比較多
如上圖，已知 $k = 4$，如果在判斷城市 $A$ 的時候就把遷移人口加入城市 $B$
那城市 $B$ 最後就會剩下 $3$ 個人，所以不能在計算城市少多少人時，先增加周遭城市人口
最後可以用一個陣列暫時儲存要進入的人口數量，最後在加入城市即可
還要注意如果該位置是 $-1$，那它就不是城市，不會有人進入或離開
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int maps[50][50] ;
int nplus[50][50] ; // 城市將要加入多少人口
int mm[4][2] = {1,0,-1,0,0,1,0,-1} ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int r, c, k, m ;
cin >> r >> c >> k >> m ;
vector<int> r1(c,0) ;
for (int i=0;i<r;i++) {
for (int j=0;j<c;j++) {
cin >> maps[i][j] ;
nplus[i][j] = 0 ;
}
}
// 先記錄離開的人口跟將要進入的人口
for (int p=0;p<m;p++) { // m 天後的結果
for (int i=0;i<r;i++) {
for (int j=0;j<c;j++) {
if (maps[i][j] == -1) // 遇到非城市
continue ;
int sum = 0 ;
for (int it=0;it<4;it++) {
int x = i+mm[it][0], y = j+mm[it][1] ;
// 在範圍中且該位置是城市
if (x >= 0 && x < r && y >= 0 && y < c && maps[x][y] != -1) {
nplus[x][y] += maps[i][j] / k ; // 暫時儲存
sum += maps[i][j] / k ; //
}
}
maps[i][j] -= sum ;
}
}
// 人口進入城市
for (int i=0;i<r;i++) {
for (int j=0;j<c;j++) {
if (maps[i][j] == -1)
continue ;
maps[i][j] += nplus[i][j] ;
nplus[i][j] = 0 ; // 重置
}
}
}
int mmin = INT_MAX, mmax = 0 ; // 最小值跟最大值
for (int i=0;i<r;i++) {
for (int j=0;j<c;j++) {
if (maps[i][j] == -1) // 遇到非城市跳過
continue ;
mmin = min(mmin, maps[i][j]) ;
mmax = max(mmax, maps[i][j]) ;
}
}
cout << mmin << '\n' << mmax ;
return 0 ;
}
```
### f580. 2. 骰子
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f580)
這題最簡單的方式就是直接把六個面紀錄，用**腦袋+紙筆推理**兩個轉向的結果
但是其實有一個關於骰子的特性可以將**六個面變成三個面**，先看下圖，然後仔細觀察
會發現骰子互相對面的點數一定是 $7$，比如 $3$ 跟 $4$，$5$ 跟 $2$
所以就可以只紀錄**三個相鄰的面**，如下圖就只記錄了 $1$、$4$、$2$
這時候就需要推理轉向時的數字變動了，假設範例中 $1$ 是上 ，$4$ 是左，$2$ 是右，{ $1,4,5$ }
那在向右轉的時候會變成 { $5,4,1$ }，再轉一次會變成 { $6,4,5$ }
從這兩次旋轉可以知道，數字 { 上，左，右 } 會變成 { 7-右，左，上 }
而向前轉也可以用**同一個方法**推知，所以最後在修改數字時就可照上面的**規律解**
```cpp=
#include<bits/stdc++.h>
using namespace std ;
struct num {
int up = 1, ri = 2, le = 4 ;
};
int loc[21] ; // 骰子位置
num dice[21] ; // 骰子 (儲存上左右)
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, a, b, tmp ;
cin >> n >> m ;
for (int i=1;i<=n;i++)
loc[i] = i ;
for (int i=0;i<m;i++) {
cin >> a >> b ;
if (b > 0) { // 位置交換
tmp = loc[a] ;
loc[a] = loc[b] ;
loc[b] = tmp ;
}
else {
int idx = loc[a] ; // 可能有位置交換，所以要用陣列紀錄位置
if (b == -1) { // 向前轉
tmp = dice[idx].up ;
dice[idx].up = 7-dice[idx].le ;
dice[idx].le = tmp ;
}
else { // 向右轉
tmp = dice[idx].up ;
dice[idx].up = 7-dice[idx].ri ;
dice[idx].ri = tmp ;
}
}
}
for (int i=1;i<=n;i++) { // 輸出每個骰子的上方
int idx = loc[i] ;
cout << dice[idx].up << ' ' ;
}
return 0 ;
}
```
### h027. 202001_2 矩陣總和
[題目連結](https://zerojudge.tw/ShowProblem?problemid=h027)
直接用最直覺的方式就可以了，因為這題概念不難，可以直接做，要注意的大概有三點
1. 子矩陣的距離是指其跟 $A$ 矩陣**同樣位置中**有多少**不同**的數字
2. 當中多少子矩陣要看 $A$ 跟 $B$ 的大小關係
3. 全部的子矩陣可以藉由列舉左上角元素位置枚舉
當中的第一點其實很簡單，因為矩陣 $A$ 的左上角元素是 `A[0][0]`，子矩陣是 `B[i][j]`
而子矩陣遍歷時會是 `B[i+dx][j+dy]`，能夠表示子矩陣的所有元素位置
所以在判斷的時候只要寫 `if (A[i+dx-i][j+dy-j] != B[i+dx][j+dy])`
就能讓兩矩陣在同樣的位置，不過這裡的 $dx$ 只是一個變數，下方的程式碼用 $nx$ 代表 $i+dx$
第二點要考慮子矩陣跟矩陣的大小關係，比如一個一個矩陣高 $5$，子矩陣高 $1$
那很明顯至少有五個子矩陣，也就是 $0 \le i \le 4 = 5-1$，寬的部分也相同
所以兩個範圍分別是 $0\le i \le n-s$ 、 $0 \le j \le m-t$
第三點不選用子矩陣中心元素是因為子矩陣可能沒有中心點，而會比較複雜
所以採用左上角元素去枚舉，會比較貼近一般在使用二維矩陣的習慣
(比如遍歷二維陣列都是用 `A[0][0]` 作為開始)
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[11][101], B[11][101] ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int s, t, n, m, r, sum = 0, ans = INT_MAX, num = 0 ;
cin >> s >> t >> n >> m >> r ;
for (int i=0;i<s;i++) { // 輸入陣列 A 跟計算 A 總合
for (int j=0;j<t;j++) {
cin >> A[i][j] ;
sum += A[i][j] ;
}
}
// cout << "Asum: " << sum << "\n\n" ;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
cin >> B[i][j] ; // 輸入陣列 B
for (int i=0;i<=n-s;i++) { // i 是子矩陣的 x 範圍
for (int j=0;j<=m-t;j++) { // j 是子矩陣的 y 範圍
int tmp = 0, dis = 0 ; // 總和跟距離
// cout << "x: " << i << ", y: " << j ;
for (int nx=i;nx<i+s;nx++) { // 目前的子矩陣 x
for (int ny=j;ny<j+t;ny++) { // 目前的子矩陣 y
if (B[nx][ny] != A[nx-i][ny-j]) // 不同
dis++ ; // 距離+1
tmp += B[nx][ny] ; // 總和計算
}
}
// cout << ", tmp: " << tmp << ", dis: " << dis << '\n' ;
if (dis <= r) { // 距離不超過題目要求
num++ ;
ans = min(ans, abs(tmp - sum)) ;
}
}
}
cout << num << '\n' ;
if (!num) // 找不到要求的子矩陣
cout << -1 ;
else
cout << ans ;
return 0 ;
}
```
### f606. 2. 流量
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f606)
這題比較難，因為除了有題目本身的理解問題之外，還有很多小細節需要注意
在這邊先把題目大致上分成多點講解
1. 計算流量的方式要看**伺服器位置**跟**城市位置**
2. $n$ 個伺服器所以有 $n$ 行，計算方案時也要記得**考慮不同伺服器**
3. 伺服器的流量計算費用會受到多個因素(比如**位置**跟**流量大小**)影響
所以依據這三點大致上可以知道整個程式碼的架構是怎樣了，但是這裡還有兩個小細節
1. $u \not = v$ 超過 $1000$ 時是 $3000(1000\times3)+$ 超過 $1000$ 的部分 $\times 2$
2. 若 $u$ 有多個伺服器要傳送流量到城市 $v$，先將這些**傳輸流量相加**再計算花費
根據第二點，在計算時需要先加總，所以另外開一個陣列 $QS$ 儲存 $u$ 到 $v$ 的流量加總
這樣就不會因為缺少加總而多計算數字(比如加總後 $>1000$ 那某些部分只需 $\times \ 2$ )
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int Q[51][51], QS[51][51] ;
// QS[x][y] 所有從城市 x 到城市 y 的流量總和
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, k, sum, ans = INT_MAX ;
cin >> n >> m >> k ;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
cin >> Q[i][j] ;
for (int i=0;i<k;i++) {
sum = 0 ; // 初始化方案流量費用總和
for (int u=0;u<m;u++) // 初始化方案流量
for (int v=0;v<m;v++) // 是城市到城市所以都是 m
QS[u][v] = 0 ;
for (int j=0, tmp;j<n;j++) {
cin >> tmp ;
for (int c=0;c<m;c++)
QS[tmp][c] += Q[j][c] ; // 多伺服器都傳送流量到同城市
}
for (int u=0;u<m;u++) { // 是城市到城市所以都是 m
for (int v=0;v<m;v++) {
if (u == v) // u == v
sum += QS[u][v] ;
else { // u != v
if (QS[u][v] <= 1000) // 1000 內
sum += QS[u][v]*3 ;
else // 1000 以上
sum += (QS[u][v]-1000)*2+3000 ;
}
}
}
// cout << "sum: " << sum << '\n' ;
ans = min(ans, sum) ; // 找最小值
}
cout << ans ;
return 0 ;
}
```
### h082. 2. 贏家預測
[題目連結](https://zerojudge.tw/ShowProblem?problemid=h082)
這題是模擬題中偏難的題目，但是只要拆開題目就可以了
首先這個題目會給定三種數值，分別是**戰力**、**應變力**跟**順序**，其中順序會改變**第一輪**對戰的人選
再來就是對戰部分，依照人數區分成兩種情況
1. 人數是偶數，兩兩一組隊戰
2. 人數是奇數，剩下的一個直接晉級
而對戰後會有戰力跟應變力的增加，除了奇數當中**直接晉級**的人，直接晉級就**沒有數值增加**
這裡介紹一個小技巧，因為兩兩一個比較，所以誰輸誰贏都可以用交換變數的方式
```cpp=
if (py > px) // 如果 y 贏了(預設 x 是贏家)
swap(x, y) ;
cout << "win: " << x << ", lose: " << y << '\n' ;
```
而這裡因為贏的人跟輸的人改變數值不同，所以改變變數的方式很簡潔好用
也就是不需要把兩種情況(用if-else)寫出來，只需**改變變數**就可以了
還要注意除法是**無條件捨去**，就直接用兩個整數相除就好
最後一個環節就是把贏的人跟輸的人放入兩個組別，然後把**輸的人接在贏的人後面**
如果有人輸的次數夠了就直接淘汰，不用繼續比賽，而多出來的一個人**直接進下輪**
幫各位整理一下整個流程的順序
1. 輸入數值
2. 根據題目給定順序開始第一輪比賽
3. 每次比賽後修改數值、判斷淘汰人口和區分贏/輸組
4. 根據組別在修改下一輪的比賽順序(記得多出來的那個人)
5. 直到剩下一人就結束並輸出那一個人的編號
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
LL p[1005] ; // 戰力
LL t[1005] ; // 應變力
int order[1005] ; // 順序
int ltime[1005] = {0} ; // 輸幾次
int win[505], lose[505] ; // 輸贏組別
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, idx, k = 0 ;
cin >> n >> m ;
idx = n ;
for (int i=1;i<=n;i++) // 輸入
cin >> p[i] ;
for (int i=1;i<=n;i++)
cin >> t[i] ;
for (int i=0;i<n;i++)
cin >> order[i] ;
while (idx > 1) {
// cout << "Fidx: " << idx << '\n' ;
int w_idx = 0, l_idx = 0 ;
for (int i=0;i+1<idx;i+=2) {
int x = order[i], y = order[i+1] ;
if (p[x]*t[x] < p[y]*t[y]) // 如果 y 贏了，變數交換
swap(x, y) ;
int np = p[x] + p[y]*t[y] / (2*t[x]) ; // 贏的戰力
int nt = t[x] + p[y]*t[y] / (2*p[x]) ; // 贏的應變直
p[x] = np, t[x] = nt ;
p[y] += p[y] / 2, t[y] += t[y] / 2 ; // 輸的人
// cout << "win: " << x << ", lose: " << y << '\n' ;
win[w_idx++] = x ; // 贏的人分組
if (++ltime[y] < m) // 如果沒淘汰
lose[l_idx++] = y ; // 輸的人分組
}
if (idx % 2 == 1) // 多出的一個人
win[w_idx++] = order[idx-1] ;
// cout << "w: " << w_idx << ", l: " << l_idx << "\n\n" ;
int it = 0 ;
for (int i=0;i<w_idx;i++) // 贏的人排前面
order[it++] = win[i] ;
for (int i=0;i<l_idx;i++) // 輸的人排前面
order[it++] = lose[i] ;
idx = w_idx + l_idx ; // 重複檢查人數
// cout << "Sidx: " << idx << "\n\n" ;
}
cout << order[0] << '\n' ; // 剩下一個直接輸出
return 0 ;
}
```
### i400. 2. 字串解碼
[題目連結](https://zerojudge.tw/ShowProblem?problemid=i400)
看完題目後大概可以知道加密的流程
1. $1$ 的數量是偶數就跳過，奇數就平分字串然後前後交換
2. 根據規則一個個字元放置
3. 重複 $1,2$ 直到跑過所有 $01$ 字串
4. 結束加密過程
但是題目給定的是加密後的字串，求原本未加密的字串
所以**整個流程都要倒過來**，特別是根據 $01$ 字串放置字元的部分
再來說一下 $01$ 字串遇到 $0$ 跟遇到 $1$ 放置字元的規律
正常加密的過程是如果遇到 $0$ 就把**最前方**的字元放到新字串的**最後面**
如果遇到 $1$ 就把**最後**一個字元放到新字串的**最前面**，如果反過來看(解密)
要把 $01$ 字串**倒過來看**，如果遇到 $0$ 代表加密時是**最前方**(**左邊**)的字元，所以還原就是**放左邊**
同理如果遇到 $1$ 就**放右邊**，那這個部分就可以解決了
下一個部分就是如果 $01$ 字串當中切割交換的部分
這裡要注意的只有當字串長度是**奇數**的時候**正中間**的字元**不移動**
詳細的程式碼會如下所述
1. 輸入(需紀錄所有的 $01$ 字串，因為要從後往前解密)
2. 從後往前判斷 $01$ 字串，$0$ 放左 $1$ 放右
3. 如果 $01$ 字串中 $1$ 的數量是奇數就將字串前後交換位置(正中間不換)
4. 重複 $2,3$ 步直到跑過所有 $01$ 字串
5. 輸出結果
```cpp=
#include<bits/stdc++.h>
using namespace std ;
string S[105] ; // 放所有的 01 字串
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int m, n ;
string after, befo ;
cin >> m >> n ; // 輸入
for (int i=0;i<m;i++)
cin >> S[i] ;
cin >> after ;
for (int i=m-1;i>=0;i--) { // 跑過所有 01 字串
int one = 0 ;
befo = "" ;
for (int j=n-1;j>=0;j--) {
one += S[i][j] - '0' ;
if (S[i][j] == '1') // 還原放右邊
befo = befo + after[j] ;
else // 還原放左邊
befo = after[j] + befo ;
// cout << befo << '\n' ;
}
if (one % 2 == 1) { // 1 的數量是奇數
after = befo ;
befo = "" ;
if (n % 2 == 1) { // 字串長度是奇數
for (int k=n/2+1;k<n;k++)
befo += after[k] ;
befo += after[n/2] ; // 正中間
for (int k=0;k<n/2;k++)
befo += after[k] ;
}
else
for (int k=n/2;k<(n/2+n);k++) // 從中間開始交換
befo += after[k%n] ;
// cout << befo << '\n' ;
}
after = befo ;
}
cout << befo << '\n' ;
return 0 ;
}
```
### j123. 2. 運貨站
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j123)
這題大概就幾個重點，主要是實作難度比較高，概念應該沒有太大的問題
1. 有五種**不同形狀**貨物要"由右到左"的進入倉庫
2. 推到直到不能前進為止，且不能轉貨物的方向
3. 如果有一個貨物不能完整的放入倉庫當中，會被丟棄
4. 問倉庫剩餘多少空間和丟棄多少貨物
這題最難的地方在於第一點+第二點，因為有五個**不同形狀**的貨物要進入倉庫
但是其實五個貨物的程式碼都可以整理成三個步驟
1. 判斷貨物要放在哪裡
2. 如果貨物可以被放進去就修改倉庫空間
3. 如果不行就丟棄貨物
所以其實五個貨物只需要修改部分細節，但大體上是相同的
在這邊也介紹一個模擬常用的技巧，也就是**功能切割**，對於不同貨物包在**不同 function** 當中
這樣做有多個優點，比如可以**針對性**的 debug，**方便觀察**輸出結果等等
最重要的是可以**不用把邏輯寫在一起**，把很複雜的東西切分出來處理就會變簡單
至於倉庫的位置有沒有貨物，可以用 bool 值表示，如果用數字 $0,1$ 也可以
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int thro = 0 ;
bool V[31][51] = {false} ;
void doA(int cnt, int mx) {
int x = mx-1, y = cnt ;
for (;x>=-1;x--) { // 由右往左
if (x == -1 || V[y][x] || V[y+1][x] || V[y+2][x] || V[y+3][x]) {
x++ ; // 這格不行但是上一格可以
break ;
}
}
if (x != mx)
for (int i=0;i<4;i++) // 填入貨物
V[y+i][x] = true ;
else
thro++ ;
}
void doB(int cnt, int mx) {
int x = mx-3, y = cnt ;
for (;x>=-1;x--) {
if (x == -1 || V[y][x] || V[y][x+1] || V[y][x+2]) {
x++ ;
break ;
}
}
if (x != mx-2)
for (int i=0;i<3;i++)
V[y][x+i] = true ;
else
thro++ ;
}
void doC(int cnt, int mx) {
int x = mx-2, y = cnt ;
for (;x>=-1;x--) {
if (x == -1 || V[y][x] || V[y][x+1] || V[y+1][x] || V[y+1][x+1]) {
x++ ;
break ;
}
}
if (x != mx-1)
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
V[y+i][x+j] = true ;
else
thro++ ;
}
void doD(int cnt, int mx) {
int x = mx-3, y = cnt ;
for (;x>=-1;x--) {
if (x == -1 || V[y][x+2] || V[y+1][x] || V[y+1][x+1] || V[y+1][x+2]) {
x++ ;
break ;
}
}
if (x != mx-2) {
V[y][x+2] = true ;
for (int i=0;i<3;i++)
V[y+1][x+i] = true ;
}
else
thro++ ;
}
void doE(int cnt, int mx) {
int x = mx-2, y = cnt ;
for (;x>=-1;x--) {
if (x == -1 || V[y][x+1] || V[y+1][x] || V[y+1][x+1] || V[y+2][x] || V[y+2][x+1]) {
x++ ;
break ;
}
}
if (x != mx-1) {
V[y][x+1] = true ;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
V[y+1+i][x+j] = true ;
}
else
thro++ ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int r, c, n, cnt, ans = 0 ;
char type ;
cin >> r >> c >> n ;
for (int i=0;i<n;i++) {
cin >> type >> cnt ;
if (type == 'A')
doA(cnt, c) ;
else if (type == 'B')
doB(cnt, c) ;
else if (type == 'C')
doC(cnt, c) ;
else if (type == 'D')
doD(cnt, c) ;
else
doE(cnt, c) ;
// for (int j=0;j<r;j++) { // 輸出做觀察
// for (int k=0;k<c;k++) {
// cout << V[j][k] << ' ' ;
// }
// cout << '\n' ;
// }
}
for (int j=0;j<r;j++) // 也可以在放貨物的時候計算
for (int k=0;k<c;k++)
if (!V[j][k])
ans++ ;
cout << ans << ' ' << thro ;
}
```
### j606. 2. 造字程式
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j606)
先把這題的流程跟要求整理一下
1. 根據 $Q$ 個序列 $P$ 修改字串
2. 過程中的所有字串當中的第 $i$ 個字元要整合成另一個字串
3. 根據第二點，會有 $Q$ 個字串是新整合出來的
再來就是這題算是比較簡單的，因為不是解密，是**加密**過程
所以**不需要反推**原字串，直接依照題目敘述走就可以了
不過這題還**加入一個考點**，就是最後是需要輸出 $R$ 個字串
輸出操作 $1\sim Q$的新字串的第 $1$ 個字元
輸出操作 $1\sim Q$的新字串的第 $2$ 個字元
後面**以此類推**就可以得到 $R$ 個新字串，最後面直接**按照順序**輸出
其實這個也不難，只要先開一個字串矩陣，在轉變的過程中加入對應字元
最後用 for 迴圈去輸出字串矩陣當中的字串就可以了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
string S[21] = {""} ; // 答案字串
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int k, q, r ;
string s1, s2 ; // 目前字串、新字串
cin >> k >> q >> r ;
cin >> s1 ;
s2 = s1 ;
for (int i=0;i<q;i++) {
for (int j=0, tmp;j<k;j++) {
cin >> tmp ;
s2[tmp-1] = s1[j] ; // 填充新字串
}
s1 = s2 ; // 更新字串
for (int j=0;j<k;j++) {
S[j] += s2[j] ; // 更新答案字串
}
}
for (int i=0;i<r;i++)
cout << S[i] << '\n' ; // 輸出多個答案字串
return 0 ;
}
```
### k732. 2. 特殊位置
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k732)
這題可能會有人不太清楚題目描述的範圍，但是只要先**決定一個點**
再接著把附近的曼哈頓距離都**算出來**，就可以很清楚了，如下圖
曼哈頓距離是**往外延伸**的，下面左就是距離 $1$ 之內的曼哈頓距離
(2024/03/07勘誤:中間那張圖的正中央應該是 $0$ )
其他兩圖也很容易推出來，不過如果單就是這樣的範圍很麻煩
因為 for 迴圈會很難寫，所以這裡用**正方形**去寫迴圈
只要再多一層 if **判斷曼哈頓距離是否在規定範圍中**即可
這種題目最難的是**想到怎麼實作**，因為**比較難超時**，所以就直接用**最好寫**的方法即可
至於字典序，二維座標 $(x,y)$ 的字典序就是先比較 $x$ 再比較 $y$
```cpp=
#include<bits/stdc++.h>
using namespace std ;
#define P pair<int,int>
#define FF first
#define SS second
int n, m ;
int maps[52][52] ;
int run(int x, int y, int k) {
int sum = 0 ;
for (int nx=x-k;nx<=x+k;nx++) // 正方形上下
for (int ny=y-k;ny<=y+k;ny++) // 上方形左右
if (nx>=0 && ny>=0 && nx<n && ny<m) // 在地圖範圍內
if (abs(nx-x)+abs(ny-y) <= k)
sum += maps[nx][ny] ;
return sum ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int num = 0 ;
cin >> n >> m ;
vector<P> anses ;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
cin >> maps[i][j] ; // 輸入
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
int sum = run(i,j,maps[i][j]) ; // 計算範圍內總和
if (sum % 10 == maps[i][j]) { // 符合特殊位置條件
num++ ; // 答案數量+1
anses.push_back({i,j}) ; // 放入座標
}
}
}
cout << num << '\n' ;
for (P it:anses)
cout << it.FF << ' ' << it.SS << '\n' ;
return 0 ;
}
```
### m371. 2. 卡牌遊戲
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m371)
整理幾個重點
1. 消除具有**相同數值**且**之間沒有障礙物**的兩個元素
2. 每一種數字在表格中出現**恰好兩次**
3. 消除兩個相同的數字 $x$，會獲得 $x$ 分
4. 垂直或水平地將兩個相同數值的元素消除 => 上下左右消除
這題簡單來說就是**重複消除元素**直到**不能在消除任何數字**為止
如果要執行上述方式，可以使用下列程式碼
```cpp=
bool B = true ; // 判斷此回合是否有消除元素
while (B) {
B = false ; // 新的回合尚未消除
if (有消除) // 有消除元素(圖出現變化)
B = true ;
}
```
因為只要有消除元素，就有**可能有**新的元素可以被消除，比如下方的橘色區塊
如果橘色區塊被消除，那綠色區塊就可以在**下一回合**被消除，但如果沒有元素被消除
那下一回合的圖跟這個回合一樣，也就是說**不可能會有元素再被消除**了
比如圖中只剩下藍色區塊，那 $0$ 跟 $1$ 就是**相互**成為對方的**障礙物**
所以現在重複找消除元素的方式已經完成了，剩下就是關於**上下左右消除**跟**消除後的元素表示**
因為消除後的元素**不是障礙物**，所以可以用一個獨立於**題目設定數字範圍**的數字
比如這題是 $0\sim 1000$，那就可以設 $-1$，今天在找上下左右的數字時，遇到 $-1$ 就跳過
剩下上下左右尋找，這裡介紹一個在二維陣列很好用的技巧
如果要上下左右，可以提前寫好 $x$ 的變量跟 $y$ 的變量，這裡用 mm 表示
`int mm[4][2] = {-1,0,1,0, 0,-1,0,1} ; // 上下左右`
這樣在解題時只要多用一個 for 迴圈就可以跑出上下左右的效果，在 BFS 也很好用
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int maps[21][41] ; // 範圍
int mm[4][2] = {-1,0,1,0, 0,-1,0,1} ; // 上下左右
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, sum = 0 ;
cin >> n >> m ;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
cin >> maps[i][j] ;
bool have = true ; // 本回合是否有消除元素
while (have) {
have = false ;
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
int now = maps[i][j] ; // 此格的數字
if (now == -1)
continue ;
for (int k=0;k<4;k++) {
int x = i+mm[k][0], y = j+mm[k][1] ;
while (x>=0 && x<n && y>=0 && y<m && maps[x][y] == -1)
x += mm[k][0], y += mm[k][1] ; // 從上下左右找
if (x>=0 && x<n && y>=0 && y<m && maps[x][y] == now) {
// cout << x << ' ' << y << '\n' ;
sum += now ; // 更新分數
maps[x][y] = -1 ; // 清除
maps[i][j] = -1 ; // 清除
have = true ; // 有消掉
break ; // 結束上下左右尋找
}
}
}
}
}
cout << sum ;
}
```
### m932. 2. 蜜蜂觀察
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m932)
這題最難的是怎麼用資料結構去儲存蜂窩，但其實整個結構只有**移動步驟**
所以可以簡化成二維陣列的方式，將蜂窩**向左推**，會變成右下方這樣
那現在就可以把 $6$ 個移動步驟給簡化，0 右上(上)，1 右，2 右下，3 左下(下)，4 左，5 左上
一樣用 mm 去表示 $6$ 個方向的移動，會比較簡單，最直觀的感受就是少寫很多 if
接下來整理剩下的幾個解題重點，其他的問題都不太難
1. 輸出**經過的路徑**每格的代表字母，碰到牆壁該行動會停在原地
2. 經過字元的種類數（大小寫相異）
首先第一點很簡單，只要判斷行動完有沒有超過範圍就可以了
第二點就比較麻煩了，這邊提出兩個很直觀的方式
一是用**兩個陣列**儲存哪個字母(大小寫)有被走過
二是用 set 去儲存走過的路，因為會自動刪除重複元素
第一個方法是最簡單的，只要用字母的 ASCII 去儲存位置即可
可以先輸出 $A$ 跟 $a$ 的 ASCII 之後用 if 做大小寫分類即可
第二個方法只要有學過 set 就直接拿來用就好
(以下程式碼混和了兩種方法，請自行斟酌)
```cpp=
#include<bits/stdc++.h>
using namespace std ;
char maps[21][21] ;
int mm[6][2] = {-1,0, 0,1, 1,1, 1,0, 0,-1, -1,-1} ;
//0 右上(上), 1 右, 2 右下, 3 左下(下), 4 左, 5 左上
bool gone[2][26] = {false} ;
// 有沒有遇到小(大)寫字母
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int m, n, k, to, num = 0 ;
cin >> m >> n >> k ;
set<char> s ; // 用 set 會比較方便(去除重複)
int x = m-1, y = 0 ;
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
cin >> maps[i][j] ;
for (int i=0;i<k;i++) {
cin >> to ;
// 新的座標 nx, ny
int nx = x + mm[to][0], ny = y + mm[to][1] ;
if (nx >= 0 && nx < m && ny >= 0 && ny < n)
x = nx, y = ny ; // 在範圍內
char now = maps[x][y] ;
s.insert(now) ;
if ((int)now >= 97) // a 97 A 65(ASCII)
gone[0][now-'a'] = true ; // 小寫
else
gone[1][now-'A'] = true ; // 大寫
cout << now ;
}
cout << '\n' << s.size() ;
for (int i=0;i<2;i++)
for (int j=0;j<26;j++)
if (gone[i][j]) num++ ; // 看經過幾種字母
cout << '\n' << num ;
return 0 ;
}
```
Sign in with Wallet
Connect another wallet