[HDU3031]To Be Or Not To Be(可并堆,左偏树)

发布于 2018-02-18  102 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU3031]To Be Or Not To Be(可并堆,左偏树)

Description

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.
HDU3031-1
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.

Http

HDU

Tag

可并堆,左偏树

题目大意

若干轮,每一轮给出\(n\)张特殊卡牌和\(m\)堆分值卡牌。两人轮流操作,每一次从特殊卡牌中抽出一张,使用完后丢弃。特殊卡牌有一下几种
\(Challenge-card\),不管是谁抽到这一张,将两人分别数值最大的卡牌比较,分值大的一方获得另一方的所有卡牌。
\(Loss-card\),抽到这一张卡牌的人要弃掉他分值最大的卡牌。
\(Add-card\),抽到这一张卡牌的人将他分值最大的卡牌加上\(Add-card\)上对应的数值。
\(Exchange-card\),抽到这一张卡牌的人将他分值最大的卡牌的分值变成\(Exchange-card\)上对应的分值。
\(Take-card\),抽到这一张卡牌的人获得\(Take-card\)上数值对应的第几堆分值卡牌。
每一轮后,统计两人手中有的分值卡牌的个数,多的人得一分。
最后得分高的人胜。

解决思路

看到所有的卡牌操作,发现所有的操作都与取\(max\)有关,那么就想到用堆来维护两人分别的手牌。由于涉及到合并操作,那么就可以用可并堆来实现合并操作。
有部分细节需要注意。
这里使用左偏树实现可并堆。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100*10000+100;
const int inf=2147483647;

class Heap
{
public:
    int key;
    int ls,rs,dis;
    void init(){
            ls=rs=dis=0;return;
        }
};

int R;
int n,m,Pile[maxN],Pnum[maxN];//Pile维护第i堆分值卡牌对应在可并堆中的堆顶,Pnum维护第i堆分值卡牌中卡牌的数量。
Heap H[maxN];//左偏树

int Merge(int r1,int r2);

int main()
{
    ios::sync_with_stdio(false);
    while (cin>>R)
    {
        int hap=0,wof=0;//统计两人的得分
        while (R--)
        {
            int nodecnt=0;mem(Pile,0);
            cin>>n>>m;
            for (int i=1;i<=m;i++) cin>>Pnum[i];//输入,并把每一堆初始分值卡牌构造成堆的形式
            for (int i=1;i<=m;i++)
                for (int j=1;j<=Pnum[i];j++)
                {
                    ++nodecnt;H[nodecnt].init();
                    cin>>H[nodecnt].key;
                    Pile[i]=Merge(Pile[i],nodecnt);
                }
            int Id[3];Id[1]=Id[2]=0;//记录两个人当前手中牌的堆顶
            int Size[3];Size[1]=Size[2]=0;//记录两人手中当前牌的数量
            for (int now=1;now<=n;now++)
            {
                int pl=(now-1)%2+1;//当前操作的人
                char opt;cin>>opt;
                if (opt=='T')//Take-card
                {
                    int kth;cin>>kth;
                    Id[pl]=Merge(Id[pl],Pile[kth]);
                    Size[pl]+=Pnum[kth];
                }
                if (opt=='C')//Challenge-card
                {
                    if (H[Id[2]].key>H[Id[1]].key){
                        Id[2]=Merge(Id[1],Id[2]);Id[1]=0;
                        Size[2]+=Size[1];Size[1]=0;
                    }
                    else if (H[Id[1]].key>H[Id[2]].key){
                        Id[1]=Merge(Id[1],Id[2]);Id[2]=0;
                        Size[1]+=Size[2];Size[2]=0;
                    }
                }
                if (opt=='L'){//Lost-card
                    Id[pl]=Merge(H[Id[pl]].ls,H[Id[pl]].rs);Size[pl]--;
                }
                if (opt=='A'){//Add-card
                    int key;cin>>key;H[Id[pl]].key+=key;
                }
                if (opt=='E')//Exchange-card
                {
                    int key;cin>>key;
                    int id=Id[pl];Id[pl]=Merge(H[Id[pl]].ls,H[Id[pl]].rs);
                    H[id].key=key;Id[pl]=Merge(Id[pl],id);
                }
            }
            printf("%d:%d\n",Size[1],Size[2]);
            if (Size[1]>=Size[2]) wof++;
            else hap++;
        }
        if (wof>hap) printf("Hahaha...I win!!\n");
        else printf("I will be back!!\n");
    }
    return 0;
}

int Merge(int r1,int r2)
{
    if (r1==0) return r2;
    if (r2==0) return r1;
    if (H[r1].key<H[r2].key) swap(r1,r2);
    H[r1].rs=Merge(H[r1].rs,r2);
    if (H[H[r1].ls].dis<H[H[r1].rs].dis) swap(H[r1].ls,H[r1].rs);
    if (H[r1].rs) H[r1].dis=H[H[r1].rs].dis+1;
    else H[r1].dis=0;
    return r1;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU3031]To Be Or Not To Be(可并堆,左偏树)


HNCJ OIer