首页 > ACM题库 > HDU-杭电 > HDU 3031-To Be Or Not To Be[解题报告]HOJ
2014
02-27

HDU 3031-To Be Or Not To Be[解题报告]HOJ

To Be Or Not To Be

问题描述 :

That’s a question. Now Happy (Xi Yangyang) has been caught by Wolffy (Hui Tailang). As Wolffy is busy preparing the big meal, a good idea comes to Happy. He proposes a game that only Wolffy had won, he can eat Happy. Wolffy always believes he is the cleverest one, so they reach a consensus. And they both agree with Wolnie (Hong Tailang) when the referee. A theater will be beat to die by Wolnie’s pan.
 Increasing Speed Limits

The game is defined as follow.

There are multiple test cases.

In each case there are R (R < 10) rounds of the game, R is an odd number to guarantee that there must be a winner in the end.

In each round: There is a pile of n (10 <= n <= 200) Special-cards and m (1 <= m <= 100) piles of Point-card on the table. The Point-card piles are ordered from 1 to m. Wolffy and Happy take turns to get one card from the top of Special-cards pile. Wolffy always takes first in the game. When all the Special-cards have been taken, the round is over and the one with more cards in the hands gains one point. If there is a tie, Wolffy gains one point.(Wolffty and Happy both have 0 point before the game).

There are 5 kinds of Special-cards besides the Point-card in the game.

0) Point-card: a card with a point X (1 <= X <= 2000000).

1) Challenge-card: no matter who takes this card, they both take one card with the maximum point from their own hands. After a comparison, if Happy’s card has a larger point, He takes all the Wolffy’s in-hands cards, vice versa; If there is a tie no more operation.

2) Loss-card: the one who takes this card, He must throw a card with the maximum point.

3) Add-card: a card with P point, the one who gets this card will make the card with maximum point P point larger, i.e. if a Point-card with X point is the maximum, its point will change to X + P. An Add-card can only work on one Point-card.

4) Exchange-card: a card with Q point. The one who gets this card must change one maximum-point card’s point to Q.

5) Take-card: a card with a integer K, indicates one can get the all the cards of Kth Point-card pile. In one round no two Take-card have the same K.

You can assume that when one gets the Loss-card, Add-card, Exchange-card, He has at least one card in the hands, when one gets a Challenge-card, they both have at least one card in the hands.

输入:

Input

For each test case, the first line of input is an integer R, indicates the number of rounds:

Line 2: two integers n indicates the number of Special-cards, m indicates the number of Point-card piles.

Line 3: a line of m integers. The ith number Pi (1 <= Pi <= 10000)indicates the number cards of ith Point-card pile.

For the next m lines, ith line contains Pi numbers indicate every Point-card’s point of ith Point-card pile.

The next n lines, in each line, there are five kinds of input, indicate Special-cards by the order of "from top to bottom".

1) T K: indicates one gets a Take-card, and He can get Kth Point-card pile(1 <= K <= m).

2) C: indicates one gets a Challenge card.

3) L: indicates one gets a Loss card.

4) A P: indicates one gets an Add card with P point (1 <= P <= 30).

5) E Q: indicates one gets an Exchange card with Q point (1 <= Q <= 2000000).

输出:

Input

For each test case, the first line of input is an integer R, indicates the number of rounds:

Line 2: two integers n indicates the number of Special-cards, m indicates the number of Point-card piles.

Line 3: a line of m integers. The ith number Pi (1 <= Pi <= 10000)indicates the number cards of ith Point-card pile.

For the next m lines, ith line contains Pi numbers indicate every Point-card’s point of ith Point-card pile.

The next n lines, in each line, there are five kinds of input, indicate Special-cards by the order of "from top to bottom".

1) T K: indicates one gets a Take-card, and He can get Kth Point-card pile(1 <= K <= m).

2) C: indicates one gets a Challenge card.

3) L: indicates one gets a Loss card.

4) A P: indicates one gets an Add card with P point (1 <= P <= 30).

5) E Q: indicates one gets an Exchange card with Q point (1 <= Q <= 2000000).

样例输入:

3
5 3
3 3 3
10 11 2
7 4 12
4 2 9
T 1
T 2
A 7
T 3
C
6 3
2 2 2
1 4
5 2
4 2
T 2
T 1
L
A 2
T 3
C
5 3
2 2 2
1 3
4 2
5 2
T 2
T 1
E 3
A 1
L

样例输出:

9:0
0:5
1:2
I will be back!!

#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct sd
{
 int dian;
 friend bool operator<(sd a,sd b)
 {
 return a.dian<b.dian;
 }
};
int card[210][1509];
int carnum[1000];
vector<int >pile[180];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
 int cas;
 // freopen("e://b.txt","r",stdin );
 while(scanf("%d",&cas)!=EOF)
 {
 	
 int totw=0,toth=0;
 while(cas--)
 {priority_queue<sd>hap;
			priority_queue<sd>wof;
			int sumh=0,sumw=0;
 int sp,po;
 sd kkk,a,b;
 scanf("%d%d",&sp,&po);
 for(int i=1;i<=po;i++)
 {scanf("%d",&carnum[i]);
 pile[i].clear();
 }
 for(int i=1;i<=po;i++)
 {for(int j=0;j<carnum[i];j++)
 {	
 scanf("%d",&card[i][j]);
 // pile[i].push_back(card);
 }
 }
 int h=0,w=1;
 char dir[2];
 vector<int >::iterator it;
 for(int i=0;i<sp;i++)
 {
 scanf("%s",&dir);
 if(dir[0]=='T'){
 int pi;
 scanf("%d",&pi);
 if(h==1){
					sumh+=carnum[pi];
					int j=0;
 	while(!hap.empty())
 		{
 			kkk=hap.top();
 		//	pile[pi].push_back(kkk.dian);
 				card[pi][carnum[pi]+j]=kkk.dian;
								hap.pop();
 		}
 	//	sort(pile[pi].begin(),pile[pi].end(),cmp);
 	sort(card[pi],card[pi]+carnum[pi]+j,cmp);
 //for(it=pile[pi].begin();it!=pile[pi].end();it++)
 		for(int t=0;t<min(sp-i,carnum[pi]+j);t++)
 {
 kkk.dian=card[pi][t];
 hap.push(kkk);
 }
 }
 else {
 	sumw+=carnum[pi];
 	int j=0;
						while(!wof.empty())
						{
							kkk=wof.top();
							//pile[pi].push_back(kkk.dian);
							card[pi][carnum[pi]+j]=kkk.dian;
							wof.pop();
							j++;
						}
							sort(card[pi],card[pi]+carnum[pi]+j,cmp);
						//sort(pile[pi].begin(),pile[pi].end(),cmp);
							//for(it=pile[pi].begin();it!=pile[pi].end();it++)
							for(int k=0;k<min(sp-i,carnum[pi]+j);k++)
		 { kkk.dian=card[pi][k];
		 wof.push(kkk);
		 }
 }
 }
 else if(dir[0]=='C'){
 a=wof.top();
 b=hap.top();
 if(a.dian>b.dian)
 {
 	
 	sumw+=sumh;
						sumh=0;
 while(!hap.empty())
 {
 kkk=hap.top();
 wof.push(kkk);
 hap.pop();
 }
 }
 else {
 	sumh+=sumw;
 	sumw=0;
 while(!wof.empty())
 {
 kkk=wof.top();
 hap.push(kkk);
 wof.pop();
 }
 }
 }
 else if(dir[0]=='L'){
 if(h==1)
 {hap.pop();
 sumh--;
 }
 	else {
 			sumw--;
								wof.pop();}
 }
 else if(dir[0]=='A'){
 int num;
 scanf("%d",&num);
 if(h==1){
 a =hap.top();
 hap.pop();
 a.dian+=num;
 hap.push(a);
 }
 else {
 a=wof.top();
 wof.pop();
 a.dian+=num;
 wof.push(a);
 }
 }
 else if(dir[0]=='E'){
 int q;
 scanf("%d",&q);
 if(h==1){
 hap.pop();
 a.dian=q;
 hap.push(a);
 }
 else {
 wof.pop();
 a.dian=q;
 wof.push(a);
 }
 }
 h=1-h;
 w=1-w;
 }
 printf("%d:%d\n",sumw,sumh);
 if(sumh>sumw)
 toth++;
 else totw++;
 }
 if(toth<totw)
 printf("Hahaha...I win!!\n");
 else printf("I will be back!!\n");
 }
 return 0;
}

  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的边不是都没了吗?