首页 > 代码库 > [HDOJ5929]Basic Data Structure（双向队列，规律）

[HDOJ5929]Basic Data Structure（双向队列，规律）

2024-08-15 20:21:27   211人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5929

题意：维护一个栈，支持往栈里塞 0/1 ，弹栈顶，翻转栈，询问从栈底到栈顶按顺序 NAND 的值。

题解：只要知道最后的 00 后面 11 的个数的奇偶性就行。可以用链表把所有 00 的位置存下来。

  1 #include <bits/stdc++.h>  2 using namespace std;  3   4 typedef long long LL;  5   6 const int maxn = 866666;  7 int n;  8 int q[maxn], l, r;  9 int ll[maxn], rr[maxn]; 10 int zerol, zeror; 11 char cmd[10]; 12  13 int main() { 14   // freopen("in", "r", stdin); 15   int T, _ = 1; 16   scanf("%d", &T); 17   while(T--) { 18     scanf("%d", &n); 19     l = maxn/2 + 1; r = maxn/2; 20     int x, cur; 21     zerol = zeror = -1; 22     int dir = 0, zero = 0; 23     printf("Case #%d:\n", _++); 24     while(n--) { 25       scanf("%s", cmd); 26       if(strcmp(cmd, "PUSH")==0) { 27         scanf("%d", &x); 28         if(!dir) { 29           q[--l] = x; 30           cur = l; 31         } 32         else { 33           q[++r] = x; 34           cur = r; 35         } 36         if(x == 0) { 37           zero++; 38           if(zero == 1) { 39             zerol = zeror = cur; 40             ll[cur] = rr[cur] = -1; 41           } 42           else { 43             if(!dir) { 44               ll[zerol] = cur; rr[cur] = zerol; 45               ll[cur] = -1; zerol = cur; 46             } 47             else { 48               rr[zeror] = cur; ll[cur] = zeror; 49               rr[cur] = -1; zeror = cur; 50             } 51           } 52         } 53       } 54       if(strcmp(cmd, "POP")==0) { 55         if(!dir) { 56           x = q[l]; 57           cur = l++; 58         } 59         else { 60           x = q[r]; 61           cur = r--; 62         } 63         if(x == 0) { 64           zero--; 65           if(zero == 0) zerol = zeror = -1; 66           else { 67             if(!dir) { 68               ll[rr[cur]] = -1; 69               zerol = rr[cur]; 70             } 71             else { 72               rr[ll[cur]] = -1; 73               zeror = ll[cur]; 74             } 75           } 76         } 77       } 78       else if(strcmp(cmd, "REVERSE")==0) dir ^= 1; 79       else if(strcmp(cmd, "QUERY")==0) { 80         int siz = r - l + 1, one; 81         if(!siz) printf("Invalid.\n"); 82         else { 83           if(!zero) printf("%d\n", siz%2); 84           else { 85             int tmp; 86             if(!dir) { 87               one = r - zeror; 88               tmp = (zeror == l); 89             } 90             else { 91               one = zerol - l; 92               tmp = (zerol == r); 93             } 94             printf("%d\n", one % 2 == tmp); 95           } 96         } 97       } 98     } 99   }100   return 0;101 }

 

[HDOJ5929]Basic Data Structure（双向队列，规律）


联系
我们