UVa 246

题意

有一叠52张的扑克牌(除去大王小王), 每次在总叠堆里拿出最上面的一张, 分别放在1-7叠堆的最下面. 如果放下这张牌之后, 小叠堆的最上面2张+最下面1张 / 最上面2张+最下面1张 / 最下面3张 的和为10或20或30, 则将这三张牌抽出来并放到总叠堆的最下面. 如果抽出这三张牌之后, 该小叠堆没有排了, 那么这个叠堆消失, 所有右面序列的叠堆左移.

求这个游戏是win(小叠堆全部消失) / loss(总叠堆无牌) / draw(陷入死循环, 游戏不可能结束) ? 并求出游戏次数

思路

双端队列模拟

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
#include <vector>
#include <set>

using namespace std;

#define mst(a) memset(a, 0, sizeof(a));

deque<int> q[8];
typedef deque<int> Dque;
set<vector<Dque> > G;
bool ok[10];
int hp;

void clear_piles()
{
    for( int k = 0; k < 8; k++ )
        while( !q[k].empty() )
            q[k].pop_back();
    mst(ok);
    G.clear();
}

bool judge( int a, int b, int c )   //判断是否为10/20/30
{
    if( (a+b+c) % 10 == 0 ){
        q[7].push_back(a), q[7].push_back(b), q[7].push_back(c);
        return true;
    }
    return false;
}

bool check( int k ){ //选择三张牌
    int l = q[k].size();
    if( l < 3 ) return 0;
    int a = q[k].front(); q[k].pop_front();
    int b = q[k].front(); q[k].pop_front();
    int c = q[k].back(); q[k].pop_back();
    if( judge(a, b, c) )    return true;
    else q[k].push_front(b);
    b = q[k].back(); q[k].pop_back();
    if( judge(a, b, c) )    return true;
    else q[k].push_front(a);
    a = q[k].back(); q[k].pop_back();
    if( judge(a, b, c) )    return true;
    q[k].push_back(a), q[k].push_back(b), q[k].push_back(c);
    return false;
}

void playing(int k){
    int temp = q[7].front();
    q[7].pop_front();
    q[k].push_back(temp);
    while( check(k) );
    if( q[k].empty() ){
        ok[k] = true;
        hp++;
    }
}

bool is_draw(){
    vector<deque<int> > que;
    for( int i = 0; i < 8; i++ )
        que.push_back(q[i]);
    if( G.count(que) )  return true;
    G.insert(que);
    return false;
}

int main()
{
    int n, cnt;
    bool win, los, daw;
    while( scanf("%d",&n) && n ){
        clear_piles();
        hp = 0, cnt = 0;
        win = false, los = false, daw = false;
        q[7].push_back(n);
        for(int i = 0; i < 51; i++){ scanf("%d",&n);  q[7].push_back(n); }
        int k = 0;
        while(!daw){
            if( hp == 7 )  { win = true; break; }
            if( q[7].empty() )  { los = true; break; }
            k = (k+1)%7;    //循环取0-6
            //cout << k << endl;
            if(ok[k]) continue;
            playing(k);
            ++cnt;
            if( is_draw() ) { daw = true; break;++cnt; }
        }
        if( win ) printf("Win : ");
        else if( los ) printf("Loss: ");
        else if( daw ) printf("Draw: ");
        printf("%d
",cnt);
    }
    return 0;
}