前往
大廳
主題

【CPE】2024/04/23 CPE心得

懶洋洋的豪豬 | 2024-04-23 22:45:14 | 巴幣 0 | 人氣 153

結果:7題
之前最高4題好沒真實感
原本是在前幾個禮拜考但系統出包所以改到今天考。
這次考的有比較簡單,名次跟之前差不多但整體題數有增加,尤其7題人數多好多。


題目簡述(?)
A.給定房子位置問最短距離和
之前有遇到過這題,用二分搜寫出來了但感覺暴力也能行?

B.蝸牛爬牆
之前好像也遇過這題,但邊界條件卡導致比前一題久,尤其一個測資的情況是:
我輸出6 標準答案是7
我*檢查高度變化多加了一個cout->輸出7 標準答案是7
我整個不知所云,加了判斷這個測試資料的條件後交出去就過了

C.修改字串
根據題目要求寫判斷式輸出更正後的結果。

D.判斷函數結果奇偶
給一個函數模式(計算結果的),問結果%2。
用DP解出來了(底層條件想了一下,因為題目沒給)

E.密碼遊戲(其實就是)幾A幾B的題目
問詢問密碼與正確密碼的差異,相同數字位置(強提示)、數字對不同位置(弱提示),把每次詢問的結果輸出。
由於每次詢問是獨立的所以很快寫出來了(比第四題快吧好像),感覺難度有點不適合,也可能第四題後順序是亂的。

F.核元素堆疊排列組合(應該)
U代表鈾、L代表隔層,三個U連續排列是危險的排列,詢問長度為n的盒子有多少種危險排列。
這題我用DP算出來不危險的排列後以2^n(全部可能的排列組合)去減,剩下的自然是危險的排列組合數量了。

G.費氏數列求餘
給定n,m,求Fn(費氏數列第n項)%2^m的結果。0<=n<=10^9(大約),0<=m<=20
這題敘述超短,剛看到時就知道如何讓計算過程不要讓複雜度變成線性O(n)是解出這題的關鍵,後來想到可以用矩陣
|0 1|
|1 1|
去把[a,b]轉為[b,a+b](也就是費氏數列的操作步驟)
上述矩陣乘n次後的matrix[0][1]就是答案了(對應到[b,a+b]的第一項)
加速的方法好像叫矩陣快速冪?
有聽人講過但沒實際寫過(只寫過快速冪)
後來剩20多分鐘時完成

總結
當下通過六題、七題時很開心(第七題寫完更開心因為這對我來講算是有挑戰性的,加上以前沒看過這種題目),但後面情緒就慢慢平衡了,因為心裡知道只是這次難度下降,自身並沒有進步太多,之後有機會還會繼續挑戰的(主要是因為考試時間太長不想每次都考,想準備更完善後再報)。


創作回應

更多創作