题目:http://acm.split.hdu.edu.cn/showproblem.php?pid=5929
题意:让你维护一个栈,有4个操作
push 放入一个0或1
pop 取出顶部元素
reverse 反转栈
query 求nand
用双端队列模拟,push和pop很容易实现,reverse也只需要换一头进行操作
而求nand时可以注意到 0和任何数的nand都是1 所以我们需要维护0的位置
我们可以建立一个0的位置的双向链表,同时维护最靠近两头的0的位置
query只需要数1的个数就行了
注意pop时需要初始化双向链表
#include<cstdio> #include<iostream> #include<cmath> #include<queue> #include<map> #include<set> #include<stack> #include<stack> #include<string> #include<sstream> #include<cstring> #include<algorithm> using namespace std; const int N=5e5; int a[N+5];//双端队列 int lz[N+5];//左边0的位置 int rz[N+5];//右边0的位置 int main() { int T; scanf("%d",&T); for(int ca=1;ca<=T;ca++) { memset(a,0x3f,sizeof(a)); memset(lz,0,sizeof(lz)); memset(rz,0x3f,sizeof(rz)); int n; scanf("%d",&n); char s[10]; int t; int l=N/2,r=N/2,f=1,ll=0,rr=N;//队列左端,右端,方向,靠近左端的0位置,靠近右端的0位置 printf("Case #%d: ",ca); for(int i=1;i<=n;i++) { scanf("%s",s); if (s[0]=='P') { if (s[1]=='U') { scanf("%d",&t); if (f) { a[r]=t; if (t==0) { if (rr<r) { lz[r]=rr; rz[rr]=r; } rr=r; if (ll<l) ll=r; } r++; } else { a[--l]=t; if (t==0) { if (ll>l) { rz[l]=ll; lz[ll]=l; } ll=l; if (rr>=r) rr=l; } } } else { if (f) { r--; if (a[r]==0&&lz[r]>=l) { rz[lz[r]]=N; rr=lz[r]; lz[r]=0; rz[r]=N; } else if (a[r]==0) { ll=0; rr=N; lz[r]=0; rz[r]=N; } } else { if (a[l]==0&&rz[l]<r) { lz[rz[l]]=0; ll=rz[l]; rz[l]=N; lz[l]=0; } else if (a[l]==0) { ll=0; rr=N; lz[l]=0; rz[l]=N; } l++; } } } else if (s[0]=='R') f^=1; else { if (l==r) {printf("Invalid. ");continue;} if (!f) { int t=0; if (rr==l) t=r-l+1; else if (rr>=l&&rr<r) t=r-rr; else t=r-l; if (t&1) printf("1 "); else printf("0 "); } else { int t=0; if (ll==r-1) t=r-l+1; else if (ll>=l&&ll<r) t=ll-l+1; else t=r-l; if (t&1) printf("1 "); else printf("0 "); } } } } return 0; }