uva246 10-20-30 （双端队列deque + vector模拟）

【题意】：

一个游戏。共52张牌（1~10中的数字）。

初始状态，按输入顺序放在 总堆里。然后从头开始，挨着拿7张，从左到右摆开，作为7堆。

然后回到第一堆，以此循环着每次往一堆放一张。

每放完一张牌，考虑下面的情况：

1. 这一堆的头两张与尾一张之和等于10 or 20 or 30

2. 这一堆的头一张与尾两张之和等于10 or 20 or 30

3. 这一堆的尾三张之和等于10 or 20 or 30

若满足其中一个情况，则从这堆里取出这三张牌，放到总堆的尾部（注意要不改变这三张牌的头尾顺序）。

多个情况满足时，优先考虑前面的。

当某一堆恰好某一次取牌被取空了，则这一堆将永久被遗忘，不再往上发牌。

问：最后的状态。若7个堆都空了，则Win

若总堆空了，则Loss

若陷入了无限循环，则为Draw

然后输出步数。

【分析】

视一个状态为：7个堆+1个总堆。若某此操作后，状态在以前就出现过了，就表示陷入循环了。用

set维护这个状态。

这个状态用vector维护，每一个堆用一个双端队列deque维护。即：vector<deque<int> > dui;

模拟即可。

【代码】：

#include<bits/stdc++.h>
using namespace std;

int isten(int x)
{
    return x==10 || x==20 || x==30;
}

int check1(deque<int>piple) //头2+尾1
{
    int sum=0;
    sum+=piple.front(); piple.pop_front();
    sum+=piple.front(); piple.pop_front();
    sum+=piple.back(); piple.pop_back();
    return isten(sum);
}

int check2(deque<int>piple) //头1+尾2
{
    int sum=0;
    sum+=piple.front(); piple.pop_front();
    sum+=piple.back(); piple.pop_back();
    sum+=piple.back(); piple.pop_back();
    return isten(sum);
}

int check3(deque<int>piple) //尾3
{
    int sum=0;
    sum+=piple.back(); piple.pop_back();
    sum+=piple.back(); piple.pop_back();
    sum+=piple.back(); piple.pop_back();
    return isten(sum);
}

int putit(deque<int>&piple, deque<int>&all) //试图拿piple这堆,按从头到尾顺序，拿到总堆
{
    if(piple.size()<3)return 0;
    if(check1(piple))
    {
        int s1=piple.front(); piple.pop_front();
        int s2=piple.front(); piple.pop_front();
        int s3=piple.back(); piple.pop_back();
        all.push_back(s1);
        all.push_back(s2);
        all.push_back(s3);
        return 1;
    }
    else if(check2(piple))
    {
        int s1=piple.front(); piple.pop_front();
        int s2=piple.back(); piple.pop_back();
        int s3=piple.back(); piple.pop_back();
        all.push_back(s1);
        all.push_back(s3);
        all.push_back(s2);
        return 1;
    }
    else if(check3(piple))
    {
        int s1=piple.back(); piple.pop_back();
        int s2=piple.back(); piple.pop_back();
        int s3=piple.back(); piple.pop_back();
        all.push_back(s3);
        all.push_back(s2);
        all.push_back(s1);
        return 1;
    }
    return 0;
}
void output(vector<deque<int> > dui,deque<int> all)
{
    while(!all.empty()) {cout<<all.front()<<" ";all.pop_front();}cout<<endl;
    for(int i=0;i<7;i++)
    {
        cout<<i<<" : ";
        while(!dui[i].empty()){cout<<dui[i].front()<<" ";dui[i].pop_front();}cout<<endl;
    }
}
int main()
{
    vector<deque<int> > dui;
    int a[52];
    set< vector<deque<int> > > status; //8个堆的状态
    for(int i=0;i<8;i++) dui.push_back(deque<int>()); //初始8堆
    deque<int> &all=dui[7];
    while(scanf("%d",&a[0])!=EOF&&a[0])
    {
        all.clear();
        status.clear();
        for(int i=1;i<52;i++) scanf("%d",&a[i]);
        for(int i=0;i<52;i++) all.push_back(a[i]); //放入总堆
        for(int i=0;i<7;i++)
        {
            int num=all.front();
            all.pop_front();
            dui[i].clear();
            dui[i].push_back(num);
        }
        int ans=7;
        int point=0; //指向牌堆
        while(1)
        {
            ans++;
            int num=all.front(); all.pop_front();
            dui[point].push_back(num); //point堆的尾部放上一张num
            while(putit(dui[point],all));
            //cout<<"step: "<<ans<<endl;
            //output(dui,all);
            if(status.count(dui))
            {
                printf("Draw: %d\n",ans);
                break;
            }
            status.insert(dui);
            if(all.size()==0)
            {
                printf("Loss: %d\n",ans);
                break;
            }
            if(all.size()==52)
            {
                printf("Win : %d\n",ans);
                break;
            }

            do{
                point=(point+1)%7;
            }while(dui[point].size()==0);
        }
    }
    return 0;
}
/*
1 7 5 9 7 3 10 7 2 2 3 1 1 5 2 9 10 10
 1 1 4 5 8 8 9 4 8 10 6 3 5 4 7 1 7 9 10
 2 9 8 7 5 6 2 4 5 4 6 8 5 9 6

 Win : 207
*/