A-Maximum Element In A Stack

Maximum Element In A Stack

题目大意:对一个栈进行操作入栈和出栈。每次操作后返回当前栈中的最大值,push和pop操作由题目给定的代码段进行决定,最后输出   

i为第i次操作,ai为每一次操作的结果即最大值,输出每次的异或和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =5*1000000+10;
ll Max;
ll ans[maxn];
int times;
struct sta
{
    ll a[maxn];
    ll top=-1;
};
struct sta s;
unsigned int SA,SB,SC;
ll n,p,q,m;
void PUSH(ll x)
{
    if(x>=s.a[s.top])
    {
      Max=x;
      s.a[++s.top]=Max;
    }
    else
    {
        s.a[++s.top]=Max;
    }
    ans[++times]=s.a[s.top];
}
void POP()
{
    if(s.top==-1){ans[++times]=0; Max=0;}
    else
    {
         s.top--;
         if(s.top!=-1)
         {
               ans[++times]=s.a[s.top];
               Max=s.a[s.top];
         }
         else
         {
               ans[++times]=0;
               Max=0;
         }
    }
}
unsigned int rng61()
{
    SA^=SA<<16;
    SA^=SA>>5;
    SA^=SA<<1;
    unsigned int t=SA;
    SA = SB;
    SB = SC;
    SC^= t^ SA;
    return SC;
}
void gen()
{

    scanf("%lld%lld%lld%lld%u%u%u",&n,&p,&q,&m,&SA,&SB,&SC);
    for(int i=1;i<=n;i++)
    {
        if(rng61()%(p+q)<p)
            PUSH(rng61()%m+1);
        else
            POP();
    }
}
int main()
{
    int t;
    int kase=0;
    //freopen("data.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        ll Max=0;
        ll sum=0;
        times=0;
        memset(ans,0,sizeof(ans));
        memset(s.a,0,sizeof(s.a));
        s.top=-1;
        gen();
        for(ll i=1;i<=n;i++)
            sum^=i*ans[i];
        printf("Case #%d: %lld
",++kase,sum);

    }
    return 0;
}
原文地址:https://www.cnblogs.com/kuroko-ghh/p/9363340.html