首页 > ACM题库 > HDU-杭电 > hdu 2900 Song contest待解决[解题报告]C++
2014
02-21

hdu 2900 Song contest待解决[解题报告]C++

Song contest

问题描述 :

Every year, the continent of Cacophonea organises the Cacophonean Song Contest, for which each of its nations presents an act by a national singer or group. Each Cacophonean inhabitant may televote for any act which is not from his nation, so a nation can never vote for its own act. In the end, each of the s Cacophonean nations will award points to r acts. The act which received most votes from a certain nation will get r points from this nation, the act with the second largest amount of votes will get r – 1 points, etc., so the act with the rth largest amount of votes gets 1 point and less popular acts get no points from the voting nation. The final ranking of the song-contest will then be decided by the total amount of points each nation received.

Music producer Dustin has been eagerly following the Cacophonean Song Contest for many years. Lately, he has observed that in certain nations, televotes are politically rather than artisti-cally motivated:

Politically voting nations prefer acts from neighbouring nations. More speci cally, the Eu-clidean distance between their capital and another nation’s capital is their popularity measure, irregardless of the artistic quality of the corresponding act. Hence, the nation with the closest capital will get most votes and the nation with the farthest capital will receive the least votes, which could yield no points at all if r < s -1. It will never occur that two or more capitals will have the same distance to a certain capital.

Nations that vote quality-motivated will, as the name suggests, award points to nations according to an indisputable act ranking based on each act’s artistic quality. In this ranking,there will be no ties so each nation has its own unique rank.

However, Dustin has heard he can in uence the voting behaviour of other nations: an artist can find favour of politically voting nations by giving them special attention during his act (e.g. by singing parts in their local dialects, waving their ags, etcetera). The more a politically voting nation will receive such attention in an act, the higher it will rank it. Of course this will be at the cost of the original act and might result in terribly campy results. Therefore, nations that vote according to artistic quality will punish such behaviour.

More speci cally, Dustin can divide an act into exactly s – 1 parts. Originally, all parts are dedicated to the nation of the performer (i.e. they re ect his original artistic ideas), but this can be changed:

For each part in the act that will be dedicated to a certain politically voting nation, that nation will rank the performer’s nation one place higher (unless the performer’s nation is already ranked rst). As each nation has a unique ranking position, the nation that originally was at that higher rank will then be ranked one place lower.

Quality-motivated voting nations do not like these soft-soaping attempts at all. Therefore, for each part in the act that will be dedicated to a nation which is not the original performer’s nation, quality-motivated nations will rank the original performer’s nation one place lower (unless the performer’s nation is already ranked lowest).

Only the fact that a certain amount of parts is dedicated to a certain nation will in uence voting behaviour: the exact part dedication sequence in the total act is not of interest here.

Dustin wants to use this knowledge (which no other Cacophonean producer has) to produce asmashing act, yielding as much points in the overall results as possible. You are asked to determine what the largest possible overall point score is he can obtain for an act, when he optimally exploits the described act-changing practices.

输入:

The rst line of input consists of the integer number n, the number of test cases;

Then, for each test case:

A line with an integer number s (1 < s <= 100), indicating the number of participating nations in the song contest;

Then, for each nation:

A line containing:A string c (not containing any spaces) with the nation’s name, followed by a space. Within a test case, there will not be multiple nations sharing the same name ;

A character indicating the nation’s voting behaviour: ‘q’ if the voting behaviour is quality-motivated and ‘p’ if the behaviour is politically motivated.

A line containing:

The location of the nation’s capital, expressed in an (x, y) integer coordinate(-10000 <=x <= 10000, -10000 <= y <= 10000). x and y are separated by a space. Furthermore, y is followed by a space;

The actual artistic quality rank q of the nation’s act. This is a unique number-in the range 1 ….. s.

A line with an integer number r (0 < r <= s – 1), indicating to how many nations each nation will attribute points;
A line with the name of the nation for which Dustin should produce a song, achieving as much points as possible.

输出:

The rst line of input consists of the integer number n, the number of test cases;

Then, for each test case:

A line with an integer number s (1 < s <= 100), indicating the number of participating nations in the song contest;

Then, for each nation:

A line containing:A string c (not containing any spaces) with the nation’s name, followed by a space. Within a test case, there will not be multiple nations sharing the same name ;

A character indicating the nation’s voting behaviour: ‘q’ if the voting behaviour is quality-motivated and ‘p’ if the behaviour is politically motivated.

A line containing:

The location of the nation’s capital, expressed in an (x, y) integer coordinate(-10000 <=x <= 10000, -10000 <= y <= 10000). x and y are separated by a space. Furthermore, y is followed by a space;

The actual artistic quality rank q of the nation’s act. This is a unique number-in the range 1 ….. s.

A line with an integer number r (0 < r <= s – 1), indicating to how many nations each nation will attribute points;
A line with the name of the nation for which Dustin should produce a song, achieving as much points as possible.

样例输入:

2
3
Aulatrias q
0 0 1
Binen q
5 0 2
Cahin q
0 -4 3
2
Cahin
3
Aulatrias p
0 0 1
Binen p
5 0 2
Cahin p
0 -4 3
2
Binen

样例输出:

2
4


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  4. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n