/ XMU_ACM / 题库 /

Maximum_Element_In_A_Stack

Maximum_Element_In_A_Stack

Description

现在有一个栈,初始为空。接下来有若干次操作,每次可能向栈顶push一个正整数,也可能pop掉一个栈顶元素。
你需要在每次操作之后计算出栈内所有元素的最大值。如果栈为空则认为此时最大值为0。
为了避免输入文件过大,所有操作将会使用rng61算法生成。同时为了避免输出文件过大,你只需要输出一个数:表示每次操作之后的答案与下标乘积的异或和。

Input

第一行给出了7个整数 n,p,q,m,SA,SB,SC。其中n表示总的操作次数,你的程序可以使用如下的c++代码生成所有的操作。
1<=n<=5*10^6
1<=p,q,m<=10^9
10^4<=SA,SB,SC<=10^6

int n,p,q,m;
unsigned int SA,SB,SC;
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("%d%d%d%d%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();
        }
    }
}

在这份代码中,PUSH(v)表示向栈顶中插入一个新的元素,它的值为v。POP()表示弹出栈顶的元素;如果当前栈为空,则什么也不操作(即:没有东西可以弹出)。

Output

输出一个正整数y

y=(a[1]*1)^(a[2]*2)^...(a[n]*n)

其中a[i]为第i次操作之后的答案。即y为每次操作之后的答案与下标乘积的异或和。

Sample 1

Input

4 1 1 4 23333 66666 233333

Output

19

Input

4 2 1 4 23333 66666 233333

Output

1

Limitation

1s, 64MB for each test case.

Hint

Free Pascal Code

var a,b:longint;
begin
    readln(a,b);
    writeln(a+b);
end.

C Code

#include <stdio.h>
int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

C++ Code

#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

Python Code

a, b = [int(i) for i in raw_input().split()]
print(a + b)

Java Code

import java.io.*;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a + b);
    }
}

Source

Vijos Original

信息

难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者

相关

在下列比赛中:

小学期第一次课堂小测