1、枚舉與搜索例題版本20071002,清華大學 劉汝佳,Multiples,求min,max有多少個整數(shù)是n的整數(shù)倍。 1=n=1000, -106=min=max=106,LCMRange,求a,b中所有數(shù)的最小公倍數(shù) 1=a=b=12,Workshop,給出n個1到10000之間的整數(shù)，以它們?yōu)檫呴L（每個整數(shù)最多選一次）能組成多少個不同的三角形？1=n=50。,ObtainingDigitK,給一個最多50位的正整數(shù)n，至少加幾（非負整數(shù)），使得和包含數(shù)字k(09),Stairs,你需要設計以垂直部分開始和結(jié)束的階梯。每段水平距離均相同且為不小于minWidth的正整數(shù)，每段垂直距離也相同且

2、為不大于maxHeight的正整數(shù)。 給出總水平距離W和高度H，求滿足條件的階梯總數(shù)。 例如maxHeight=22, minWidth=25, W=H=100，則只有一種方案：每段垂直距離為20，每段水平距離25,Reppity,給字符串S，找出至少出現(xiàn)兩次（不重疊）的、盡量長的子串 S=ABCDEXXXYYYZZZABCDEZZZYYYXXX，則ABCDE為所求,CalcButton,給一個數(shù)字串，你可以設計一個3數(shù)字鍵，使得敲出這個數(shù)字串的擊鍵次數(shù)盡量少 例如100002000，如果設計出的3數(shù)字鍵為000，則只需要敲5次鍵盤：1-000-0-2-000 串的長度不超過2500,Pric

3、ing,給n個非負整數(shù)，把它們分成最多4份。把每份中的所有數(shù)都改成它們中的最小值，要求所有數(shù)之和盡量大。 1=n=50,PaternityTest,給出孩子和母親的DNA序列。對于一個可能是父親的DNA序列，判斷是否能找出把所有位置平均分成兩半，使得一半位置上孩子和父親相同，其他所有位置孩子和母親相同。孩子、母親和父親的DNA序列長度均為n=20,OptimalGroupMovement,有n=50個square，有的有counter有的沒有。連續(xù)的counter必須整體的連續(xù)移動，移動一格的費用為C2(C為該整體所包含的counter數(shù)）。要求所有counter成為一個整體，總費用盡量小。

4、例如.XXX.XXXX.的最小費用為9。,Cubism,給一個4*4*4的大立方體，每個單位小立方體為白色或者黑色。給一個顏色，統(tǒng)計有多少條長度為4的小立方體序列（所有小立方體的中心必須在同一條直線上，相鄰立方體可以有公共面、公共邊或者公共頂點）。,LargestCircle,給一個n*m(1=n,m=50)網(wǎng)格，有黑有白。求一個圓心在某正方形頂點的，半徑為整數(shù)的圓，邊界不通過任何黑格（但可以經(jīng)過黑格的邊界）。圓必須完全在網(wǎng)格中。,RegimentArming,一個很大的數(shù)組被分成n段，每段有counti個數(shù)poweri。要求選連續(xù)的m個數(shù)，使得和盡量大。 1=n=50, 1=m=109, 1

5、=counti=109.,CaptureThemAll,8*8棋盤上有一個白knight和一個黑queen和黑rook。黑子都不動，用盡量少的移動讓白knight吃掉兩個黑子。 例如白knight在a1, 黑子在b3和c5時只需要兩步即可。,Arcs,給一個W*H(1=W,H=50黑白網(wǎng)格。求一條從(0,0)到(W,H)的路徑，由盡量少的90度圓弧構(gòu)成，要求路徑邊界不通過任何黑格（但可以經(jīng)過黑格的邊界）?；〉膱A心在某頂點，邊長為整數(shù)，且起點終點的極角均為90度的倍數(shù)。,MNS,給出9個09之間的整數(shù)，把它們放在3*3網(wǎng)格中，使得3行3列之和全部相等（行和等于列和），如： 1 2 3 3 2 1

6、 2 2 2 求方案總數(shù)。如果兩個網(wǎng)格至少有一個位置上的數(shù)不同，就被視為不同的方案。,TennisRallies,給一個只包含c和d的字符串，有m個（連續(xù)）子串是敏感的。這些敏感字符串出現(xiàn)的總次數(shù)必須小于k。例如ccccdd出現(xiàn)了3次cc，1次cd和1次ccd，一共5次。 給出長度n，統(tǒng)計滿足條件的串的個數(shù)。 1=n=18, 0=m=10, 1=k=100,PickTeam,有n個人，要求選出k個人，使得它們之間兩兩合作系數(shù)ai,j之和盡量大。 3=n=20, 2=k=n 如下表，有三種方法選出3個人： ABC:1 + -1 + 2 = 2 ABD:1 + 3 + -4 = 0 ACD:-1

7、+ 3 + 2 = 4 BCD:2 + -4 + 2 = 0 其中第三種方案最好。,Mafia,簡化版的殺人游戲的規(guī)則如下： n(=16)個玩家被分為兩種：殺手和平民。殺手知道每個人的身份，但平民不知道。 如果有偶數(shù)的玩家，則是“深夜”。殺手商量出一個平民并把他暗殺掉。 如果有奇數(shù)個玩家，則是“白天”。游戲者投票選出一個嫌疑最大的人并處死。 如果在某一輪中所有殺手都被處死了，或者所有平民都被殺掉了，則游戲結(jié)束，還有人活著的一方勝利。,Mafia (Cont.),每個人（包括殺手和平民）當前的嫌疑用數(shù)組guilt表示，而暗殺對guilt的影響用矩陣responses描述。 當?shù)趇個人被暗殺后，每個人j的guiltj增加responsei,j。 每次guilt最大的人被處死。如果有多個人的guilt最大，則編號最小的人被處死。被處死后所有人的guilt不變。 你是殺手，并且你的同伙全部被處死了。你的任務是讓你自己存活的時間盡量長。,