题目链接:http://codeforces.com/problemset/problem/546/C
题意大意: 给一个n(<=10)表示两人手***有n张牌,接下来一行表示第1个人有k1张牌,k1 v1[1] v1[2]…v1[k1], v1[i]表示第i 张牌的大小,第三行表示第2个人 有k2张牌,k2 v2[1] v2[2]…v2[k2], v2[i]表示第i 张牌的大小。每一轮,两人从牌顶部各出一张,谁出的牌大则两张牌归谁,把对方和自己的牌放入到自己牌的底部,直到其中一个人 手中没有牌出,则那个人输了。问需要多少轮,哪个人赢了。如果没有解则输出-1(k1 + k2 = n)

//用两个队列模拟就可以了。当游戏次数太多时可以输出-1

//如果严格的来判断游戏会不会结束。
//可以用map保存两个人手中的状态
map<queue<int>, map<queue<int>,int> >m;

while(!q1.empty()&&!q2.empty())
    {
        ans++;
        /**************/
        m[q1][q2]++;  //每轮游戏开始时,记录当前状态存在
		/*************/
        
        int a=q1.front(), b=q2.front();
        q1.pop(), q2.pop();

        if(a>b)
        {
            q1.push(b), q1.push(a);
        }
        else
        {
            q2.push(a), q2.push(b);
        }
		
		/**************/
        if(m[q1][q2]==1)//每轮游戏结束时,判断新状态是否已经存在
        {
            printf("-1\n");

            return 0;
        }
        /*************/
    }

思考:map对状态判重有奇效。

全部代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define p1 first
//#define p2 second
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map

queue<int> q1, q2;
map<queue<int>, map<queue<int>,int> >m;
int main()
{
    int n, a, cut=0, ans=0;
    scanf("%d",&n);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        q1.push(a);
    }

    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        q2.push(a);
    }

    while(!q1.empty()&&!q2.empty())
    {
        ans++;
        m[q1][q2]++;
        int a=q1.front(), b=q2.front();
        q1.pop(), q2.pop();

        if(a>b)
        {
            q1.push(b), q1.push(a);
        }
        else
        {
            q2.push(a), q2.push(b);
        }

        if(m[q1][q2]==1)
        {
            printf("-1\n");

            return 0;
        }
    }
    if(!q1.empty())
    {
        printf("%d 1\n",ans);
    }
    else
    {
        printf("%d 2\n",ans);
    }

    return 0;
}