HDU 5929 Basic Data Structure（模拟 + 乱搞）题解

题意：给定一种二进制操作nand，为

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

现在要你模拟一个队列，实现PUSH x 往队头塞入x，POP队尾退出，REVERSE翻转，QUERY询问队头到队尾的nand和。

思路：其他都可以模拟，但是n为2e5，如果直接求nand和必超时，找规律可得，任何串和0nand都为1，那么我们维护一个双端队列保存0出现的位置，然后每次就计算离队尾最近的0和队尾间有几个1。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int seed = ;

const ll MOD = ;

const int INF = 0x3f3f3f3f;

deque<int> q;   //

int main(){

    int t, x, l, r, ca = , cnt;

    char order[];

    scanf("%d", &t);

    while(t--){

        printf("Case #%d:\n", ca++);

        int n;

        int turn = ;

        cnt = ;

        l = , r = -;

        while(!q.empty()) q.pop_back();

        scanf("%d", &n);

        while(n--){

            scanf("%s", order);

            if(order[] == 'S'){    //push

                scanf("%d", &x);

                if(turn){

                    cnt++;

                    r++;

                    if(x == ) q.push_back(r);

                }

                else{

                    cnt++;

                    l--;

                    if(x == ) q.push_front(l);

                }

            }

            else if(order[] == 'P'){   //pop

                if(turn){

                    if(!q.empty() && q.back() == r) q.pop_back();

                    r--;

                }

                else{

                    if(!q.empty() && q.front() == l) q.pop_front();

                    l++;

                }

                cnt--;

            }

            else if(order[] == 'V'){   //reverse

                turn ^= ;

            }

            else{   //query

                int ans;

                if(cnt == ) printf("Invalid.\n");

                else{

                    if(q.empty()) ans = (r - l + ) % ;

                    else{

                        if(turn)

                            ans = (q.front() - l +  - (q.front() == r)) % ;

                        else

                            ans = (r - q.back() +  - (q.back() == l)) % ;

                    }

                    printf("%d\n", ans);

                }

            }

        }

    }

    return ;

}

巴特西

HDU 5929 Basic Data Structure（模拟 + 乱搞）题解

最新文章

热门文章