The Rock Game

題目大意：

有N (1 <= N <= 15)位二進制數，一開始是N個0, 你每次對當前狀態進行一次操作，把當前狀態的某個位置取反（即原來是0的變成1，原來是1的變成0）。 但是產生的新狀態必須是之前從來沒產生的。你的任務是：從N個0的狀態出發，把2^N個狀態都訪問一次，最后重新能回到N個0的狀態。 請你把這個轉換過程輸出來，如果有多種方案成立，任意輸出一種。

這是三位數的樣例輸出：

OOO

OXO

OXX

OOX

XOX

XXX

XXO

XOO

OOO

刪去最后一行，就是2^N個狀態，我們發現這個圖像會基于中間這條線對稱

我們會想到如何構造這樣一個圖形。把第二行和第三行對調，就變成紅色字體的圖形。容易發現，最后一豎列是根據01對稱一次變成10，再如此對稱。而第二行0011，對稱為1100。第三行又翻一倍，00001111。實際上就是格雷碼。

所以可以用雙重循環實現，但就要用到二維數組，其實還可以用位運算進一步節省空間。用a[i]或1<<X來把1放在第（x+1）位。

附：位運算運算符

運算符　　含義

    &　　按位與

    |　　　按位或

     ^ 　　按位異或

  ~　　　取反

<< 　　左移

>> 　　右移

Test Taking

題目大意：

有N (1 <= N <= 1,000,000)個 true 或者false的問題。

其中答案是true的問題的個數有K種可能：t_1, t_2, t_3,..., t_K (0 <=t_i<= N; 0 <= K <= 10,000). 但是我們無法知道具體哪個問題的答案是true或false。

現在Bessie要回答這N個問題，為了在運氣最差的情況下答對的題目最多，她必須采取最優策略。

如：有6個問題，N=6， k = 2, t_1 = 0, t_2 = 3. 也就是說，這6個問題中，真命題的個數可能是0個，也可能是3個。那么Bessie為了在運氣最差的情況答對的問題最多，她可以回答每個問題都是的答案都是false. 可以看出，如果她運氣好的話，她能答對6題，但如果運氣差的話（即有3到是true的問題），那么她只能答對3題（因為她的回答是6個false）。

因此，Bessie在最差的情況下能答對3題。這就是最優策略。

分析：二分答案：針對每一個可能，都要分別驗證，看每個答案是否滿足每個可能，但我們發現二分答案的驗證實際上就有三種情況：

全選false，則采取true最多的可能

全選true，則采取true最少的可能

找出相鄰差最大的兩個可能，取其差的中間值

證明：排序，t_i設t_x 和 t_y是相鄰的兩個t_i（t_x>t_y）,可以保證（t_x-t_y）/2個正確答案，他只需選擇N-[(t_x+t_y)/2]個正確答案，其余全部選擇false

Need For Speed

題目大意：

賽車質量是M (1 <= M <= 1,000) ，馬力是F (1 <= F <= 1,000,000). 為了提升賽車性能，他可以到加工店添加一些零件。加工店有N(1 <= N <= 10,000)種零件，編號1..N， 每種零件只有一件。牛頓第二定理F =MA，（ F 是力, M是質量, A 是加速度）. 如果讓他的車的加速度最大(如果有多種方案，讓賽車的質量最小),應該配置哪些零件?

分析：

首先我們可以把每個加速度排序，然后加上去加速度越大的零件，提升也就越大，所以從大往小加，發現加了一個會使加速度變慢，就跳出循環。

陷阱：如果有多種方案，讓賽車的質量最小。