洛谷 P1503鬼子进村

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

题目描述

描述县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来

1、消息为D x：鬼子将x号房子摧毁了，地道被堵上。

2、消息为R ：村民们将鬼子上一个摧毁的房子修复了。

3、消息为Q x：有一名士兵被围堵在x号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

输入输出格式

输入格式：

第一行2个整数n，m（n，m<=50000）。

接下来m行，有如题目所说的三种信息共m条。

输出格式：

对于每一个被围堵的士兵，输出该士兵能够到达的房子数。

输入输出样例

输入样例#1：

7 9

D 3

D 6

D 5

Q 4

Q 5

Q 4

Q 4

输出样例#1：

说明

若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。

有人暴力AC！！！

//80‘

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int cnt=;

char s;

int sum;

int xxx[];

int n,m;

int f[]={};

void sousuo2(int a)

{

    if(f[a]||a==) return;

    if(f[a]==)

    {

        sum++;

        sousuo2(--a);

    }

}

void sousuo(int x,int y)

{

    if(f[x]||x>n)

    {

        sousuo2(y-);

        return;

    }

    if(f[x]==)

    {

        sum++;

        sousuo(++x,y);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

        cin>>s;

        if(s=='D')

        {

            scanf("%d",&xxx[++cnt]);

            f[xxx[cnt]]=;

        }

        if(s=='Q')

        {

            int x;

            sum=;

            scanf("%d",&x);

            int y=x;

            if(f[x]==)

                sum=;

            else

                sousuo(x,y);

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

        }

        if(s=='R')

            f[xxx[cnt--]]=;

    }

    return ;

}

//100——by whw

//我太懒了

#include<stack>

#include<cstdio>

#include<iostream>

#include<algorithm>

#define M 50001

using namespace std;

stack<int> q;

bool vis[M];

int tree[M];

int a[M],n,m;

inline int read(int&x) {

    x=;char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c>=''&&c<='') x=*x+c-,c=getchar();

}

int main() {

    read(n);read(m);

    char s;

    int x,bj=,tot=;

    for(int i=;i<=n;i++) vis[i]=true;

    for(int i=;i<=m;i++) {

        cin>>s;

        if(s=='D') {

            read(x);

            q.push(x);

            vis[x]=false;

            a[++tot]=x;

        }

        else if(s=='R') {

            x=q.top();

            q.pop();

            vis[x]=true;

            sort(a+,a+tot+);

            for(int i=;i<=tot;i++)

              if(a[i]==x) {

                  if(a[i]==a[tot]) tot--;

                  else a[i]=a[tot],tot--;

                  break;

              }

        }

        else if(s=='Q') {

            read(x);

            if(!vis[x]) printf("0\n");

            else {

                sort(a+,a+tot+);

                if(x>a[tot]) printf("%d\n",n-a[tot]);

                else for(int i=;i<=tot;i++) {

                    if(a[i]>x) {

                        printf("%d\n",a[i]-a[i-]-);

                        break;

                    }

                }

            }

        }

    }

    return ;

}

巴特西

洛谷 P1503鬼子进村

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章