本文主要是介绍hdu 5929 Basic Data Structure 模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// hdu 5929 Basic Data Structure 模拟
// 题目链接:// http://acm.hdu.edu.cn/showproblem.php?pid=5929// 题目大意:// 有这样一个栈,栈中只放入0或者1,有四种操作
// 1)PUSH 1 or 0
// 2)POP: 弹出栈顶元素
// 3)REVERSE: 将栈中元素逆序
// 4)QUERY: 查询stack[top] nand stack[top-1]... nand stack[0];// 注:
// 0 nand 0 = 1
// 0 nand 1 = 1
// 1 nand 0 = 1
// 1 nand 1 = 0// 解题思路:// 首先注意到有0的时候,结果一定是1,重要性质.我们只要搞定距离栈底的
// 最近的0以及之后1的个数就好
// 其次对于REVERSE,我们可以用一个双端栈,设置一个标量,就可以解决// 感悟:// 亮点就是用双端栈的结构了,其次是细节的考虑,还算简单,熟悉栈的操作
// 并不难写.继续奋斗^_^#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int MAXN = 2e5 + 8;
const int ZERO = 2e5; // 矫正0
int pos[MAXN << 1]; // 记录0的位置int main(){int t;//freopen("1.txt","r",stdin);scanf("%d",&t);for (int tt = 1; tt <= t; tt++){printf("Case #%d:\n",tt);memset(pos,0,sizeof(pos));int n;scanf("%d",&n);char str[10];int dir = 1; // 方向标量int ltop = ZERO; // 反向栈顶int rtop = ZERO + 1; //正向栈顶int lz = ZERO; // 反向栈顶0int rz = ZERO + 1; // 正向栈顶0int x;for (int i = 1;i <= n;i ++){scanf("%s",str);if (str[0] == 'P' && str[1] == 'U'){scanf("%d",&x);if (dir > 0){if (x == 0)pos[rz++] = rtop;rtop++;}else {if (x == 0)pos[lz--] = ltop;ltop--;}}else if (str[0] == 'P' && str[1] == 'O'){if (dir > 0){if (pos[rz - 1] == rtop - 1) // 弹出0pos[rz - 1] = 0,rz--;rtop--;}else {if (pos[lz + 1] == ltop + 1) // 弹出0pos[lz + 1] = 0,lz++;ltop++;}}else if (str[0] == 'R'){dir = - dir;}else{// cout << "top: " << ltop << " " << rtop << endl;
// cout << "lz: " << lz << " " << rz << endl;
// cout << "pos: " << pos[lz + 1] << " " << pos[rz - 1] << endl;
// cout << "dir: " << dir << endl;if (ltop + 1 > rtop - 1){ // 栈中元素为空printf("Invalid.\n");continue;}if (dir > 0){if (pos[lz + 1] > ltop && pos[lz + 1] < rtop){ // 栈中有0if (pos[lz + 1] == ltop + 1){ //栈底为0puts("1");continue;}// 考虑 111...110 与 1111...011...111int l = pos[lz + 1] - ltop - 1; // 栈底0以下的1的个数bool has = (pos[lz + 1] == rtop - 1 ? 0 : 1); // 0上是否有0if ((l & 1) ^ has){ //分类讨论得出puts("1");}else{puts("0");}}else { // 全1int sum = rtop - 1 - ltop;if (sum & 1){puts("1");}else {puts("0");}}}else {// 镜像对称,反向考虑即可if (pos[rz - 1] > ltop && pos[rz - 1] < rtop){if (pos[rz - 1] == rtop - 1){puts("1");continue;}int l = rtop - 1 - pos[rz - 1];bool has = (pos[rz - 1] == ltop + 1 ? 0 : 1);if ((l & 1) ^ has){puts("1");}else{puts("0");}}else {int sum = rtop - 1 - ltop;if (sum & 1){puts("1");}else {puts("0");}}}}}}return 0;
}
这篇关于hdu 5929 Basic Data Structure 模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
