FZU 1884——排火车—————

排火车

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

某天,Apple问起Gaga，”扑克牌排火车有没有玩过??”,”没有-_-“。Apple感到很不可思议，他决定马上教Gaga玩这个游戏。碍于手头上没有扑克牌，Apple就剪了几张卡片，然后在卡片上写上数字，然后对Gaga说“简单来讲，就是你有一堆牌，我有一堆牌，我们轮流出，每次把牌叠在上一次出的牌的下方，如果这时发现当前的牌与前面的牌有重复，那么这之间的牌就都归你了。这样到最后谁没有牌，谁就输了。”“oh，原来如此”。Gaga觉得这个也不过如此。

于是他们开始玩排火车了。。。

现在假设Apple和Gaga各有N张牌，Apple先出牌。请你给出一轮下来Apple和Gaga各获得的牌数。

Input

第一行T，表示T组测试数据，接下来有T部分。

每部分开头是一个整数N（1 <= N <= 50000）,表示Apple和Gaga的牌数。接下来有2行，给出Apple和Gaga的牌的情况。首先给出Apple的牌，有N个整数，第i个整数xi(1 <= xi <= 100000)表示Apple的第i张牌面。其次给出Gaga的牌，格式类似。

Output

对于每组测试数据，首先输出”Case k:”，其中k表示第几组。然后输出 Apple和Gaga这一轮获得的牌数。

Sample Input

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

Sample Output

Case 1:Apple:0 Gaga:6 Case 2:Apple:0 Gaga:0 Case 3:Apple:3 Gaga:3

Hint

输入巨大，c++请使用scanf输入避免超时。

错误点：自己用两个数组模拟过程，因为要每次清空标记，没想到用容器来存储。。。脑子笨。然后一直超时，后改为容器后，又一直wa，不知道到底哪里错了。囧。看了其他人的代码，发现用栈来模拟过程相当简单，然后就借鉴了。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<stack>

using namespace std;

const int maxn=110000;

int flag[maxn];

int a[maxn];

int main(){

    int t,cnt=0;

    scanf("%d",&t);

    while(t--){

        memset(flag,0,sizeof(flag));

        int n,aa=0,bb=0;

        scanf("%d",&n);

        for(int i=0;i<n;i++){

            scanf("%d",&a[i*2]);

        }

        for(int i=0;i<n;i++){

            scanf("%d",&a[i*2+1]);

        }

        stack<int>S;

        while(!S.empty()){

            S.pop();

        }

        for(int i=0;i<2*n;i++){

            if(!flag[a[i]]){

                flag[a[i]]=1;

                S.push(a[i]);

            }else{

                int tmp=0,num=0;

                while(!S.empty()){

                    tmp=S.top();

                    flag[tmp]=0;

                    if(tmp!=a[i]){

                        S.pop();

                        num++;

                    }else{

                        break;

                    }

                }

                S.pop();

                num+=2;

                if(i%2==0){

                    aa+=num;

                }else{

                    bb+=num;

                }

            }

        }

        printf("Case %d:Apple:%d Gaga:%d\n",++cnt,aa,bb);

    }

    return 0;

}

巴特西

FZU 1884——排火车——————【栈的模拟】

最新文章

热门文章