山东2011省选第二轮第二试

2011年全国青少年信息学奥林匹克山东省省队选拔赛（第二轮）第二试竞赛时间：2011年4月17日上午8:0012:00题目名称贪食蛇保密消耗战目录snaketfnhnsmrepair可执行文件名snake.exetfnhnsm.exerepair.exe输入文件名snake.intfnhnsm.inrepair.in输出文件名snake.outtfnhnsm.outrepair.out每个测试点时限1s1s2s测试点数目201010每个测试点分值51010内存限制512MB512MB512MB是否有部分分无无无题目类型传统型传统型传统型提交源程序须加后缀对于Pascal语言paspaspas对于C 语言ccc对于C+ 语言cppcppcpp注意：最终测试时，所有编译命令均不打开任何优化开关。贪食蛇（snake）【问题描述】相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。活动区域：贪食蛇的活动区域是一个R行C列的网格A，贪食蛇活动不能超过这个网格的范围。第i行第j列的方格用Ai,j表示。每个方格有一个整数权值，记作w(Aij)。0=w(Aij)0时，Aij允许进入。方向：对于P=(X0,Y0)、Q=(X1,Y1)，有以下四种基本方向：l 正左(L)：X0=X1且Y0=Y1-1，则称P位于Q的正左方向。l 正右(R)：X0=X1且Y0=Y1+1，则称P位于Q的正右方向。l 正上(U)：X0=X1-1且Y0=Y1，则称P位于Q的正上方向。l 正下(D)：X0=X1+1且Y0=Y1，则称P位于Q的正下方向。贪食蛇：贪食蛇B是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为m，则贪食蛇从头到尾，用B1、B2、Bm表示。记p为贪食蛇的形态，若Bi位于第Xi行第Yi列，则p(Bi)=(Xi,Yi)。初始情况下，m=4，且运动过程中始终需要满足以下限制：l 对于Bi和Bi+1(1=im)，就是贪食蛇的前、后相邻两部分，必须满足Bi位于Bi+1的L、R、U、D四个方向之一。l 对于Bi和Bj(1=ij=m)，p(Bi)=(Xi,Yi)，p(Bj)=(Xj,Yj)，需要满足Xi!=Xj或Yi!=Yj。也就是说，贪食蛇身体的任意一部分不能相交。食物：贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上，食物不会重叠。每个食物只能被吃一次。贪食蛇的运动：如果贪食蛇的头部B1的L、R、U、D四个方向之一的Aij能进入，且Aij上不存在食物，则贪食蛇可以向该方向运动，新的头部位于Aij上。记p为贪食蛇新的形态，则：l p(Bk)=p(Bk-1)，当2=k=m。l p(Bk)=(i,j)，当k=1贪食蛇的进食：如果贪食蛇的头部B1的L、R、U、D四个方向之一的Aij能进入，且Aij上存在食物，则贪食蛇可以向该方向进食，新的头部位于Aij上，蛇的新长度m=m+1。记p为贪食蛇新的位置，则：l p(Bk)=p(Bk-1)，当2=k=m。l p(Bk)=(i,j)，当k=1注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置，因为在变换后头部和尾部仍不会重叠。运动或进食所需要的时间：贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是P，运动或进食后头部所在的方格是Q，则此次运动或进食的所消耗的时间为|w(P)-w(Q)|+1。游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。【输入格式】第一行，两个正整数R、C。接下来R行，每行C个没有空格分隔的数字。其中第i行第j个数字为w(Aij)。接下来4行，每行2个正整数。第i行的两个整数Xi、Yi，表示p(Bi)=(Xi,Yi)。接下来一个正整数N，表示食物的数量。接下来N行，每行2个正整数i、j，表示Aij上存在一个食物。【输出格式】如果贪食蛇不能吃到所有的食物，输出“No solution.”（不包括引号）。否则，输出：第一行，一个整数，表示所需花费的时间；第二行，一个由L、R、U、D组成的字符串，表示贪食蛇前进的方案。如果存在多种可能，你只需输出任意一种。【样例输入】5 511011110111101111011114111 12 13 14 145 54 42 51 4【样例输出】21RDDDDRRRULURULU【数据规模和约定】对于20%的数据，N = 1。对于40%的数据，N = 2。对于60%的数据，N = 3。对于100%的数据，N = 4。对于30%的数据，R * C = 36。对于100%的数据，R = 12，C = 12。This filename has no special meanings（tfnhnsm）【问题描述】现在，保密成为一个很重要也很困难的问题。如果没有做好，后果是严重的。比如，有个人没有自己去修电脑，又没有拆硬盘，后来的事大家都知道了。当然，对保密最需求的当然是军方，其次才是像那个人。为了应付现在天上飞来飞去的卫星，军事基地一般都会建造在地下。某K国的军事基地是这样子的：地面上两排大天井共n1个作为出入口，内部是许多除可以共享出入口外互不连通的空腔，每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为1,3,5和2,4,6并且最大的编号为n1。虽然上面扯了那么多关于保密的东西，但是其实解密也是一件很纠结的事情。但其实最简单直接暴力无脑的解密方法就是找个人去看看。我们有很牛X的特种部队，只需要派出一支特种部队到K国基地的某个出入口，那么和这个出入口直接相连的所有空腔都可以被探索，但也只有这些空腔可以被这支部队探索。现在有足够多的特种部队可以供你调遣，你必须使用他们调查完所有的K国基地内的空腔。当然，你的基地离K国基地不会太近，周边的地图将会给你，表示为n个检查点和m条连接这些点的道路，其中点1到点n1就是K国基地的出入口，点n是你的部队的出发点。对每条道路，有不同的通行时间t和安全系数s。因为情报部门只对单向的道路安全系数进行了评估，所以这些道路只允许单向通行，并且不会存在环。一支特种部队从你的基地出发，通过某条路径，到达某个K国基地出入口，此时这支部队的危险性表示为总时间和这条路径经过的所有道路的安全系数和的比值。整个行动的危险性表示为你派出的所有部队的危险性之和。你需要使这个值最小的情况下探索整个K国基地。快点完成这个任务，在K国的叫兽宣布你是K国人之前。【输入格式】第一行2个正整数n，m (4 = n = 700, m = 100000) 表示整个地区地图上的检查点和道路数。下面m行，每行4个正整数a, b, t, s(a, b =n, 1 = t, s = 10)表示一条从a到b的道路需时为t，安全系数为s。接下来1行2个正整数m1和n1(m1 = 40000, n1 minn, 161), m1表示K国基地空腔的个数，n1表示K国基地出入口的个数。再接下来m1行，每行2个正整数u, v (u, v=n1, u是奇数，v是偶数)，表示每个空腔的2个出入口。 【输出格式】一行，最小的危险性，保留一位小数。或者输出”-1”（无引号）表示此任务不可能完成。【样例输入】5 55 1 10 15 1 10 15 2 9 15 3 7 15 4 8 14 41 21 43 23 4【样例输出】17.0【数据规模和约定】对30%的数据，n=30对60%的数据，n=300另外 40%的数据n1=20消耗战（repair）【问题描述】在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。【输入格式】第一行一个整数n，代表岛屿数量。接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1=u,v=n且1=c=100000。第n+1行，一个整数m，代表敌方机器能使用的次数。接下来m行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,hk，表示资源丰富岛屿的编号。【输出格式】输出有m行，分别代表每次任务的最小代价。【样例输入】101 5 131 9 62 1 192 4 82 3 915 6 87 5 47 8 3110 7 932 10 64 5 7 8 33 9 4 6【样例输出】123222【数据规模和约定】对于10%的数据，2=n=10,1=m=5,1=ki=n-1对于20%的数据，2=n=100,1=m=100,1=ki=min(10,n-1)对于40%的数据，2=n=1,sigma(ki)=500000,1=ki=min(15,n-1)对于100%的数据，2=n=1,sigma(ki)=500000,1=ki=n-1