第七届河南省大学生程序设计竞赛ACM网络热身赛题目
Yougth's Game[Ⅲ]
时间限制：3000 ms | 内存限制：65535 KB
描述: 有一个长度为n的整数序列，A和B轮流取数，A先取，每次可以从左端或者右端取一个数，所有数都被取完时游戏结束，然后统计每个人取走的所有数字之和作为得分，两人的策略都是使自己的得分尽可能高，并且都足够聪明，求A的得分减去B的得分的结果。
输入输入包括多组数据，每组数据第一行为正整数n（1<=n<=1000）,第二行为给定的整数序列，结束标志为n=0,。输出对于每组数据，输出A和B都采取最优策略的情况下，A的得分减去B的得分的结果。
样例输入
3
1 2 3
4
2 4 5 3
样例输出
2
0
非洲小孩
时间限制：1000 ms | 内存限制：65535 KB
描述 家住非洲的小孩，都很黑。为什么呢？
第一，他们地处热带，太阳辐射严重。
第二，他们不经常洗澡。（常年缺水，怎么洗澡。）
现在，在一个非洲部落里，他们只有一个地方洗澡，并且，洗澡时间很短，瞬间有木有！！（这也是没有的办法，缺水啊！！）
每个小孩有一个时间段能够洗澡。并且，他们是可以一起洗的（不管你是男孩是女孩）。
那么，什么时间洗澡，谁应该来洗，由谁决定的呢？那必然是他们伟大的“澡”神啊。“澡”神有一个时间表，记录着该部落的小孩，什么时候段可以洗澡。现在，“澡”神要问你，一天内，他需要最少开启和关闭多少次洗澡的水龙头呢？因为，开启和关闭一次水龙头是非常的费力气的，即便，这也是瞬间完成的。
输入多组数据
第一行一个0
接下来n行，每行一个时间段。H1H1:M1M1-H2H2:M2M2，24小时制。
保证该时间段是在一天之内的。但是，不保证，H1H1:M1M1先于H2H2:M2M2
输出题目描述，“澡”神最少需要开启和关闭多少次水龙头呢？
样例输入
1
00:12-12:12
2
00:12-12:12
14:00-12:00
样例输出
1
1
将军问题
时间限制：1000 ms | 内存限制：65535 KB
描述:关于中国象棋，想必大家都很熟悉吧。我们知道，在走棋的时候，被对方將军的这种情形是很容易被人察觉的(不然，你也太粗心了)。但是我们的计算机是如何识别这种情形的呢？它显然没有人的这种“直觉”。这就是我们今天要解决的问题，你的任务就是写一段计算机代码，根据当前局面信息，判断是否存在一方正在被另一方將军的情形，并给出正确结果。
如图一，象棋棋盘由九条竖线和十条横线交叉组成。棋盘上共有九十个交叉点，象棋子就摆放在和活动在这些交叉点上。棋盘中间没有画通直线的地方，叫做“九宫”。棋子共有三十二个，分为红、黑两组，每组共十六个，各分七种，其名称和数目如下：
红棋子： 帅一个，车、马、炮、相、仕各两个，兵五个。
黑棋子： 将一个，车、马、炮、象、士各两个，卒五个。
各种棋子的走法如下：
将（帅）每一步只许前进、后退、横走，但不能走出“九宫”。
士（仕）每一步只许沿“九宫”斜线走一格，可进可退。
象（相）不能越过“河界”，每一步斜走两格，可进可退，即俗称“象（相）走田字“。当田字中心有别的棋子时，俗称”塞象（相）眼“，则不许走过去。
马每步一直（或一横）一斜，可进可退，即俗称”马走日字“。如果在要去的方向有别的棋子挡住，俗称”蹩马腿”，则不许走过去。具体可参考图二。
车每一步可以直进、直退、横走，不限步数。
炮在不吃子的时候，走法跟车一样。在吃子时必须隔一个棋子（无论是哪一方的）跳吃，即俗称“炮打隔子”。
卒（兵）在没有过“河界”前，没步只许向前直走一格；过“河界”后，每步可向前直走或横走一格，但不能后退。
另外，在一个局面中，如果一方棋子能够走到的位置有对方将（帅）的存在，那么该局面就称为將军局面，我们的任务就是找出这样的局面。根据上述规则，我们很容易就能推断出只有以下几种方式才会造成將军局面：
1、将（帅）照面。即将和帅在同一直线上。2、马对将（帅）的攻击。（注意马有蹩脚）3、车对将（帅）的攻击。4、炮对将（帅）的攻击。（注意炮要隔一子）5、过河兵对将（帅）的攻击。
输入：输入的第一行为一个正整数n(1<=n<=100)。表示有n个测试局面。接下来的n次测试，每次输入10行，每行输入9个特定正整数，用来表示一个局面（上黑下红）。其中数字0表示该处无棋子，其他数字具体表示如下：黑方：将(1)、士(2,3)、象(4,5)、马(6,7)、车(8,9)、炮(10,11)、卒(12,13,14,15,16)红方：帅(17)、仕(18,19)、相(20,21)、马(22,23)、车(24,25)、炮(26,27)、兵(28,29,30,31,32)提示：样例中的第一组数据表示的是初始局面，第二组数据表示的是图一的局面。
输出：如果存在将军局面，则输出"yes"。反之，输出"no"。
样例输入
2
8 6 4 2 1 3 5 7 9
0 0 0 0 0 0 0 0 0
0 10 0 0 0 0 0 11 0
12 0 13 0 14 0 15 0 16
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
28 0 29 0 30 0 31 0 32
0 26 0 0 0 0 0 27 0
0 0 0 0 0 0 0 0 0
24 22 20 18 17 19 21 23 25
8 6 4 2 1 3 5 0 9
0 0 0 0 0 0 0 0 0
0 10 0 0 0 0 7 11 0
12 0 13 0 14 0 15 0 16
0 0 0 0 0 0 0 0 0
0 0 0 0 27 0 0 0 0
28 0 29 0 30 0 31 0 32
0 26 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
24 22 20 18 17 19 21 23 25
样例输出
no
yes
Error Curves
时间限制：3000 ms | 内存限制：65535 KB
描述 Josephina is a clever girl and addicted to Machine Learning recently. Shepays much attention to a method called Linear Discriminant Analysis, whichhas many interesting properties.In order to test the algorithm's efficiency, she collects many datasets.What's more, each data is divided into two parts: training data and testdata. She gets the parameters of the model on training data and test themodel on test data. To her surprise, she finds each dataset's test error curve is just a parabolic curve. A parabolic curve corresponds to a quadratic function. In mathematics, a quadratic function is a polynomial function of the form f(x) = ax2 + bx + c. The quadratic will degrade to linear function if a = 0.
It's very easy to calculate the minimal error if there is only one test error curve. However, there are several datasets, which means Josephina will obtain many parabolic curves. Josephina wants to get the tuned parameters that make the best performance on all datasets. So she should take all error curves into account, i.e., she has to deal with many quadric functions and make a new error definition to represent the total error. Now, she focuses on the following new function's minimum which related to multiple quadric functions. The new function F(x) is defined as follows: F(x) = max(Si(x)), i = 1...n. The domain of x is [0, 1000]. Si(x) is a quadric function. Josephina wonders the minimum of F(x). Unfortunately, it's too hard for her to solve this problem. As a super programmer, can you help her?
输入：The input contains multiple test cases. The first line is the number of cases T (T < 100). Each case begins with a number n (n ≤ 10000). Following n lines, each line contains three integers a (0 ≤ a ≤ 100), b (|b| ≤ 5000), c (|c| ≤ 5000), which mean the corresponding coefficients of a quadratic function.
输出：For each test case, output the answer in a line. Round to 3 digits after the decimal point.
样例输入
2
1
2 0 0
2
2 0 0
2 -4 2
样例输出
0.000
0.500
Yougth's Game[II]
时间限制：2000 ms | 内存限制：65535 KB
描述 ：NYIST的Yougth最近发明了一种游戏机，推广到了市场，受到了很大的反响，很多人沉迷其中不能自拔，于是这种游戏机被迫停产了。
游戏规则是这样的，由游戏双方各自说一个数x和y，然后游戏机随机生成n个数，然后两个人开始玩游戏，两个人对他们各自说的数x和y以及x*y任一个选择减去游戏机生成的数列中任一数，然后直到三个数都变为0（注意不能把任何数变为负数），某一方无法操作了，那么他就输了。
后来瑶瑶大牛发现了游戏机的奥秘，他发现游戏机总是能够根据游戏双方说出的数控制游戏机生成相应的数，然后控制游戏的输家和赢家，Yougth找到瑶瑶要跟他大战一场，当然是用游戏来决斗，现在给出游戏机生成的数，以及瑶瑶和Yougth说的数，让你判断他们的输赢，已知瑶瑶总是先手，他们可都是聪明人，如果Yougth赢了输出“Yougth is best”,瑶瑶赢的话输出“No”。
输入：输入包括多组数据首先第一行两个数x和y，第二行首先一个n，接着后面n个数（所有数据均小于100且合法）。
输出：如果Yougth赢了输出“Yougth is best”,瑶瑶赢的话输出“No”。
样例输入
2 3
1 1
3 5
2 1 2
样例输出
No
Yougth is best
阶乘末尾非0
时间限制：2000 ms | 内存限制：65535 KB
描述：我们的问题很是简单，n！末尾非0数是几？比如n=5的时候，n！=120，那么n！末尾非0数是2.
输入：多组数据，每组数据占一行，每行一个整数0<=n<=10^1000
输出：n!末尾非0数。
样例输入
5
样例输出
2
yes, master ghost! (I)
时间限制：1000 ms | 内存限制：65535 KB
描述：Recently, edward is reading a novel
The story is about a poor guy possessed by a ghost, and became a magician under the ghost's teaching, fighting against the evil and save the world finally.
This time, the human ghost team is going to dig a boss's grave, the lord of the ghosts' grave. It's not a easy thing. As we all know, ancient Chinese thinks that the grave is the home after human dead. So the boss's grave was built as an underground palace is not even strange. What's more, this grave was protected by misters, ghosts, gears, etc.
Now they faced the door after a long time journey but they can't open it. Lucky the ghost used her special eyes found that they are standing on a big map which marked with two color, white and black. The map consists of a lot of cell. Each cell is a square marked with white or black. So the map is a big rectangle actually. They both believe that the way to open the door is to find some row which use those row can make up a new rectangle that every column has only one white cell, because every thing has it's own balance, like Tai Chi.
To save the world, let's give them a hand. Write a program to find the new rectangle.
输入：multible testevery test start with two integer C and R which describing the map(1<=C,R<=30)then C*R integer is the map1 means white0 means black
输出：output the new rectangle(Guaranteed at only one available answer)
样例输入
6 7
0 0 1 0 1 1 0
1 0 0 1 0 0 1
0 1 1 0 0 1 0
1 0 0 1 0 0 0
0 1 0 0 0 0 1
0 0 0 1 1 0 1
样例输出
0 0 1 0 1 1 0
1 0 0 1 0 0 0
0 1 0 0 0 0 1
合并游戏
时间限制：1000 ms | 内存限制：65535 KB
描述 ：大家都知道Yougth除了热爱编程之外，他还有一个爱好就是喜欢玩。
某天在河边玩耍的时候，他发现了一种神奇的石子，当把两个石子放在一起的时候，后一个石子会消失，而且会蹦出一定数量的金币，这可乐坏了Yougth，但是他想得到最多的金币，他该怎么做?
输入：首先一行，一个n（1<=n<=10），表示有n个石子。接下来n*n的一个矩阵，Aij表示第i个和第j个合并蹦出的金币值(小于10000，注意合并后j会消失)。
输出：输出最多能得到的金币值。
样例输入
2
0 4
1 0
3
0 20 1
12 0 1
1 10 0
样例输出
4
22
yes, master ghost! (III)
时间限制：1000 ms | 内存限制：65535 KB
描述：After they fixed the water pipes,they are going to use those water pipes to get out of this hell. But when one of them touch the water, he feel his blood is sucking by the water and shout "help". Luckily, this guy doesn't die. However, they have to find a way to get out. A magician say, it's not water, it's a kind of monster, like slime. A warlock say, "I have a spell, we can suck the monsters' blood back. But if the blood you got is smaller than you lost, you maybe die!". A paladin say,"Don't warry about this, I can keep you alive, and let those monster lose their ability at the same time. ". "How powerful magic!"someone say. "Infact, this magic is a camouflage. Monsters suck my mana instead of your blood." the paladin keep saying.
Luckly, the warlock has figured out how much blood will lose and get if pass through one pipe(no mater how many people), and every pipe's cost is different. After deliberation, they decide draw apart so that they can get maximum of monsters' blood(because it's pricious) while using the minimum of the paladin's mana.(Guaranteed that they have enough man which means they can visit every pipe)
Imagine that all those pipes consist a net, and our mission is find a way to from point A to point B. Of cause we need cost smallest mana of paladin and get the blood of monsters as much as we can.
输入：multiple test.the first line has two integers N and M(1<=N<=300,1<=M<=1000)fowoll M lines,every line has four integers,pa,pb,m,b. Which means from point pa to point pb will cost m mana of paladin and get b blood of the monster.last line has two integers S and E. Which means they are at point S, and they want to go to point E.
输出：output the maximum of the blood while using the minimum of the mana.
样例输入
5 7
1 3 3 5
1 3 4 3
1 4 2 3
2 3 1 6
3 5 4 3
4 5 5 2
2 5 3 3
1 5
5 7
1 2 2 1
1 3 1 3
2 3 3 2
2 4 6 5
3 4 2 1
3 5 3 1
4 5 4 3
1 5
样例输出
34
12
本文来源：https://www.2haoxitong.net/k/doc/27f26337e45c3b3566ec8b1e.html
文档为doc格式