枚舉與搜索例題劉汝佳

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

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

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

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

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

6、。17TennisRallies給一個(gè)只包含c和d的字符串，有m個(gè)（連續(xù)）子串是敏感的。這些敏感字符串出現(xiàn)的總次數(shù)必須小于k。例如ccccdd出現(xiàn)了3次cc，1次cd和1次ccd，一共5次。給出長(zhǎng)度n，統(tǒng)計(jì)滿(mǎn)足條件的串的個(gè)數(shù)。1=n=18, 0=m=10, 1=k=10018PickTeam有n個(gè)人，要求選出k個(gè)人，使得它們之間兩兩合作系數(shù)ai,j之和盡量大。3=n=20, 2=k=n如下表，有三種方法選出3個(gè)人：ABC:1 + -1 + 2 = 2ABD:1 + 3 + -4 = 0ACD:-1 + 3 + 2 = 4BCD:2 + -4 + 2 = 0其中第三種方案最好。02-43DAVI

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