UVa 246 - 10-20-30 | Sengxian's Blog

UVa 246 - 10-20-30

#数据结构 #模拟 #哈希 #双端队列

Published on 2016-01-04

描述

你手上有 $52$ 张牌，给定按顺序给出这些牌的点数（认为 $J = Q = K = 10$ ）。一开始从左到右发出 $7$ 张牌，将这 $7$ 张牌分为 $7$ 堆，继续发牌（从左到右，到了最右边返回最左边）。在发了一张牌之后，如果有

最上面两张和最下面一张。
最上面一张和最下面两张。
最下面三张。

它们的点数之和为 $10$ 、 $20$ 或 $30$ ，就把这三张牌按描述的顺序收进手牌的底部，在判断条件时，依此按顺序 1、2、3 检查。你必须将某一堆牌处理到没有牌能够收进手牌为止。如有一堆牌被完全拿光，则这一堆牌消失，不再往上发牌。最终只可能有三种结果：

win： $7$ 堆牌全部消失。
lose：你的手牌空了。
draw：重复之前出现过的局面，即陷入死循环。

请输出最终的结果以及达到这一结果总共发牌的次数。

样例输入

2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1
10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2
4 3 2 10 8 10 6 8 9 5 8 10 5 3 5 4 6 9 9 1 7 6 3 5 10 10 8 10 9 10 10 7
2 6 10 10 4 10 1 3 10 1 1 10 2 2 10 4 10 7 7 10
10 5 4 3 5 7 10 8 2 3 9 10 8 4 5 1 7 6 7 2 6 9 10 2 3 10 3 4 4 9 10 1 1
10 5 10 10 1 8 10 7 8 10 6 10 10 10 9 6 2 10 10
0

样例输出

Win : 66
Loss: 82
Draw: 73

分析

目测一个大模拟题，决策就那么三种，我们选取数据结构 deque，双端队列来方便我们插牌删牌。很方便的一点就是，deque 重载了 [] 运算符，因此可以直接像数组一样使用，但更安全的做法是直接 .at() ，这样有越界的情况直接报错，容易调试。

主算法模拟下去就行了，关键在于如何判断平局。我这里使用哈希记录每堆牌以及手牌的信息（牌堆之间加分隔符）+ set 来判重，时间空间均不错。哈希中使用 unsigned long long 能够天然溢出，是个不错的选择。

代码

//  Created by Sengxian on 1/4/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 246 模拟 + 哈希判重
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <deque>
#include <set>
using namespace std;
const int maxn = 52, maxp = 7, hashBase = 1007;
deque<int> deck, piles[maxn];
int times;

typedef unsigned long long ull;
set<ull> vis;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return n;
}

inline int firstCard(int i) {
    return piles[i].front();
}
inline int secondCard(int i) {
    return piles[i].at(1);
}
inline int lastCard(int i) {
    return piles[i].back();
}
inline int lastSecondCard(int i) {
    return piles[i].at(piles[i].size() - 2);
}
inline int lastThirdCard(int i) {
    return piles[i].at(piles[i].size() - 3);
}

bool clear(int i) {
    if(piles[i].size() >= 3) {
        if((firstCard(i) + secondCard(i) + lastCard(i)) % 10 == 0) {
            deck.push_back(firstCard(i));
            deck.push_back(secondCard(i));
            deck.push_back(lastCard(i));
            piles[i].pop_front();
            piles[i].pop_front();
            piles[i].pop_back();
            return true;
        }else if((firstCard(i) + lastCard(i) + lastSecondCard(i)) % 10 == 0) {
            deck.push_back(firstCard(i));
            deck.push_back(lastSecondCard(i));
            deck.push_back(lastCard(i));
            piles[i].pop_front();            
            piles[i].pop_back();
            piles[i].pop_back();
            return true;
        }else if((lastCard(i) + lastSecondCard(i) + lastThirdCard(i)) % 10 == 0) {
            deck.push_back(lastThirdCard(i));
            deck.push_back(lastSecondCard(i));
            deck.push_back(lastCard(i));
            piles[i].pop_back();
            piles[i].pop_back();
            piles[i].pop_back();
            return true;
        }
    }
    return false;
}

bool memorize() {
    ull val = 0; //采用哈希记录局面
    for(int i = 0; i < maxp; ++i) {
        for(int j = 0; j < piles[i].size(); ++j)
            val = val * hashBase + piles[i].at(j);
        val = val * hashBase + 15; //分隔符
    }
    for(int i = 0; i < deck.size(); ++i)
        val = val * hashBase + deck[i];
    if(vis.count(val)) return true;
    vis.insert(val);
    return false;
}

int deal() {
    for(int i = 0; i < maxp; ++i) {
        if(deck.size() == maxn) return 1; //获胜
        if(piles[i].empty() == false) {
            if(deck.empty()) return 0; //输了
            piles[i].push_back(deck.front());
            deck.pop_front();
            times++;
            while(clear(i)); //消牌
            if(memorize()) return -1; //每一步记录局面
        }
    }
    return 2; //什么都没有发生
}

void Solve() {
    for(int i = 0; i < maxp; ++i)
        piles[i].resize(0);
    times = maxp * 2;
    for(int i = 0; i < maxp; ++i) {
        piles[i].push_back(deck.front());
        deck.pop_front();
        memorize();
    }
    for(int i = 0; i < maxp; ++i) {
        piles[i].push_back(deck.front());
        deck.pop_front();
        memorize();
    }
    while(true) {
        int ret = deal();
        if(ret == 1) {
            printf("Win : %d\n", times);
            break;
        }else if(ret == 0) {
            printf("Loss: %d\n", times);
            break;
        }else if(ret == -1) {
            printf("Draw: %d\n", times);
            break;
        }
    }
}

int main() {
    int t;
    while(t = ReadInt(), t) {
        deck.resize(0);
        vis.clear();
        deck.push_back(t);
        for(int i = 0; i < 51; ++i) deck.push_back(ReadInt());
        Solve();
    }
    return 0;
}

UVa 1400 - Ray, Pass me the dishes! UVa 11997 - K Smallest Sums