题目地址:https://nanti.jisuanke.com/t/41285
解题思路:
栈顶元素保存的是第i次操作之后栈中的最大值。
待入栈元素x, 栈不为空:若x>=栈顶值, x入栈,否则重新将栈顶值入栈;栈为空:直接入栈
ac代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e6+10;
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;
}
stack<ll> s;
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int t, Case = 0;
scanf("%d", &t);
while(t--)
{
ll ans = 0;
while(!s.empty()) s.pop();
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)
{
ll x = rng61() % m + 1;
if(!s.empty()) // 非空才有top()
{
if(x >= s.top()) s.push(x);
else s.push(s.top());
}
else s.push(x);
}
else
{
if(!s.empty()) s.pop();
}
if(!s.empty()) ans ^= i*s.top();
}
printf("Case #%d: %lld\n", ++Case, ans);
}
return 0;
}