---
# System prepended metadata

title: 111學年度初階班上學期期末考題解
tags: [初階班]

---

# 111學年度初階班上學期期末考題解

這次考試我出的有一點上頭
所以有一點點難
但這裡面的題目其實花時間仔細想想
其實解法都不複雜

## a884 sum
[題目](http://203.64.191.163/ShowProblem?problemid=a884)
這題非常簡單，
就是輸入陣列加簡單的if判斷
```
if(後項-前項 > 0){
    ans += 後項-前項
}
```

但是這題有一個小陷阱導致有一些人只有$50%$
我題目寫所有側資保證$1 \leq a_i \leq 2147483647$
$2147483647$的確是$int$的範圍
但這題會有加法
所以經過加法後會超過$int$的範圍
所以要記得用$long long int$

---
## a881 Only Wah Purposely
[題目](http://203.64.191.163/ShowProblem?problemid=a881)
簡單數學
根據題目可以知道每次直播最少會 wah 2次，最多6次
那麼如果能夠整除6的話，直播次數就會是 n/6 ~ n/2
但如果不能整除6，多出來的那一次必須開新的直播
就算只有多一次也能讓上一個直播 wah 5次來達到最少直播數
而若是無法整除2，則不用加，因為直播無法只 wah 1次
整合一下就會變成
%6 == 0 : n/6 ~ n/2
else : n/6+1 ~ n/2

---
## a878 好想海底撈____________________________月
[題目](http://203.64.191.163/ShowProblem?problemid=a878)
這題其實還蠻簡單的，只要先getline進去之後用str.find找空格，找到最後
一個之後輸出之後的就好。但這樣很累，所以有一個酷東東叫str.rfind
用法跟find一樣，只是它會從後面找回來，所以直接就是最後一個空格。

---
## a853 秋葉原朝聖之旅
[題目](http://203.64.191.163/ShowProblem?problemid=a853)
先把第一個數字存起來
接著把剩下的數字用 while + vector.push_back 儲存起來
用內建 sort (或其他排序) 完之後便會由小大排列
之後再用原本的存款數字由 vector 頭開始往後減
中間要記錄減了多少次
如果減到一半變成負數則 break 迴圈
直接輸出記錄結果
但如果跳出迴圈後結果與 vector.size() 相符
表示有全部買齊，則輸出 "Hololive Daisuki !!!"

---
## a873 even&odd
[題目](http://203.64.191.163/ShowProblem?problemid=a873)
這題沒多少人寫出來，但這題其實很簡單，他只是藏在有點後面
題目要求是分別排序奇數和偶數
其實只要開三個陣列就可以解決這個問題
一個存原本的數列
一個存奇數
一個存偶數
>奇數和偶數的陣列建議用vector
因為只要直接push_back就好
不用特別看陣列要開多大(用array開太大排序時會影響)

把存偶數和奇數的陣列分別排序
接下來輸出時
只要判原數列是偶數就輸出偶數陣列的
只要判原數列是奇數就輸出奇數陣列的

---
## a877 迴文針
[題目](http://203.64.191.163/ShowProblem?problemid=a877)
除了最後一個測資其實都還好，有兩種做法
第一個是直接將字串反轉之後比較原本的跟反轉的是否相同
第二個是從字串頭跟尾分別比較是否相同，比到中間停
最後一個測資比較麻煩是因為有空格跟標點
可以先getline之後把標點一個一個判斷掉
但這樣程式會很長
所以有一個東西是isalnum()
這個可以直接判斷括弧內的值是否為數字或字母，是的話輸出1，反之為0
這樣就可以直接刪掉非字母數字的東西然後再判斷。

---
## a870 正方形
[題目](http://203.64.191.163/ShowProblem?problemid=a870)
這題是一個小小的數學
那就是最大公因數和最小公倍數

### 幾何意義
兩數當長方形的邊長，這時最大公因數就是可以填滿長方形的最大正方形邊長
兩數當長方形的邊長，這時最大公倍數就是長方形可以組成的最小正方形

### 數學
最大公因數稱為GCD
最小公倍數稱為LCM
$LCM(a,b) = (a \times b)/GCD(a,b)$
這裡我就不證明了，想知道的自己去查

### 輾轉相除法(歐幾里得演算法)
我們可以用輾轉相除法求出GCD
假設現在有一個長方形邊長為38和16
我們要找出可以填滿長方形的最大正方形邊長
我們可以用小邊構造出長16的正方形
再用這個正方形填入長方形
剩下的區域變成了一個新的長方形
新的長方形再繼續剛剛的流程直到只剩正方形
最後的正方形就是答案了

上面的想法可以簡化成數學式
$gcd(a,b)=gcd(b,a\%b),(a>b)$
### 輾轉相除法虛擬碼
迴圈
```=
gcd(a,b):
    while 0 < b:
        r <- a % b
        a <- b
        b <- r
    return a
```
遞迴(可以想想為什麼這次是回傳b，不像剛剛是a)
```=
gcd(a,b):
    r <- a % b
    if r == 0:
        return b
    gcd(b,r)
```
---
## a897 ()
[題目](http://203.64.191.163/ShowProblem?problemid=a879)
學過stack的應該覺得這題很簡單
這題其實就只要想像一下
假設題目是(()())
我從最左邊的開始一個一個推入陣列
只要出現()就消掉
(
((
(()可以消$\implies$(
((
(()可以消$\implies$(
()可以消$\implies$沒了
如果像現在這樣全部消完就代表這個括號是合理的
如過無法全部消掉就是不合理的
例如
())(()
()消掉
)
)(
)((
)(()消掉
)(
最後剩這樣就是不合理的括號


---
## a875 最佳區間
[題目](http://203.64.191.163/ShowProblem?problemid=a875)
這題和a074非常像，可以去寫a074看看

這題如果單50%測資的話非常簡單
for迴圈直接炸開
但如果要100%的話就要用到一點點greedy的概念(沒聽過可以不用理他)
我們想像在數列中有兩個指針
這兩個指針的中間就是現在要取的範圍
我們直接舉例
6 8
3 0 4 -2 2 1
我們要找到一個最短的時間賺到8元以上
```cpp=
↓
 3 0 4 -2 2 1 現在0元，0小時
↑
不夠所以上指針向右
  ↓
 3 0 4 -2 2 1 現在3元，1小時
↑
不夠所以上指針向右
    ↓
 3 0 4 -2 2 1 現在3元，2小時
↑
不夠所以上指針向右
      ↓
 3 0 4 -2 2 1 現在7元，3小時
↑
不夠所以上指針向右
         ↓
 3 0 4 -2 2 1 現在9元，5小時
↑
錢夠了，ans = min(ans,5) 如果5比現在的最短打工時間短就更新，長就保留原本的
現在錢超過了不用再排更長的班，所以下指針向右
         ↓
 3 0 4 -2 2 1 現在6元，4小時
  ↑
不夠所以上指針向右
           ↓
 3 0 4 -2 2 1 現在8元，5小時
  ↑
ans = min(ans,5)
錢超過所以下指針向右
           ↓
 3 0 4 -2 2 1 現在8元，4小時
    ↑
ans = min(ans,5)
錢超過所以下指針向右
             ↓
 3 0 4 -2 2 1 現在5元，4小時
      ↑
上指針到底所以下指針向右

接下來我就不模擬了，就都是一樣的東西
最後答案是4
```
  
---
## a880 DFS?
[題目](http://203.64.191.163/ShowProblem?problemid=a880)
這題我題目命名是DFS?，學過DFS應該會很直覺想到這題是用DFS解
這題也的確可以用DFS解
但這裡是初階班，肯定是有其他更簡單的方法
輸出的東西都是由0和1組成
這些0和1就和二進位一樣
每個0和1的組合換成10進位
例如
是3個格子的話
$000 \implies 0$
$001 \implies 1$
$010 \implies 2$
$100 \implies 4$
$101 \implies 5$
$110 \implies 6$
$111 \implies 7$
我們可以發現這其實就是
輸出$0到2^3-1$的十進位換成二進位
如果是4個格子
就是輸出$0到2^4-1$的十進位換成二進位

那要怎麼把十進位換成二進位呢
我們可以用$\%\ 2$來看十進位轉二進位的最後一位是0還是1
如果$\%\ 2 == 1$就代表二進位的最右邊是1
如果$\%\ 2 == 0$就代表二進位的最右邊是0
判斷完一個後可以用/2或是>>1的方式去掉最右邊的數字
ex
01101 / 2 = 0110
10010 >> 1 = 1001

虛擬碼
```
decimal_to_binary(m,n):
    r
    for i <- 0 to n:
        if m % 2 == 1:
            r += '1'
        else:
            r += '0'
        m >>= 1
    return r
```








