A、 15 and 20

• 猜拳游戲的模擬
• 把四個(gè)數(shù)加起來(lái)，判斷一下即可

B、 顯示器

• 求給定比例的最大分辨率
• 直接求橫縱的最小倍數(shù)，取最小的；
• 也可以枚舉倍數(shù)

C、 Sequence

• ，已知 , 求 。
• 手工枚舉一下，可以發(fā)現(xiàn)循環(huán)節(jié)長(zhǎng)為 。
• 

D、 Carrot

• 個(gè)奇數(shù)， 分成兩個(gè)集合，使得集合累加和的差值最小
• 結(jié)論： , 差值為 ； 其他， 差值為 。
• 證明：
  • 連續(xù)四個(gè)奇數(shù)為 分成兩組 , 差值為 。所以，當(dāng) ， 結(jié)果為 。
  • 當(dāng) 時(shí)， 我們把 以外的所有數(shù)按連續(xù) 個(gè)進(jìn)行分組，差值為 ，然后把 隨便給某個(gè)集合，差值為 。由于 是奇數(shù)，所有奇數(shù)個(gè)奇數(shù)的和為奇數(shù)，所以分成兩組，差值最小為 。所以，之前的構(gòu)造為一個(gè)最小差值分組。
  • 當(dāng) 時(shí)，結(jié)果顯然為 。其他 時(shí)，最小的 個(gè)數(shù)分為 和 , 差值為 。顯然最后結(jié)果為 。
  • 當(dāng) 時(shí)，采用類似于第 步的構(gòu)造和利用奇偶性，得到最小值為 。

E、 Cuboid

• 長(zhǎng)方體沿表面走對(duì)角的最短路徑長(zhǎng)度
• 結(jié)論 當(dāng)
• 平面上，兩點(diǎn)間直線最短
• 將長(zhǎng)方體展開(kāi)，很容易得到以上結(jié)論。
  
  

F、 Order

• 個(gè)訂單，求完成時(shí)間的最小累加和
• 最優(yōu)安排是按訂單數(shù)從小到大安排生成
• 反證
  • 假設(shè)一個(gè)最優(yōu)安排中，存在 , 但是 。我們交換 和 的位置，得到一個(gè)新的安排。
  • 顯然對(duì)于 或者 的訂單，這種交換沒(méi)有影響。
  • 對(duì)于 的訂單，顯然，其完成時(shí)間是小于或等于原有安排的。
  • 矛盾

G、 Ball

• 一個(gè)球，從左上角彈出，彈幾庫(kù)到右下角？
• 結(jié)論： 和 都為奇數(shù)時(shí)能彈到右下角，需要彈 庫(kù)
  
  

H、 奇怪的回文子串

• 構(gòu)造一個(gè)長(zhǎng)度為 的字符串，要求其中最長(zhǎng)回文子串的長(zhǎng)度處于 之間，且出現(xiàn)各種字符的次數(shù)不超過(guò)給定的限制。
• 做法很多
  • 先構(gòu)造一個(gè)類似于 的回文串，長(zhǎng)度為 。然后取其他字符填充成 的形式，然后再用這個(gè)子串按順序填充成 長(zhǎng)的字符串 （雷智凱）
  • 先利用無(wú)限制字符，構(gòu)造一個(gè)類似于 的串，然后隨機(jī)產(chǎn)生后面的字符，要求隨機(jī)出來(lái)的字符不超過(guò)限制，且不等于前 和前 個(gè)字符。 （謝勇）

I、 Line

• 過(guò)矩形外一點(diǎn)畫(huà)一條直線，分割矩形使得兩邊面積相等。
• 結(jié)論： 取矩形的中點(diǎn) 和 給定點(diǎn) 畫(huà)一條直線 即為所求。
• 顯然，由于對(duì)稱性，所有過(guò)中點(diǎn)的直線必然平分矩形。
• 注意：中點(diǎn)坐標(biāo)需要除 ，可能為小數(shù)，為此先把坐標(biāo)都乘 來(lái)處理。

J、 勾股定理

• 給一個(gè)整數(shù) ，求另外兩個(gè)整數(shù) 和 ，使其構(gòu)成直角三角形
• 構(gòu)造的方法也很多
  • 
  • 不妨設(shè) ,所以 必須為奇數(shù),解得
  • 不妨設(shè) ,所以 必須為偶數(shù),解得

K、 BAD String

• 交換一個(gè)串的兩個(gè)字符以后，使得串不含 這個(gè)子串
• 構(gòu)造方法也很多
  • 統(tǒng)計(jì) 的數(shù)量 ，顯然每次交換最多破壞兩個(gè) 子串，所以當(dāng) 時(shí)無(wú)解
  • 如果 , 交換成
  • 如果 , 交換成
  • 否則，隨機(jī)交換兩個(gè)字符，驗(yàn)證一下。