Try   HackMD

PCCA Winter 一般組 Day 1 練習賽 參考解答

A. Simple Base Conversion

  • 看清楚題目和測資的大小寫和範圍!
  • 對於 <cstdio>%i 可以自動判斷輸入的整數是 16 進位或 10 進位並存入 int 型別中,再自行判斷後用 %d 輸出 10 進位和 %X 輸出 16 進位(大寫字母)即可。
  • <ios> 中有 std::showbasestd::hexstd::decstd::uppercase 等物件可以使用,如:
    ​cout << hex << uppercase;
    ​cout << "0x" << 44 << endl;
    
    會輸出:
    ​0x2C
    
  • 如果使用 cin, cout 的同學,請在 main 函數一開始加上以下程式碼,避免超時。
    ​ios_base::sync_with_stdio(false);
    ​cin.tie(NULL);
    
  • 題目敘述中提到是非負整數,小心輸入為 00x0 的狀況。

B. Kindergarten Counting Game

  • 輸入一整行之後再處理。
  • 注意開頭和結尾的一些特殊狀況!

C. The Playboy Chimp

  • 二分搜

D. Rotating Sentences

  • 請小心處理換行字元,不要輸出多餘的空白!

E. Solve It

  • 發現單調性。
  • 答案只要求到小數點後第四位。
    • 比較兩個數字是否相等時,可以接受非常小的誤差。
    • 即: \(|a-b| \le \varepsilon\) 但因為 \(\varepsilon\) 太小所以我們忽略,仍然可以視為 \(a=b\) 成立。

F. Marvelous Mazes

  • 字串處理

G. Where's Waldorf?

  • 字串處理
  • 同 A,使用 cincout 時請注意速度。

H. Humidex

  • 二分搜
  • 單調性
  • 同 E,請注意浮點數運算的誤差。

I. Broken Keyboard (a.k.a. Beiju Text)

  • 開一個陣列 \(O(n)\) 檢查,每次移動指針時(Home, End, Next)把下一個字元映射到指針位置的陣列格中。
  • 另解:linked-list

J. Monthly Expense

  • \(N+1\) 個數的數列分成連續的 \(M\) 個區間,使最大區間和最小。
  • 二分搜答案,並且爬行法 \(O(n)\) 是否有合法的分法。

K. The Monkey and the Oiled Bamboo

  • 二分搜答案,按照題意 \(O(n)\) 檢查是否合法。

L. Product

  • 數字範圍到 \({10}^{250}\),也就是兩個 \(250\) 位數相乘,直式乘法:\(O(n^2)\)\(n \le 250\)
  • 兩個最大到 \({10}^{250}\) 的數字相乘,最大會到 \({10}^{500}\)
  • 如果寫不出大數乘法,開其他程式語言也是不錯的選擇。