枚舉與搜索例題劉汝佳

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

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

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

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

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

6、。17TennisRallies給一個只包含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=10018PickTeam有n個人，要求選出k個人，使得它們之間兩兩合作系數(shù)ai,j之和盡量大。3=n=20, 2=k=n如下表，有三種方法選出3個人：ABC:1 + -1 + 2 = 2ABD:1 + 3 + -4 = 0ACD:-1 + 3 + 2 = 4BCD:2 + -4 + 2 = 0其中第三種方案最好。02-43DAVI

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