首页 > ACM题库 > HDU-杭电 > hdu 3566 Counting Heads待解决[解题报告]C++
2014
11-05

hdu 3566 Counting Heads待解决[解题报告]C++

Counting Heads

问题描述 :

Notice: If you are an honest guy and don’t want to help the host, you can do another problem, but you cannot get the "AC".

The world wide game of counting heads is around the corner. Now the qualifier is feverishly on show. Those who pass the qualifier will have the chance to advance to the final, and may win the Super King of Counting Heads! The qualifier has two rounds, and N players will participate in it. The scores for player i in Round 1 and Round 2 are xi and yi respectively. The host will select one of a player’s scores as his final result. If a player’s score in Round 1(or Round 2) is selected as his final result, he will be involved in the rank of Round 1(or Round 2). The first g players involved in Round 1(and Round 2) will advance to the final. Two Rounds rank scores separately from high to low. If less than g players are involved in the rank of Round 1(or Round 2), all of them advance.

Every country hopes his players can win the title, especially the host country. How can the host select the scores so as to maximize the number of native final players according to the rules?

输入:

The first line is an integer T (T <= 200), representing the number of test cases.

In each test case, two integers N (2 <= N <= 200), g (0 <= g <= N / 2) come in the first line. N is the number of players competing in the qualifications, g is the advancing limit. Then come N lines. In each following line, there are three integers x, y, f (0 <= x, y < 10000), representing the scores of Round 1 and Round 2. If f is 1, then this is native, 0 otherwise.

(It’s guaranteed that there are no two same score in one round)

输出:

The first line is an integer T (T <= 200), representing the number of test cases.

In each test case, two integers N (2 <= N <= 200), g (0 <= g <= N / 2) come in the first line. N is the number of players competing in the qualifications, g is the advancing limit. Then come N lines. In each following line, there are three integers x, y, f (0 <= x, y < 10000), representing the scores of Round 1 and Round 2. If f is 1, then this is native, 0 otherwise.

(It’s guaranteed that there are no two same score in one round)

样例输入:

2
2 1
1 2 0
2 1 1
8 3
6 7 0
5 8 0
4 5 1
7 4 0
8 2 1
3 3 0
1 1 1
2 6 1

样例输出:

Case 1: 1
Case 2: 4

Hint
For the 5th, 7th, 8th players, you can select their score of Round 1 as their final result. Others select their score of Round 2 as their final result. Then you can let four host players pass the qualifier.


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept