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 | \leq ε$ 但因為
  $ε$ 太小所以我們忽略，仍然可以視為
  $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 \leq 250$ 。
兩個最大到
$10^{250}$ 的數字相乘，最大會到
$10^{500}$ 。
如果寫不出大數乘法，開其他程式語言也是不錯的選擇。