枚举与搜索例题-刘汝佳.ppt

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

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

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

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

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