# 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 ```