首页 > ACM题库 > HDU-杭电 > hdu 2331 Soccer Tournament-高精度-[解题报告]hoj
2014
01-05

hdu 2331 Soccer Tournament-高精度-[解题报告]hoj

Soccer Tournament

问题描述 :

ACM decided to run a big advertising campaign. Beside others, it will sponsor soccer tournaments by providing them with a system for computing and displaying game results. You are to write that system.

输入:

The input contains description of several tournaments. Each tournament begins with a line containing single positive integer N: the number of participating teams, N ≤ 80. Then there are N lines, each containing a unique name of one team. The name is case-sensitive and may be composed only from letters, digits, dots (“.”), and dashes (“-”). No name will be longer than 100 characters.

After the team names, there will be a line with a single non-negative integer M: the number of games that have already been played. Each of the next M lines describes one game and contains the host team name, space, dash, space, guest team name, space, and the game result. The result will always appear as a single digit (0-9), colon (“:”), and another single digit (0-9). The digits specify the number of goals scored by the host and guest teams.

Then, the next tournament is described. The last tournament is followed by a zero on a separate line. No output should be produced for this zero.

You may assume that all team names have been listed among the N teams. All games will have distinct opponent pairs. This also means that any two teams may play at most two games with each other ― in such a case, each of the two teams will be a host in one game and a guest in the other.

输出:

The input contains description of several tournaments. Each tournament begins with a line containing single positive integer N: the number of participating teams, N ≤ 80. Then there are N lines, each containing a unique name of one team. The name is case-sensitive and may be composed only from letters, digits, dots (“.”), and dashes (“-”). No name will be longer than 100 characters.

After the team names, there will be a line with a single non-negative integer M: the number of games that have already been played. Each of the next M lines describes one game and contains the host team name, space, dash, space, guest team name, space, and the game result. The result will always appear as a single digit (0-9), colon (“:”), and another single digit (0-9). The digits specify the number of goals scored by the host and guest teams.

Then, the next tournament is described. The last tournament is followed by a zero on a separate line. No output should be produced for this zero.

You may assume that all team names have been listed among the N teams. All games will have distinct opponent pairs. This also means that any two teams may play at most two games with each other ― in such a case, each of the two teams will be a host in one game and a guest in the other.

样例输入:

4
Slavia
Arsenal
Steaua
FCSevilla
4
Slavia - Arsenal 2:0
FCSevilla - Steaua 1:1
Steaua - Slavia 1:2
Arsenal - Slavia 0:0
0

样例输出:

RESULTS:
+---------+---+---+---+---+
|         |Sla|Ars|Ste|FCS|
+---------+---+---+---+---+
|Slavia   | X |2:0|   |   |
+---------+---+---+---+---+
|Arsenal  |0:0| X |   |   |
+---------+---+---+---+---+
|Steaua   |1:2|   | X |   |
+---------+---+---+---+---+
|FCSevilla|   |   |1:1| X |
+---------+---+---+---+---+

STANDINGS:
----------
1. Slavia    3 2 1 0 4:1 7
2. FCSevilla 1 0 1 0 1:1 1
3. Steaua    2 0 1 1 2:3 1
4. Arsenal   2 0 1 1 0:2 1 


今天这题让我想起了数学在计算机中的重要性,一看题意很简单,看一个数能被连续自然数之和的表示形式种类,例如:
6 = 1 + 2 + 3 一种 9 = 5 + 4 = 2 + 3 + 4
二种
最开始我就想到了最笨的方法,一个个试探,想的时候就想到了肯定会超时的,果然写完后
一运行,后面的大数在自己的电脑上不能运行得出结果,TLE——失败。
后来看到可以用数学方法来求解,这时才豁然开朗,真是叫书到用时方恨少啊!!!
数学解法思路
设连续的第一数为i,有j个数。则有(2 * i + j – 1 )* j = 2 * n;
1 有(2 * i + j – 1)> j,则有j < sqrt(2 * n),
(2 * n) / j + j =2 * ( i + j )-1;
最后可将题意转化为若(2 * n)% j==0&& ((2 * n) / j + j )%2 !=0时j的解的个数即为
题中要求的表示形式数。
数学的重要性真是可见一斑了,必须得真正的学好她了。Keep on!!!
解题参考:http://blog.sina.com.cn/s/blog_4d3c631901000c3c.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。