2014
02-27

# 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.

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;
{
degree[*j]++;
}
}

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