這一節(jié)以模擬題為主，比較惡心。一道動態(tài)規(guī)劃，一道枚舉。
Preface Numbering
問題描述：
先是介紹羅馬數(shù)字書寫（略），給出一個數(shù)字，求1到這個數(shù)字之間所有數(shù)字的羅馬表示中共出現(xiàn)幾個I，V，X，L，C，D，M。
分析：
最初的思路是一個個地模擬：觀察后可以發(fā)現(xiàn)，46可以表示為XLVI，以數(shù)組s[1…7]表示I…M，則47為2111000，而4為1100000，7為21000000，總結(jié)可知s[n][1]=s[n%10][1];s[n][2]=s[n%10][2];（注意n%10==9的話，s[n][3]+=s[9][3]）。2<=i<=7時， s[n][i]=s[n/10][i-2]。
其實完全可以分段統(tǒng)計，比如234，個位出現(xiàn)了23個0~9，1個0~4，十位出現(xiàn)了20個0~9，1個0~3，百位出現(xiàn)了1、2；
Subset Sums
問題描述：
對于從1到N (1 <= N <= 39) 的連續(xù)整數(shù)集合，能劃分成兩個子集合，且保證每個集合的數(shù)字和是相等的。給出N，你的程序應該輸出劃分方案總數(shù)，如果不存在這樣的劃分方案，則輸出0。
分析：
看完題目最先想到的是深搜，枚舉所有可能，當其和等于總和一半的時候則記錄。但提交后發(fā)現(xiàn)，當N為31，程序算了7、8秒才出答案?？磥砩钏咽遣恍辛?，在網(wǎng)上看了別人的解法才知道要動態(tài)規(guī)劃。其實應該算遞推，令ans[i][j]表示前i個數(shù)里面和為j的方案數(shù)，則ans[i][j]可以等于前i-1個數(shù)字里面和為j的方案數(shù)（即不含數(shù)字j的方案），加上前i-1個數(shù)字里和為j-i的方案數(shù)（即最終含有數(shù)字j，,ans[N][N*(N+1)/4]即為最終解。狀態(tài)轉(zhuǎn)移方程為：
ans[i][j]=ans[i-1][j]+ans[i-1][j-i];
Runaround Numbers
問題描述：
尋找循環(huán)數(shù)----從最右的數(shù)字出發(fā)，走數(shù)字對應的步數(shù)，然后從所停的數(shù)字繼續(xù)出發(fā)，再走剛才所停數(shù)字對應步數(shù)，直到回到出發(fā)點。
分析：
循環(huán)數(shù)有點類似約瑟夫環(huán)，直接模擬即可，從題目所給數(shù)字開始一個個枚舉。注意：數(shù)字不含0；回到起始點前，每一位都必須停留過一次且必須只停一次。
Party Lamps
問題描述：
有四個按鈕控制N盞燈，10<=N<=100
按鈕1：當按下此按鈕，將改變所有的燈：本來亮著的燈就熄滅，本來是關著的燈被點亮。
按鈕2：當按下此按鈕，將改變所有奇數(shù)號的燈。
按鈕3：當按下此按鈕，將改變所有偶數(shù)號的燈。
按鈕4：當按下此按鈕，將改變所有序號是3*K+1(K>=0)的燈。例如：1,4,7...
一個計時器記錄按下按鈕的次數(shù)C，現(xiàn)給出C，和某些燈的最終開關狀態(tài)，求所有的燈最終可能的所有狀態(tài)。
分析：
這題很久以前就見過了，覺得比較麻煩，就一直沒動，現(xiàn)在不動不行了。在紙上分析后會發(fā)現(xiàn)，燈的狀態(tài)是六個一組循環(huán)出現(xiàn)的，故只需得出前六個燈的狀態(tài)，后面的燈的狀態(tài)就可知了。每盞燈有開關兩種狀態(tài)，四個循環(huán)枚舉即可。在網(wǎng)上看了一下別人的解法，用二進制表示狀態(tài)是比較方便的，于是我決定第一次嘗試位運算解題。
由于異或運算符的特點：0和1異或1以后取反，異或0不變。第一種操作可以用n^(111111)2實現(xiàn)，第二種操作用n^(101010)2實現(xiàn)，第三種用n^(10101)2實現(xiàn)，第四種用n^(100100)2實現(xiàn)。
對于狀態(tài)的讀取，我想不出什么好辦法。只好這樣了：
int ReadOn()
{ bool tem[6];
memset(tem,false,sizeof(tem));
int i,c;
while(fin>>c&&c!=-1)
tem[(c-1)%6]=true;//此處燈亮，則令其為1
c=0;
for(i=0;i<6;i++)
{ c=c<<1;
if(tem[i])
c+=1;
}
return c;//c的二進制表示就是題目給出的部分燈亮的狀態(tài)
}
例如，測試數(shù)據(jù)給出2號燈亮，則最終狀態(tài)里2位上的必為1，表示為：010000 。讀入不亮的燈的函數(shù)做相應修改即可。
判斷當前枚舉得到的狀態(tài)是否滿足要求可用以下方法：
if(a+b+c+d<=times)
if((state|Off)==Off)
{ if((state&On)==On)//Off表示測試數(shù)據(jù)給出的不亮的燈 On表示亮的燈（即限制條件）
ans[state]=true;
if(state==0&&On==0)
ans[state]=true;
}
第五行如果state是0即都不亮，而On也為0，本來應該是符合的，但由于0&0=1！=0.所以在后面補上。