枚举与搜索例题刘汝佳

1、枚举与搜索例题版本1Multiples求min,max有多少个整数是n的整数倍。1=n=1000, -106=min=max=1062LCMRange求a,b中所有数的最小公倍数1=a=b=123Workshop给出n个1到10000之间的整数，以它们为边长（每个整数最多选一次）能组成多少个不同的三角形？1=n=50。4ObtainingDigitK给一个最多50位的正整数n，至少加几（非负整数），使得和包含数字k(09)5Stairs你需要设计以垂直部分开始和结束的阶梯。每段水平距离均相同且为不小于minWidth的正整数，每段垂直距离也相同且为不大于maxHeight的正整数。给出总水平距

2、离W和高度H，求满足条件的阶梯总数。例如maxHeight=22, minWidth=25, W=H=100，则只有一种方案：每段垂直距离为20，每段水平距离256Reppity给字符串S，找出至少出现两次（不重叠）的、尽量长的子串S=ABCDEXXXYYYZZZABCDEZZZYYYXXX，则ABCDE为所求7CalcButton给一个数字串，你可以设计一个3数字键，使得敲出这个数字串的击键次数尽量少例如100002000，如果设计出的3数字键为000，则只需要敲5次键盘：1-000-0-2-000串的长度不超过25008Pricing给n个非负整数，把它们分成最多4份。把每份中的所有数都改

3、成它们中的最小值，要求所有数之和尽量大。1=n=509PaternityTest给出孩子和母亲的DNA序列。对于一个可能是父亲的DNA序列，判断是否能找出把所有位置平均分成两半，使得一半位置上孩子和父亲相同，其他所有位置孩子和母亲相同。孩子、母亲和父亲的DNA序列长度均为n=2010OptimalGroupMovement有n=50个square，有的有counter有的没有。连续的counter必须整体的连续移动，移动一格的费用为C2(C为该整体所包含的counter数）。要求所有counter成为一个整体，总费用尽量小。例如.XXX.XXXX.的最小费用为9。11Cubism给一个4*4*

4、4的大立方体，每个单位小立方体为白色或者黑色。给一个颜色，统计有多少条长度为4的小立方体序列（所有小立方体的中心必须在同一条直线上，相邻立方体可以有公共面、公共边或者公共顶点）。12LargestCircle给一个n*m(1=n,m=50)网格，有黑有白。求一个圆心在某正方形顶点的，半径为整数的圆，边界不通过任何黑格（但可以经过黑格的边界）。圆必须完全在网格中。13RegimentArming一个很大的数组被分成n段，每段有counti个数poweri。要求选连续的m个数，使得和尽量大。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黑白网格。求一条从(0,0)到(W,H)的路径，由尽量少的90度圆弧构成，要求路径边界不通过任何黑格（但可以经过黑格的边界）。弧的圆心在某顶点，边长为整数，且起点终点的极角均为90度的倍数。16MNS给出9个09之间的整数，把它们放在3*3网格中，使得3行3列之和全部相等（行和等于列和），如：1 2 33 2 12 2 2求方案总数。如果两个网格至少有一个位置上的数不同，就被视为不同的方案

6、。17TennisRallies给一个只包含c和d的字符串，有m个（连续）子串是敏感的。这些敏感字符串出现的总次数必须小于k。例如ccccdd出现了3次cc，1次cd和1次ccd，一共5次。给出长度n，统计满足条件的串的个数。1=n=18, 0=m=10, 1=k=10018PickTeam有n个人，要求选出k个人，使得它们之间两两合作系数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简化版的杀人游戏的规则如下：n(=16)个玩家被分为两种：杀手和平民。杀手知道每个人的身份，但平民不知道。如果有偶数的玩家，则是“深夜”。杀手商量出一个平民并把他暗杀掉。如果有奇数个玩家，则是“白天”。游戏者投票选出一个嫌疑最大的人并处死。如果在某一轮中所有杀手都被处死了，或者所有平民都被杀掉了，则游戏结束，还有人活着的一方胜利。20Mafia (Cont.)每个人（包括杀手和平民）当前的嫌疑用数组guilt表示，而暗杀对guilt的影响用矩阵responses描述。当第i个人被暗杀后，每个人j的guiltj增加responsei,j。每次guilt最大的人被处死。如果有多个人的guilt最大，则编号最小的人被处死。被处死后所有人的guilt不变。你是杀手，并且你的同伙全部被处死了。你的任务是让你自己存活的时间尽量长。21V