首页 > 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. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

  2. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

  3. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

  4. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

  5. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

  6. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

  7. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

  8. 如果个个像你这么爱现个个上传张玉照,煎蛋有几千人的话,无聊图就一百页被废了,有几万人的话,一千页被废了,别带头做这样的傻事啊你们,尤其长得又不怎么样,照片也不大气上档次,拿来现会多少有些丢人那种就更是损人害已

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

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

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