首页 > ACM题库 > HDU-杭电 > hdu 3615 Defense of the Ancients待解决[解题报告]C++
2014
11-27

hdu 3615 Defense of the Ancients待解决[解题报告]C++

Defense of the Ancients

问题描述 :

Defense of the Ancients (commonly known as DotA) is a custom scenario for the real-time strategy video game Warcraft III: Reign of Chaos and its expansion, Warcraft III: The Frozen Throne, based on the "Aeon of Strife" map for StarCraft. The objective of the scenario is for each team to destroy the opponents’ Ancients, heavily guarded structures at opposing corners of the map. Players use powerful units known as heroes, and are assisted by allied heroes and AI-controlled fighters called "creeps". As in role-playing games, players level up their heroes and use gold to buy equipment during the mission.

Defense of the Ancients pits two teams of players against each other: the Sentinel and the Scourge. Players on the Sentinel team are based at the southwest corner of the map, and those on the Scourge team are based at the northeast corner. Each base is defended by towers and waves of units which guard the main paths leading to their base. In the center of each base is the "Ancient", a building that must be destroyed to win the game.

Each human player controls one Hero, a powerful unit with unique abilities. In DotA, players on each side choose one of 101 heroes, each with different abilities and tactical advantages over other heroes. The scenario is highly team-oriented; it is difficult for one player to carry the team to victory alone. Defense of the Ancients allows up to ten players in a five-versus-five format and an additional two slots for referees or observers, often with an equal number of players on each side.

In DotA, each hero has three basic attributes: strength, agility and intellect. One point of strength can give the hero 19 points of life and 0.03 life regen per second; One point of agility increases the hero’s attack speed by 1% and every 7 points of agility increases the hero’s Armor by 1; One point of intellect gives the hero 13 points of mana and 0.03 mana regen per second.

To simplify the problem, we make the following conventions: one points of strength gives a hero S points of fighting ability; one points of agility gives a hero A points of fighting ability; one points of intellect gives a hero I points of fighting ability. S, A and I are fixed but unknown real numbers. A hero with 0 points of the three attributes has 0 points of fighting ability. When two heroes fight with each other, the one has higher fighting ability always win. When two heroes that have equal fighting ability meet, one of them randomly wins.

Burning and AngleLover are both excellent DotA player. Burning is good at using the hero "Shadow Fiend" while AngleLover is famours for his "Rattletrap". They have fight with each other for n times. We knows the result and the attribute value of the two hero in each fight, but we don’t know the exact value of S, A and I. Now given the attribute value of the two hero in other m fights, can you determine who will be the winer?

It is guaranteed that none of S A, and I is more than 100 times as high as another, and none of them are 0.

输入:

In the first line of input file there is a single integer T, means the number of test cases. (1 ≤ T ≤ 10)

For each test case, in the first line there are two integers: n and m as mentioned above (0 ≤ n ≤ 300, 1 ≤ m ≤ 2000). Then there are n+m lines following. From line 2 to line n+1, each line describes a battle in the format:

winner S1 A1 I1 S2 A2 I2

The string winner is either "Burning" or "AngleLover", S1, A1, I1 is the strength value, agility value and intellect value of Burning’s hero respectively. And S2, A2, I2 is the strenght value, agility value and intellect value of AngleLover’s hero respectively.

From line n+2 to line n+m+1, each line describes battles whose result is to be determined in the format:

S1 A1 I1 S2 A2 I2

Each variable’s meaning is the same as the mentioned above.

The value of the attributes are all integers between 0 and 1000 inclusively.

输出:

In the first line of input file there is a single integer T, means the number of test cases. (1 ≤ T ≤ 10)

For each test case, in the first line there are two integers: n and m as mentioned above (0 ≤ n ≤ 300, 1 ≤ m ≤ 2000). Then there are n+m lines following. From line 2 to line n+1, each line describes a battle in the format:

winner S1 A1 I1 S2 A2 I2

The string winner is either "Burning" or "AngleLover", S1, A1, I1 is the strength value, agility value and intellect value of Burning’s hero respectively. And S2, A2, I2 is the strenght value, agility value and intellect value of AngleLover’s hero respectively.

From line n+2 to line n+m+1, each line describes battles whose result is to be determined in the format:

S1 A1 I1 S2 A2 I2

Each variable’s meaning is the same as the mentioned above.

The value of the attributes are all integers between 0 and 1000 inclusively.

样例输入:

1
3 3
Burning 6 5 4 5 4 7
AngleLover 5 4 2 3 5 5
Burning 9 0 10 8 2 7
6 6 4 5 4 7
9 0 10 8 2 6
3 4 8 4 4 6

样例输出:

Burning
Burning
I don't know


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. [email protected]

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。