首页 > 代码库 > 2016CCPC东北地区大学生程序设计竞赛 - 重现赛 1008

2016CCPC东北地区大学生程序设计竞赛 - 重现赛 1008

2024-08-15 19:42:16   218人阅读

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

题意：给你一种数据结构以及操作，和一种位运算，最后询问：从‘栈’顶到低的运算顺序结果是多少

解法：根据位运算，发现出现0，结果就是1，那么就记录两端0的位置就好，中间不管出现什么，结果大部分都是1，考虑还有反转操作，使用双端队列，用flag标记反转后的情况，然后根据需要添加元素记录位置，最后根据标记，出现元素等进行讨论计算

#include <iostream>#include <deque>#include <string>#include <cstring>#include <stdio.h>using namespace std;int a[600005];int main(){    int T;    deque<int>d;    char s[20];    scanf("%d",&T);    for(int xx=1;xx<=T;xx++){        d.clear();        int n,flag=1,x,l=300000-1,r=300000;        scanf("%d",&n);        printf("Case #%d:\n",xx);        while(n--){            scanf("%s",s);            if(s[0]==‘R‘) flag^=1;            if(s[1]==‘O‘){                if(flag){                    r--;                    if(a[r]==0) d.pop_back();                }                else{                    l++;                    if(a[l]==0) d.pop_front();                }            }            if(s[2]==‘S‘){                scanf("%d",&x);                if(flag){                    a[r]=x;                    if(x==0) d.push_back(r);                    r++;                }                else{                    a[l]=x;                    if(x==0) d.push_front(l);                    l--;                }            }            if(s[0]==‘Q‘){                if(l==r-1) printf("Invalid.\n");                else if(d.empty()) printf("%d\n",(r-l-1)%2);                else{                    int num=0;                    if(!flag){                        int y=d.back();                        num+=(y!=l+1)+r-y-1;                    }                    else{                        int y=d.front();                        num+=(y!=r-1)+y-l-1;                    }                    printf("%d\n",num%2);                }            }        }    }    return 0;}

　　

2016CCPC东北地区大学生程序设计竞赛 - 重现赛 1008


联系
我们