国家集训队2005论文集 金恺

《国家集训队2005论文集 金恺》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、杂题大拼盘清华大学计42班金恺第一题新L游戏问题描述一个n行m列的棋盘，里面有一个或0个格子已经损坏。请在棋盘上放一些L棋子(如下)，使每个未损坏的格子都恰巧被一个L拼块覆盖。例如输入有若干行(不超过100)，每行为一组数据：每行四个整数n,m,x,y；若x=0,y=0则表示所有格子都未损坏，否则表示第x行第y列的格子已损坏。如果有解输出“Iknow!”否则输“Noans!”数据范围1≤n,m≤10100输入样例：551156009300100001000050004000输出样例：Iknow!Iknow!Noan

2、s!Iknow!第二题消灭魔鬼有N×M的格栅，每个格子不是平地就是障碍物（边界为障碍物）。光线能水平或竖直的在平地上行进，但是遇到障碍物就会引发爆炸。某些平地上已经事先安放上了镜子，有两种方向的镜子（都是双面的）光线射在镜子上就会反射，满足反射角=入射角。镜子#1镜子#2战士手拿激光枪站在A格的中心，魔鬼站在B格中心（A、B格都是平地且A≠B），请帮助战士消灭魔鬼：在某些平地上添加一些镜子，然后告诉战士往哪个方向开激光枪。数据范围：4≤N,M≤1000约束：任意两面镜子（包括事先放好的和你新添加的）都不能放在同一格

3、上；不能让任何一个障碍物爆炸；数据保证有解；镜子越少越好。AB平地障碍物AB输出最小需要添加的镜子数此例输出2进一步思考扩展用最小费用消灭魔鬼删除原有镜子，费用f1，改变镜子的方向，费用f2，添加新的镜子，费用f3，移除障碍物，费用f4。第三题机器人迷宫有一个n×m的迷宫，每个格子不是平地就是障碍物（边界都是障碍物）。有p个机器人，全都站在平地上。某一时刻，你可以向所有机器人发布相同的指令，指令有N、S、W、E，告诉机器人向某个方向前进。N表示向上，S表示向下，W表示向左，E表示向右。如果某个机器人能够往该方向前进

4、（即不碰到障碍物）则向该方向移动一格，否则原地不动。要求用不超过maxint条指令集结所有机器人——即让他们到达同一位置。数据范围：n,m≤50,p≤20。输出：一个ESWN序列。序列长度不能超过maxint；要求所有机器人按着这个序列执行后到达同一格。思路2个机器人若在某个时刻T在同一位置，那么T时刻以后永远处在同一位置；先处理P=2，即两个机器人然后每次选择两个位置不同的机器人，把他们合并，直到所有机器人都在同一个位置。如何集结指定的2个机器人？追赶法……思考合并两个机器人的时间复杂度更低的方法？用尽量少的步数

5、？最少的步数？数据规模更大？别的思路？比如给整体局面打分，每次移动都是整体更加靠紧，局面分降到0就恰好使机器人都集结（思路而已）。第4题正三角形（交互）题目背景：你仅有一个生锈的圆规，半径固定为1。平面上有3个点：O(0,0)A(a,0)0

6、都为新的可操作的点。目标，使得点C可操作,其中ABC构成正三角形。第五题战国长城战国时期，各诸侯国为了保护领土，建造了大量的长城。长城是由烽火台和城墙组成的。烽火台用一个平面上的点表示，而长城则是连接两个烽火台的一堵笔直的墙，任意两堵墙不会在非烽火台处相交。任意一个烽火台都有偶数堵城墙与它相连，每两个诸侯国都不相邻，也就是说他们不会共有同一堵墙，但是有可能于某个烽火台相邻。问题：由于时代久远，当时具体有多少个诸侯国已无从考证。所以，历史学家们找到了参加信息学竞赛的你，请你根据长城的遗址计算最多可能拥有的诸侯国数。x

7、y第六题传输奶牛平面上n个已知点。请你找出一个宽为Len，长为正无穷的矩形长条；使得长条中包含的已知点尽量多。N<=1000，坐标都是绝对值不超过1000的整数。