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

A. Simple Base Conversion

• 看清楚題目和測資的大小寫和範圍！
• 對於 <cstdio>，%i 可以自動判斷輸入的整數是 16 進位或 10 進位並存入 int 型別中，再自行判斷後用 %d 輸出 10 進位和 %X 輸出 16 進位（大寫字母）即可。
• <ios> 中有 std::showbase、std::hex、std::dec、std::uppercase 等物件可以使用，如：
  ​cout << hex << uppercase;
  ​cout << "0x" << 44 << endl;
  

  會輸出：
  ​0x2C
  

• 如果使用 cin, cout 的同學，請在 main 函數一開始加上以下程式碼，避免超時。
  ​ios_base::sync_with_stdio(false);
  ​cin.tie(NULL);
  

• 題目敘述中提到是非負整數，小心輸入為 0 或 0x0 的狀況。

B. Kindergarten Counting Game

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

C. The Playboy Chimp

• 二分搜

D. Rotating Sentences

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

E. Solve It

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

F. Marvelous Mazes

• 字串處理

G. Where's Waldorf?

• 字串處理
• 同 A，使用 cin、cout 時請注意速度。

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}$。
• 如果寫不出大數乘法，開其他程式語言也是不錯的選擇。