The 2018 ACM-ICPC CCPC 宁夏 A-Maximum Element In A Stack

题目链接：https://nanti.jisuanke.com/t/28401

题目是维护一个栈，有入栈和出栈两种操作，每次操作后要求出zh

栈中的最大值，然后对这些值按位异或，详情看原题。

一开始是直接模拟这个过程，每次操作以后遍历找最大值，结果超时了。换思路，入栈后判断栈顶元素和下一个元素的大小，其实如果小于的话是并不需要一直记录的，一直让栈顶元素等于最大值，出栈时，栈顶元素就是最大值，这样模拟并没有什么影响。

注意大数，答案会爆int。

代码如下：

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 5000005;
int n, p, q, m;
unsigned int SA, SB, SC;
int l[maxn], len;
ll ans;
int PUSH(int x) {
l[++len] = x;
return l[len] = max(l[len], l[len - 1]);
}
int POP() {
return l[len = max(len - 1, 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;
}
ll gen() {
ll ans, temp;
//注意大数，会爆int
ans = len = 0;
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)
temp = PUSH(rng61() % m + 1);
else
temp = POP();
ans ^= i * temp;
}
return ans;
}
int main() {
int T;
cin >> T;
for (int i = 1; i <= T; i++) {
cout << "Case #" << i << ": " << gen() << endl;
}
return 0;
}

最后

以上就是单身仙人掌为你收集整理的The 2018 ACM-ICPC CCPC 宁夏 A-Maximum Element In A Stack的全部内容，希望文章能够帮你解决The 2018 ACM-ICPC CCPC 宁夏 A-Maximum Element In A Stack所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。