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

  • 發現單調性。
  • 答案只要求到小數點後第四位。
    • 比較兩個數字是否相等時,可以接受非常小的誤差。
    • 即:
      |ab|ε
      但因為
      ε
      太小所以我們忽略,仍然可以視為
      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

  • 數字範圍到
    10250
    ,也就是兩個
    250
    位數相乘,直式乘法:
    O(n2)
    n250
  • 兩個最大到
    10250
    的數字相乘,最大會到
    10500
  • 如果寫不出大數乘法,開其他程式語言也是不錯的選擇。