暗影小站

Time Limits: 1000 ms Memory Limits: 65536 KB Description Alice上化学课时又分心了，他首先画了一个3行N列的表格，然后把数字1到N填入表格的第一行，保证每个数只出现一次，另外两行他也填入数字1到N，但不限制每个数字的出现次数。 　　Alice现在想删除若干列使得每一行排完序后完全一样，编程计算最少需要删除多少列。 Input 第一行包含一个整数N(1<=N<=100000)，表示表格的列数。 　　接下来三行每行包含N个整数，每个数在1到N之间，而且第一行的数互不相同。 Output 输出最少需要删除的列数。 Sample Input 1234567891011输入1：75 4 3 2 1 6 75 5 1 1 3 4 73 7 1 4 5 6 2输入2：91 3 5 9 8 6 2 4 72 1 5 6 4 9 3 4 73 5 1 9 8 6 2 8 7 Sample Output 12345输出1：4输出2：2 Data Constraint Hint 【样例解释】 　　例1中Alice需要删除第2、4、6、 ...

时间限制: 1000 ms 空间限制: 131072 KB 题目描述 Bessie受雇来到John的农场帮他们建立internet网络。农场有 N (2<= N <= 1,000)牛棚，编号为1…N。John之前已经勘测过，发现有 M (1<= M <= 20,000)条可能的连接线路，一条线路是连接某两个牛棚的。每条可能的线路都有一个建设费用 C (1<= C <=100,000)。John当然想花尽量少的钱，甚至克扣Bessie的工钱。 Bessie发现了这点，很生气，决定给John捣乱。她要选择一些线路组成网，但费用却尽可能大。当然网络要能正常工作，也就是任意两个牛棚之间都是相互可以连通的，并且网络上不能有环，不然John会很容易发现的。 请计算组建这种网络最多可能的费用。 输入 第一行：两个整数 N M 下面M行：每行3个整数 A，B，C。表示一个可能的线路要连接A、B两个牛棚，费用是C。 输出 只一行，一个整数，即花费最大的费用。如果不可能连接通所有牛棚，输出-1。 样例输入 样例输出 数据范围限制 提示 输入 5 8 1 2 3 ...

时间限制: 1000 ms 空间限制: 131072 KB 题目描述 John的奶牛们计划要跳到月亮上去。它们请魔法师配制了 P (1 <= P <=150,000)种药水，这些药水必需安原来的先后次序使用，但中间可以跳过一些药水不吃。每种药水有一个“强度”值 s ( 1 <= s <= 500 )，表示可以增强牛的跳跃能力。然而，药力的作用却是交替相反方向起作用，也就是说：当第奇数次吃药时，牛获得跳的更高的能力，而第偶数吃药时，却降低了跳高能力。在吃药前，牛的跳高能力当然为 0 。 每种药只能吃一次，开始时为第1次吃药。 请求出牛可能跳到的最高高度－－最大跳跃能力。 输入 第一行：一个整数 P 下面P行：每行一个整数，表示按先后次序要吃的药水的“强度”。 输出 只一个整数，表示最大弹跳能力。 样例输入 样例输出 数据范围限制 提示 输入 8 7 2 1 8 4 3 5 6 去掉第2、4两种药水， 吃药为： 7,1,8,3,6； 最终能力为： 7-1+8-3+6=17 输出 17 代码 12345678910111213141516#in ...

时间限制: 1000 ms 空间限制: 131072 KB 题目描述 全球气候变暖，小镇A面临水灾。于是你必须买一些泵把水抽走。泵的抽水能力可以认为是无穷大，但你必须把泵放在合适的位置，从而能使所有的水能流到泵里。小镇可以认为是N * M的矩阵。矩阵里的每个单元格都是一个‘a’- ‘z’小写字母，该小写字母表示该格子的高度，字母大的表示该单元格比较高，反之，表示该格子高度比较低。当前单元格的水可以流到上、下、左、右四个格子，但必须满足这些格子的高度是小于或者等于当前格子的高度。现在，给你一些N * M的矩阵，你至少要买多少个泵，才能把所有格子的水都能被抽走？ 输入 多组测试数据。 第一行：K，表示有K组测试数据。 1 <= K <= 5. 接下来有K组测试数据，每组测试数据格式如下： 第一行：两个正数, N , M . 1 <= N, M <= 50，表示小镇的大小。 接下来有N行，每行有M个小写字母，表示小镇的地图。 输出 共K行，每行对应一组数据。至少要买多少个泵，才能把所有格子的水都能抽走。 样例输入 样例输出 数据范围限制 提示 输入 2 5 5 ...

时间限制: 1000 ms 空间限制: 131072 KB 题目描述 近期，农场出现了D (1<= D <=15)种细菌。John 要从他的 N (1<= N <=1,000)头奶牛中尽可能多地选些产奶。但是如果选中的奶牛携带了超过 K (1<= K <=D)种不同细菌，所生产的奶就不合格。请你帮助John 计算出最多可以选择多少头奶牛。 输入 第一行：三个整数 N， D， K 下面N行：第行表示一头牛所携带的细菌情况。第一个整数 di 表示这头牛所携带的细菌种类数，后面di个整数表示这些细菌的各自种类标号。 输出 只一个数 M，最大可选奶牛数。 样例输入 样例输出 数据范围限制 提示 样例 输入 6 3 2 0 1 1 1 2 1 3 2 2 1 2 2 1 选择： 1,2,3,5,6 只有1#和2#两种细菌 输出 5 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#inc ...

Time Limits: 1000 ms Memory Limits: 65536 KB Description Alice想让Bob陪他去看《唐山大地震》，但由于Bob是个很感性的人，怕流泪不想去，但又不好意思以这个作为拒绝的理由，便提出玩一个游戏。 　　N个正整数围成一圈，规则如下： 　　•两个玩家轮流取数； 　　•最开始先手的玩家可以取任意一个数x； 　　•从第二步开始当前玩家只能取x（上一玩家刚刚取的数）左右两边相邻的数； 　　•直到取完所有的数，游戏结束； 　　•取得较多奇数的玩家获胜。 　　Bob为了显示大度，让Alice先取，但他忘了自己和Alice都是绝顶聪明之人，现在Alice请你帮他计算第一步有多少种取法使得最终获得胜利。 Input 第一行包含一个整数N(1<=N<=100)，表示数的个数。第二行包含N个正整数，每个数都在1到1000之间，任意两个数互不相同。 Output 输出Alice第一步有多少种取法。 Sample Input 1234567891011输入1：33 1 5输入2：41 2 3 4输入3：84 10 5 2 9 8 1 7 S ...

Time Limits: 1000 ms Memory Limits: 65536 KB Description 自行车赛在一个很大的地方举行，有N个镇，用1到N编号，镇与镇之间有M条单行道相连，起点设在镇1，终点设在镇2。 问从起点到终点一共有多少种不同的路线。两条路线只要不使用完全相同的道路就被认为是不同的。 Input 第一行两个整数：N和M(1<=N<=10000,1<=M<=100000)，表示镇的数量和道路的数量。 接下来M行，每行包含两个不同的整数A和B，表示有一条从镇A到镇B的单行道。 两个镇之间有可能不止一条路连接。 Output 输出不同路线的数量，如果答案超过9位，只需输出最后9位数字。如果有无穷多的路线，输出“inf”。 Sample Input 1234567891011121314151617181920212223242526272829303132333435363738394041424344输入1：6 7 1 3 1 4 3 2 4 2 5 6 6 5 3 4 输入2：6 8 1 3 1 4 3 2 4 2 5 6 6 5 ...

Time Limits: 1000 ms Memory Limits: 65536 KB Description 你家刚买了一套新房，想邀请朋友回来庆祝，所以需要一个很大的举行餐桌，餐桌能容纳的人数等于餐桌的周长，你想买一个能容纳最多人的餐桌，餐桌的边必须跟房间的边平行。 给你的房间的设计，计算最多能邀请的客人数。 Input 第一行包含两个整数R和C(1<=R,C<=2000)，表示房子的长和宽。 接下来R行每行S个字符（中间没有空格），“.”表示空白区域，“X”表示有障碍物，餐桌所占区域必须是空白的。 Output 输出最多能要求的客人数量。 Sample Input 1234567891011121314151617输入1：2 2....输入2：4 4 X.XX X..X ..X. ..XX 输入3：3 3 X.X .X. X.X Sample Output 12345678输出1：7输出2：9输出3：3 Data Constraint Hint 【数据规模】 50%的数据R,C<=400 70%的数据R,C<=1000 100%的数据，R,C< ...

Time Limits: 2000 ms Memory Limits: 65536 KB Description 每个人都知道詹姆斯邦德，著名的007，但很少有人知道很多任务都不是他亲自完成的，而是由他的堂弟们吉米邦德完成（他有很多堂弟），詹姆斯已经厌倦了把一个个任务分配给一个个吉米，他向你求助。 每个月，詹姆斯都会收到一些任务，根据他以前执行任务的经验，他计算出了每个吉米完成每个任务的成功率，要求每个任务必须分配给不同的人去完成，每个人只能完成一个任务。 请你编写程序找到一个分配方案使得所有任务都成功完成的概率。 Input 输入第一行包含一个整数N,表示吉米邦德的数量以及任务的数量（正好相等,1<=N<=20）。 接下来N行，每行包含N个0到100之间整数，第i行的第j个数Aij表示吉米邦德i完成任务j成功的概率为Aij% Output 输出所有任务成功完成最大的概率，结果保留6位小数。 Sample Input 123456789101112131415输入1：2 100 100 50 50 输入2：2 0 50 50 0 输入3：3 25 60 100 13 0 ...

Time Limits: 1000 ms Memory Limits: 65536 KB Description 一天， 一个画家在森林里写生，突然爆发了山洪，他需要尽快返回住所中，那里是安 全的。 森林的地图由R行C列组成，空白区域用点“.”表示，洪水的区域用“*”表示，而 岩石用“X”表示，另画家的住所用“D”表示，画家用“S”表示。 有以下几点需要说明： 1、 每一分钟画家能向四个方向移动一格（上、下、左、右） 2、 每一分钟洪水能蔓延到四个方向的相邻格子（空白区域） 3、 洪水和画家都不能通过岩石区域 4、 画家不能通过洪水区域（同时也不行，即画家不能移到某个格子，该格子在画家达到的同时被洪水蔓延到了，这也是不允许的） 5、 洪水蔓不到画家的住所。 给你森林的地图，编写程序输出最少需要花费多长时间才能从开始的位置赶回家中。 Input 输入第一行包含两个整数R和C(R,C<=50)。 接下来R行每行包含C个字符(“.”、“*”、“X”、“D”或“S”)。地图保证只有一个“D”和一个“S”。 Output 输出画家最快安全到达住所所需的时间，如果画家不可能安全回家则输出“ ...