暗影小站

Time Limits: 4000 ms Memory Limits: 65536 KB Description 二维平面坐标系中有N个点。 从N个点选择3个点，问有多少选法使得这3个点形成直角三角形。 Input 第一行包含一个整数N(3<=N<=1500)，表示点数。 接下来N行，每行包含两个用空格隔开的整数表示每个点的坐标，坐标值在-10^9到10^9之间。 每个点位置互不相同。 Output 输出直角三角形的数量。 Sample Input 1234567891011121314151617181920输入1：34 22 11 3输入2：45 02 68 65 7输入3：5-1 1-1 00 01 01 1 Sample Output 12345678输出1：1输出2：0输出3：7 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737 ...

Time Limits: 1000 ms Memory Limits: 65536 KB Description Alice收到一些很特别的生日礼物：区间。即使很无聊，Alice还是能想出关于区间的很多游戏，其中一个是，Alice从中选出最长的不同区间的序列，其中满足每个区间必须在礼物中，另序列中每个区间必须包含下一个区间。 　　编程计算最长序列的长度。 Input 输入文件第一行包含一个整数N(1<=N<=100000)，表示区间的个数。 　　接下来N行，每行两个整数A和B描述一个区间(1<=A<=B<=1000000)。 Output 输出满足条件的序列的最大长度。 Sample Input 12345678910111213141516171819202122输入1：33 42 51 6输入2：510 3020 4030 5010 6030 40输入3：61 41 51 61 72 53 5 Sample Output 12345678输出1：3输出2：3输出3：5 Data Constraint Hint 【样例解释】 　　例3中可以找到长度为5 ...

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< ...