hdu 5929 CCPC东北四省赛H - Basic Data Structure

题意：

定义一个可以反转栈顶的栈，有push，pop操作，每次push只push 0,1这两种元素，除此之外还有reverse操作，即把栈顶反转为栈尾， 栈尾反转为栈顶，另外有一个query操作，查询的是从栈顶到栈尾的元素进行一种nand运算所得到的值，nand运算其实就是&&运算的非，具体规则如下：

∙ 0 nand 0 = 1 ∙ 0 nand 1 = 1 ∙ 1 nand 0 = 1 ∙ 1 nand 1 = 0

解题思路：

暴力的去查询肯定要t，观察这种运算的规律，任何数和0运算的结果都是1，所以对于查询的结果，我们考虑最后一个0出现的位置，从栈顶到这个0元素运算得到的结果一定都是1，而0之后的元素就都是1了，1nand1为0,1nand1nand1为1，我们可以得到偶数个1nand运算后是0， 奇数个1nand运算后是1,所以整个栈元素的nand值只要在知道最后一个0所在的位置，我们就可以求出了结果了。

代码：

#include <bits/stdc++.h>using namespace std;int a[410004];int nand[410004];int zero[410005];int main(){   int t;   int e=1;   cin>>t;   while(t--)   {    int n;    scanf("%d", &n);    int i, j;    //memset(nand, 0, sizeof(nand));    //memset(zero, 0, sizeof(zero));    int head, tail;    head=tail=200005;     int p=1;    int isfirst=1, x;    char oper[33];    PRintf("Case #%d:/n", e++);    int l, r;    l=r=200005;//    l=r=0;     for(i=0; i<n; i++)    {          //printf("%d %d/n", head, tail);      scanf("%s", oper);     if(strcmp(oper, "PUSH")==0)     {       if(p)       {	 scanf("%d", &x);    	 a[head--]=x;	 if(isfirst)	 {	    isfirst=0;	    tail++;//	    nand[i]=x;            if(x==0)zero[l--]=head+1, r++;	    continue;	 }         if(x==0) { zero[l--]=head+1;if(l+1==r)r++;};       }       else       {         scanf("%d", &x);	 a[tail++]=x;	if(isfirst)	{	   isfirst=0;	   head--;	   if(x==0) zero[r++]=tail-1, l--;	   continue;	}	          if(x==0){zero[r++]=tail-1;if((r-1)==l)l--;}       }     }     if(strcmp(oper, "POP")==0)     {	if(p)	{	   head++;	   if(a[head]==0)	   {	     l++;	   }	}	else	{	   tail--;	//   cout<<a[tail]<<endl;	   if(a[tail]==0)	   {	      r--;	   }	}     }     if(strcmp(oper, "REVERSE")==0){ p=!p;}      if(strcmp(oper, "QUERY")==0)     {	if(isfirst || head==(tail-1))printf("Invalid./n");	else 	{          if(p)	  {	     if(r-l>1)	     {	//	cout<<zero[r-1]<<endl; 		if((tail-zero[r-1])%2==1) 		{		   nand[i]=1;		}	        else		{		   nand[i]=0;		}	        if(zero[r-1]==head+1)nand[i]=!nand[i];		    }	     else	     {	//	cout<<r<<" "<<l<<endl;                if((tail-head-1)%2==1)nand[i]=1;		else nand[i]=0;	     }	  }	  else	  {	      if((r-l)>1)	      {                if((zero[l+1]-head)%2==1)		{ 		  nand[i]=1; 		}else		{		   nand[i]=0;		}		if(zero[l+1]==tail-1)nand[i]=!nand[i];	      }else	      { 		if((tail-head-1)%2==1)nand[i]=1;		else nand[i]=0;	      }	  }	  printf("%d/n", nand[i]);	}     }    }    }   }