欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

SDUT---OJ《数据结构与算法》实践能力专题训练3 栈与队列

程序员文章站 2024-01-28 18:06:10
...

A - 数据结构实验之栈与队列一：进制转换

Description

输入一个十进制非负整数，将其转换成对应的 R (2 <= R <= 9) 进制数，并输出。

Input

第一行输入需要转换的十进制非负整数；
第二行输入 R。

Output

输出转换所得的 R 进制数。

Sample

Input 

1279
8

Output 

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

int main()
{
    int n,r,top;
    int a[10010];
    scanf("%d",&n);
    scanf("%d",&r);
    top=0;
    if(n==0)
    {
        printf("%d\n",n);
    }
    else
    {
        while(n)
        {
            a[top]=n%r;
            n=n/r;
            top++;
        }
        for(int i=top-1; i>=0; i--)
        {
            printf("%d",a[i]);
        }
        printf("\n");
    }
    return 0;
}

B - 数据结构实验之栈与队列二：一般算术表达式转换成后缀式

Description

对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

Input

输入一个算术表达式，以‘#’字符作为结束标志。

Output

输出该表达式转换所得到的后缀式。

Sample

Input 

a*b+(c-d/e)*f#

Output 

ab*cde/-f*+
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int st(char a)
{
    if(a=='+'||a=='-') return 1;
    else if(a=='/'||a=='*') return 2;
    else if(a=='(') return 3;
    else if(a==')') return 4;
    return 0;
}
int main()
{
    int top=0;
    char s,b[1000010];
    while(~scanf("%c",&s)&&s!='#')
    {
        if(s>='a'&&s<='z')
        {
            printf("%c",s);
        }
        else
        {
            if(top==0)
            {
                top++;
                b[top]=s;
            }
            else if(st(s)>st(b[top]))
            {
                if(st(s)==4)
                {
                    while(b[top]!='(')
                    {
                        printf("%c",b[top]);
                        top--;
                    }
                    top--;
                }
                else
                {
                    top++;
                    b[top]=s;
                }
            }
            else
            {
                if(b[top]=='(')
                {
                    top++;
                    b[top]=s;
                }
                else
                {
                    printf("%c",b[top]);
                    b[top]=s;
                }
            }
        }
    }
    while(top)
    {
        printf("%c",b[top]);
        top--;
    }
    printf("\n");
    return 0;
}

C - 数据结构实验之栈与队列三：后缀式求值

Description

对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。

Input

输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。

Output

求该后缀式所对应的算术表达式的值，并输出之。

Sample

Input 

59*684/-3*+#

Output 

57

Hint

基本操作数都是一位正整数!

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

int main()
{
    int a[1000001];
    int x,y,top,i,j,k,m,n;
    char b[1000001];
    scanf("%s",b);
    n=strlen(b);
    top=0;
    for(i=0;i<n;i++)
    {
       if(b[i]=='#')
       {
          break;
       }
       else
       {
          if(b[i]>='0'&&b[i]<='9')
          {
             a[top]=b[i]-'0';
             top++;
          }
          else if(b[i]=='*')
          {
             a[top-2]=a[top-1]*a[top-2];
             top--;
          }
          else if(b[i]=='-')
          {
             a[top-2]=a[top-2]-a[top-1];
             top--;
          }
          else if(b[i]=='+')
          {
             a[top-2]=a[top-2]+a[top-1];
             top--;
          }
          else if(b[i]=='/')
          {
             a[top-2]=a[top-2]/a[top-1];
             top--;
          }
       }
    }
    printf("%d\n",a[0]);
    return 0;
}

D - 数据结构实验之栈与队列四：括号匹配

Description

 给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。

 

Input

 输入数据有多组，处理到文件结束。

 

Output

 如果匹配就输出“yes”，不匹配输出“no”

 

Sample

Input 

sin(20+10)
{[}]

Output 

yes
no
#include <bits/stdc++.h>

using namespace std;
char d[55];
char a[55];
int main()
{
    int n,i;
    while(gets(a)!=NULL)
    {
        int flag=0,top=-1;
        n=strlen(a);
        for(i=0; i<n; i++)
        {
            if(a[i]=='('||a[i]=='['||a[i]=='{')
            {
                d[++top]=a[i];
            }
            else
            {
                if(a[i]==')')
                {
                    if(top!=-1&&d[top]=='(')
                    {
                        top--;
                    }
                    else
                    {
                        flag=1;
                        break;
                    }
                }
                if(a[i]==']')
                {
                    if(top!=-1&&d[top]=='[')
                    {
                        top--;
                    }
                    else
                    {
                        flag=1;
                        break;
                    }
                }
                if(a[i]=='}')
                {
                    if(top!=-1&&d[top]=='{')
                    {
                        top--;
                    }
                    else
                    {
                        flag=1;
                        break;
                    }
                }
            }
        }
        if(top!=-1)
        {
            printf("no\n");
        }
        else
        {
            if(flag)
            {
                printf("no\n");
            }
            else
            {
                printf("yes\n");
            }
        }

    }
    return 0;
}

E - 数据结构实验之栈与队列五：下一较大值（一）

Description

对于包含n（1<=n<=1000）个整数的序列，对于序列中的每一元素，在序列中查找其位置之后第一个大于它的值，如果找到，输出所找到的值，否则，输出-1。

Input

 输入有多组，第一行输入t（1<=t<=10），表示输入的组数；

以后是 t 组输入：每组先输入n，表示本组序列的元素个数，之后依次输入本组的n个元素。

Output

 输出有多组，每组之间输出一个空行（最后一组之后没有）；

每组输出按照本序列元素的顺序，依次逐行输出当前元素及其查找结果，两者之间以-->间隔。

Sample

Input 

2
4 12 20 15 18
5 20 15 25 30 6

Output 

12-->20
20-->-1
15-->18
18-->-1

20-->25
15-->25
25-->30
30-->-1
6-->-1

Hint

 本题的数据量小、限时要求低，可以不用栈来完成。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t,n,i,j,k,flag;
    int a[1010];
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            for(i=0;i<n;i++)
            {
                if(a[i]!=0)
                {
                    k=a[i];
                    flag=0;
                    for(j=i; j<n; j++)
                    {
                        if(k<a[j])
                        {
                            printf("%d-->%d\n",k,a[j]);
                            k=a[j];
                            a[i]=0;
                            flag=0;
                            break;
                        }
                        else
                        {
                            flag=1;
                        }
                    }
                    if(flag==1)
                    {
                        printf("%d-->-1\n",k);
                    }
                }
            }
            if(t!=0)
            {
                printf("\n");
            }
        }
    }
    return 0;
}

F - 数据结构实验之栈与队列六：下一较大值（二）

Description

对于包含n（1<=n<=100000）个整数的序列，对于序列中的每一元素，在序列中查找其位置之后第一个大于它的值，如果找到，输出所找到的值，否则，输出-1。

Input

输入有多组，第一行输入t（1<=t<=10），表示输入的组数；

以后是 t 组输入：每组先输入n，表示本组序列的元素个数，之后依次输入本组的n个元素。

Output

输出有多组，每组之间输出一个空行（最后一组之后没有）；

每组输出按照本序列元素的顺序，依次逐行输出当前元素及其查找结果，两者之间以-->间隔。

Sample

Input 

2
4 12 20 15 18
5 20 15 25 30 6

Output 

12-->20
20-->-1
15-->18
18-->-1

20-->25
15-->25
25-->30
30-->-1
6-->-1

Hint

本题数据量大、限时要求高，须借助栈来完成。

#include <bits/stdc++.h>

using namespace std;

int a[100010],b[100010],c[100010];
int main()
{
    int t,i,n,l,j;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            int top=0;
            scanf("%d",&n);
            for(j=1; j<=n; j++)
            {
                scanf("%d",&a[j]);
            }
            b[n]=-1;
            c[++top]=a[n];
            for(i=n-1; i>=1; i--)
            {
                c[++top]=a[i];
                if(a[i+1]>a[i])
                {
                    b[i]=a[i+1];
                }
                else
                {
                    int f=0;
                    while(top!=1)
                    {
                        if(c[top]<c[top-1])
                        {
                            b[i]=c[top-1];
                            f=1;
                            break;
                        }
                        else
                        {
                            c[top-1]=c[top];
                            top--;
                        }
                    }
                    if(f==0)b[i]=-1;
                }
            }
            for(i=1; i<=n; i++)
            {
                printf("%d-->%d\n",a[i],b[i]);
            }
            if(t!=0)
            {
                printf("\n");
            }
        }
    }
    return 0;
}

G - 数据结构实验之栈与队列七：出栈序列判定

Description

给一个初始的入栈序列，其次序即为元素的入栈次序，栈顶元素可以随时出栈，每个元素只能入栈依次。输入一个入栈序列，后面依次输入多个序列，请判断这些序列是否为所给入栈序列合法的出栈序列。

例如序列1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个出栈序列，但4，3，5，1，2就不可能是该序列的出栈序列。假设压入栈的所有数字均不相等。

Input

第一行输入整数n(1<=n<=10000)，表示序列的长度。

第二行输入n个整数，表示栈的压入顺序。

第三行输入整数t（1<=t<=10）。

后面依次输入t行，每行n个整数，表示要判断的每一个出栈序列。

Output

对应每个测试案例输出一行，如果由初始入栈序列可以得到该出栈序列，则输出yes，否则输出no。

 

Sample

Input 

5
1 2 3 4 5
2
4 5 3 2 1
4 3 5 1 2

Output 

yes
no

Hint

#include <bits/stdc++.h>

using namespace std;

int Push[10010],Stack[10010],Pop[10010];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&Push[i]);
    }

    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d",&Pop[i]);
        }

        int i=0;
        int j=0;
        int top = -1;
        bool flag = false;
        while(j < n)
        {
            if(top == -1 || Stack[top] < Pop[j])
            {
                if(top < n-1)
                    Stack[++top] = Push[i++];
                else
                {
                    flag = true;
                    break;
                }
            }
            if(Stack[top] == Pop[j])
                --top,++j;
            else if(Stack[top] > Pop[j])
            {
                flag = true;
                break;
            }
        }
        if(!flag)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

H - 数据结构实验之栈与队列八：栈的基本操作

Description

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。

Input

首先输入整数t（1 <= t <= 10），代表测试的组数，以后是 t 组输入。
 对于每组测试数据，第一行输入两个正整数 m（1 <= m <= 100)、n（1 <= n <= 1000)，其中m代表当前栈的最大长度，n代表本组测试下面要输入的操作数。 而后的 n 行，每行的第一个字符可能是'P’或者'O’或者'A’；如果是'P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O’，表示栈顶元素出栈；如果是'A'，表示询问当前栈顶的值'。

Output

 对于每组测试数据，根据其中的命令字符来处理堆栈；
（1）对所有的'P'操作，如果栈满输出'F'，否则完成压栈操作；
（2）对所有的'A'操作，如果栈空，则输出'E'，否则输出当时栈顶的值；
（3）对所有的'O'操作，如果栈空，则输出'E'，否则输出栈顶元素的值，并让其出栈；
每个输出占据一行，每组测试数据（最后一组除外）完成后，输出一个空行。

Sample

Input 

2
5 10
A
P 9
A
P 6
P 3
P 10
P 8
A
P 2
O
2 5
P 1
P 3
O
P 5
A

Output 

E
9
8
F
8

3
5

Hint

建议： 用串的方式（%s）读入操作字符。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t, m, n, i, j, k, x, y, top;
    char a[10];
    int d[1010];
    scanf("%d",&t);
    while(t--)
    {
        top=-1;
        scanf("%d %d",&m,&n);
        for(i=0; i<n; i++)
        {
            scanf("%s",&a);
            if(a[0]=='P')
            {
                scanf("%d",&k);
                if(top==m-1)
                {
                    printf("F\n");
                }
                else
                {
                    d[++top]=k;
                }
            }
            if(a[0]=='A')
            {
                if(top==-1)
                {
                    printf("E\n");
                }
                else
                {
                    printf("%d\n",d[top]);
                }
            }
            if(a[0]=='O')
            {
                if(top==-1)
                {
                    printf("E\n");
                }
                else
                {
                    printf("%d\n",d[top]);
                    top=top-1;
                }
            }
        }
        if(t!=0)
        {
            printf("\n");
        }
    }
    return 0;
}

I - 数据结构实验之栈与队列九：行编辑器

Description

 一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。 

 

由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符"#"，以表示前一个字符无效； 

 

如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符"@"，以表示当前行中的字符均无效。 

 

如果已经在行首继续输入'#'符号无效。 

Input

 输入多行字符序列，行字符总数（包含退格符和退行符）不大于250。 

Output

 按照上述说明得到的输出。 

Sample

Input 

whli##ilr#e(s#*s)
aaa@qq.com(*s=#++);

Output 

while(*s)
putchar(*s++);
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    char a[100010],b[100010];
    int i,j,k,l,n;
    while(~scanf("%s",a))
    {
       n=strlen(a);
       int top=0;
       for(i=0;i<n;i++)
       {
          if(a[i]!='#'&&a[i]!='@')
          {
             b[top++]=a[i];
          }
          else
          {
             if(a[i]=='#')
             {
                if(top!=0)
                {
                   top--;
                }
             }
             if(a[i]=='@')
             {
                while(top)
                {
                   top--;
                }
             }
          }
       }
       for(i=0;i<top;i++)
       {
          printf("%c",b[i]);
       }
       printf("\n");
    }
    return 0;
}

J - 数据结构实验之栈与队列十：走迷宫

Description

一个由n * m 个格子组成的迷宫，起点是(1, 1)， 终点是(n, m)，每次可以向上下左右四个方向任意走一步，并且有些格子是不能走动，求从起点到终点经过每个格子至多一次的走法数。

Input

       第一行一个整数T 表示有T 组测试数据。(T <= 110)

对于每组测试数据:

第一行两个整数n, m，表示迷宫有n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行，每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走，否则是1 表示这个格子不能走，输入保证起点和终点都是都是可以走的。

任意两组测试数据间用一个空行分开。

Output

 对于每组测试数据，输出一个整数R，表示有R 种走法。

 

Sample

Input 

3
2 2
0 1
0 0
2 2
0 1
1 0
2 3
0 0 0
0 0 0

Output 

1
0
4
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

char a[210000][20],b[210000][20];
int main()
{
    int n,m;
    char s[10],x[20];
    int i,j,k,l;
    while(~scanf("%d %d",&n,&m))
    {

        int top1=0;
        int top2=0;
        int flag=0;
        while(m--)
        {

            getchar();
            scanf("%s",s);
            if(strcmp(s,"Add")==0)
            {
                getchar();
                scanf("%s",x);
                if(top1<n)
                {
                    strcpy(a[top1],x);
                    top1++;
                }
                else
                {
                    strcpy(b[top2],x);
                    top2++;
                }
            }
            if(strcmp(s,"Del")==0)
            {
                if(top1==0)
                {
                    flag=1;
                }
                else
                {
                    top1--;
                    if(top2!=0)
                    {
                        strcpy(a[top1],b[0]);
                        for(i=0; i<top2; i++)
                        {
                            strcpy(b[i],b[i+1]);
                        }
                        top2--;
                        top1++;
                    }
                }
            }
            if(strcmp(s,"Out")==0)
            {
                if(top2==0)
                {
                    flag=1;
                }
                else
                {
                    for(i=0; i<top2; i++)
                    {
                        strcpy(b[i],b[i+1]);
                    }
                    top2--;
                }
            }
        }
        if(flag==1)
        {
            printf("Error\n");
        }
        else
        {
            for(i=top1-1; i>=0; i--)
            {
                printf("%s\n",a[i]);
            }
        }

    }
    return 0;
}

K - 数据结构实验之栈与队列十一：refresh的停车场

Description

 refresh最近发了一笔横财，开了一家停车场。由于土地有限，停车场内停车数量有限，但是要求进停车场的车辆过多。当停车场满时，要进入的车辆会进入便道等待，最先进入便道的车辆会优先

进入停车场，而且停车场的结构要求只出去的车辆必须是停车场中最后进去的车辆。现告诉你停车场容量N以及命令数M，以及一些命令（Add num 表示车牌号为num的车辆要进入停车场或便道，

Del 表示停车场中出去了一辆车，Out 表示便道最前面的车辆不再等待，放弃进入停车场）。假设便道内的车辆不超过1000000.

Input

 输入为多组数据，每组数据首先输入N和M（0＜　ｎ，ｍ　＜200000），接下来输入M条命令。

Output

 输入结束后，如果出现停车场内无车辆而出现Del或者便道内无车辆而出现Out,则输出Error,否则输出停车场内的车辆，最后进入的最先输出，无车辆不输出。

Sample

Input 

2 6
Add 18353364208
Add 18353365550
Add 18353365558
Add 18353365559
Del
Out

Output 

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

char a[210000][20],b[210000][20];
int main()
{
    int n,m;
    char s[10],x[20];
    int i,j,k,l;
    while(~scanf("%d %d",&n,&m))
    {

        int top1=0;
        int top2=0;
        int flag=0;
        while(m--)
        {

            getchar();
            scanf("%s",s);
            if(strcmp(s,"Add")==0)
            {
                getchar();
                scanf("%s",x);
                if(top1<n)
                {
                    strcpy(a[top1],x);
                    top1++;
                }
                else
                {
                    strcpy(b[top2],x);
                    top2++;
                }
            }
            if(strcmp(s,"Del")==0)
            {
                if(top1==0)
                {
                    flag=1;
                }
                else
                {
                    top1--;
                    if(top2!=0)
                    {
                        strcpy(a[top1],b[0]);
                        for(i=0; i<top2; i++)
                        {
                            strcpy(b[i],b[i+1]);
                        }
                        top2--;
                        top1++;
                    }
                }
            }
            if(strcmp(s,"Out")==0)
            {
                if(top2==0)
                {
                    flag=1;
                }
                else
                {
                    for(i=0; i<top2; i++)
                    {
                        strcpy(b[i],b[i+1]);
                    }
                    top2--;
                }
            }
        }
        if(flag==1)
        {
            printf("Error\n");
        }
        else
        {
            for(i=top1-1; i>=0; i--)
            {
                printf("%s\n",a[i]);
            }
        }

    }
    return 0;
}

L - Special Judge Ⅲ

Description

Q：什么是 Special Judge，Special Judge 的题目有什么不同?

A：一个题目可以接受多种正确方案，即有多组解的时候,题目就必须被 Special Judge。Special Judge 程序使用输入数据和一些其他信息来判答你程序的输出，并将判答结果返回。

不抽黑贞与咸鱼有什么区别？

 

SDUT---OJ《数据结构与算法》实践能力专题训练3 栈与队列

 

5月3日 FGO(Fate/Grand Order) 赝作活动来袭，MLE 开始了他的玄学抽卡：

他在 n 个小方块上写上数字，并按照先后顺序往上堆，在堆的过程中他会随机性的把上面的小方块抽走，堆完以后再依次从上往下把剩余没抽完的小方块抽走。按照小方块抽走的先后顺序排列开来（先拿走的小方块放最前面），之后再随机选择一个小方块，这个小方块上面的数字就表示活动开始以后的若干秒后开始抽卡。

不幸的是由于过于激动把小方块抽走的先后顺序给忘了，MLE 向闲来无事的 keke 求助，让他给出一个序列看自己能不能想起来，但为了避免浪费时间，MLE 希望 keke 给出的序列符合小方块抽走后排列的顺序，现在问题留给你，由你来判断这个序列是否合法。

Input

输入数据有多组（数据组数不超过 1000），到 EOF 结束。

对于每组数据：

  • 第一行先输入一个数 n (0 <= n <= 1000) 表示小方块的个数
  • 第二行输入 n 个数表示小方块上的数字，均为正整数
  • 第三行输入 keke 给出的序列，长度与小方块个数一致

所有数据范围均为 [0, 1000]。

Output

Keke 的答案正确输出 "Accepted"，否则输出 "Wrong Answer"（不包括引号）。

Sample

Input 

5
1 2 3 4 5
5 4 3 2 1

Output 

Accepted

Hint

当 n 为 0 时认为是 "Accepted"。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[10010],b[10010],c[10010];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        int t;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&b[i]);
        }
        int i=0;
        int j=0;
        int top=-1;
        int flag;
        flag=0;
        while(j<n)
        {
            if(top==-1||c[top]<b[j])
            {
                if(top<n-1)
                {
                    c[++top]=a[i++];
                }
                else
                {
                    flag=1;
                    break;
                }
            }
            if(c[top]==b[j])
            {
                --top;
                ++j;
            }
            else if(c[top]>b[j])
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
            printf("Accepted\n");
        else
            printf("Wrong Answer\n");
    }
    return 0;
}

M - 我成了瘸腿鹅

Description

智 (hei) 慧 (bang) 长 (yi) 者 (ge) 阿福虽说是智勇双全，却无奈老是被该 (zheng) 死 (yi) 的成龙欺负。既然武斗不行，那么今天阿福决定靠他的智慧为自己找回些面子。所以他今天打算和成龙来比纸牌接龙游戏，输的人将会接受惩罚。游戏是这样的阿福先出牌，然后成龙出牌，出的牌按出牌顺序排成一列，如果当前出的牌在出牌序列中，那么那个人可以取走两张相同牌之间的所有牌并加上相应于牌数的分。比如原牌的排列为 5 4 3 6 9 8 现在成龙出牌 9 那么他可以取走 9 8 9 得到 3 分，然后牌的序列就变成 5 4 3 6 了。

最后看他们两个人的得分谁比较高，分数低的人将会接受惩罚，由于阿福长的比较丑，所以得分相同的情况下算阿福输（长得丑怪我咯）。

智 (hei) 慧 (bang) 长 (yi) 者 (ge) 阿福相信自己智勇双全一定会赢的，所以他打算赌得大一点：”谁输了就把他打成瘸腿鹅！”。由于没有人见证了他们的比赛过程，只知道他们的总出牌序列，想在好奇得到 UMR 想知道最后谁成了瘸腿鹅，但是 UMR 智商令人着急所以只能聪明的你求助了，你能告诉他谁被打成瘸腿鹅了吗？如果你说对了 UMR 将会将给你一个大大的 AC 作为回报。

Input

第一行输入一个 nnn，代表总共出了 nnn 张牌 (2⩽n⩽100000)(2 \leqslant n \leqslant 100000)(2⩽n⩽100000)。

接下来 nnn 个数 aia_{i}ai​，代表他们出的牌 (1⩽ai⩽10)(1 \leqslant a_{i} \leqslant 10)(1⩽ai​⩽10)。

Output

​如果阿福输了输出 ON!。

否则输出 HaHa!（不存在的）。

Sample

Input 

9
1 2 5 8 7 1 8 7 8

Output 

ON!

Hint

阿福先出牌。

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

int main()
{
    int n;
    int a[12];
    int b[100100];
    scanf("%d",&n);
    int i,j,k,top,m,sum1,sum2,sum;
    top=0;
    sum1=sum2=sum=0;
    memset(a,0,sizeof(a));
    for(i=1;i<=n;i++)
    {
        scanf("%d",&k);
        if(a[k]==0)
        {
            a[k]=1;
            b[top++]=k;
        }
        else
        {
            sum=0;
            sum++;
            while(k!=b[top-1])
            {
                a[b[top-1]]=0;
                top--;
                sum++;
            }
            sum++;
            top--;
            a[k]=0;
            if(i%2==0)
            {
                sum2=sum2+sum;
            }
            else
            {
                sum1=sum1+sum;
            }
        }
    }
    if(sum1<=sum2)
    {
        printf("ON!\n");
    }
    else
    {
        printf("HaHa!\n");
    }
    return 0;
}

N - 蚂蚁花呗

Description

众所周知，蚂蚁是一种十分神奇的生物，在算法设计中，我们往往能从它身上得到启发，例如在求解TSP问题中，就有一种模仿蚂蚁行为方式而设计出的蚁群算法。 z这种算法是由Marco Dorigo等人在1991年研究新型算法的过程中，发现蚁群在寻找食物时，通过蚂蚁分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标，据此提出来的一种十分神奇的算法。

 

今天，我们也来从蚂蚁身上寻找一些灵感。

 

水平线上有 N 只蚂蚁，每只蚂蚁的位置及大小均不同。他们沿着 X 轴爬行，有的向左，有的向右，爬行的速度是一样的，两只蚂蚁相遇大一点的会吃掉小的。

 

现在从左到右给出每只蚂蚁的大小和爬行的方向（0 表示向左，1 表示向右）。问足够长的时间之后，能剩下多少只蚂蚁？

Input

 

首先输入测试数据的组数t，后面是t组测试数据。

 

对于每组测试数据：

 

第 1 行：一个整数 N，表示蚂蚁的数量 (1≤N≤100000)。

 

第 2 到 N+1 行：每行两个数 Ai,Bi (1≤Ai≤1e9，Bi∈{0,1})，中间用空格分隔，分别表示蚂蚁的大小及爬 行的方向，Bi=0 表示向左，Bi=1 表示向右。

Output

输出最终剩下的蚂蚁的数量。

Sample

Input 

1
5
4 0
3 1
2 0
1 0
5 0

Output 

2

 

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

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a[100010];
        int n,sum,i,j,k,x,y;
        int top=0;
        scanf("%d",&n);
        sum=n;
        for(i=0;i<n;i++)
        {
            scanf("%d %d",&x,&y);
            if(y==1)
            {
                a[top++]=x;
            }
            else
            {
                while(x>a[top-1]&&top!=0)
                {
                    sum--;
                    top--;
                }
                if(top!=0)
                {
                    sum--;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

 

相关标签： 数据结构与算法

上一篇： 栈和队列——队列

下一篇：

推荐阅读