题解 P1503 【鬼子进村】

· · 题解

一道简单的模拟

思路：标记+STL栈

题目大意：

有n个房子，有m个消息，

每一个消息有三种类型：

解决：

显然，对于任意一种房子，都有两个状态：1.摧毁 2.未被摧毁

所以，便可设立一个布尔类型的open[]数组，记录每个房子的状态

但是，关于第二种操作，它涉及到了上一次，

也就是说，要记录被摧毁的房子的顺序，

用STL里的栈呀！

每一次修复的房子都为栈顶的所记录的编号

类似的，每当摧毁一个房子，都要将这个房子的编号进栈

而对于每一次询问

便可做一下for循环，来看看可以到达左右两侧的多少个房子

但要先做一下特判：判断第x个房子是否已被摧毁

若以摧毁就直接输出0就好了

但是

若依此思路的话，您就会TLE第2个点......只能说出题人太毒瘤

而我们发现，T的原因是因为在询问时所耗的时间太多

看一下数据：*1<=n,m<=510^4**

若第一次消息就是一个询问......

所以，就又用到了一个特判：

每当进行一次询问，若栈为空（就是没有房子被摧毁）,输出n

就这样，便愉快的AC了第二个点却卡了我好长时间

上代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
const int MAXN=50010;
int x,n,m;//n个房子，m条消息 
char c;//读入时要用 
stack<int>st;//来记录房子被摧毁的顺序 
bool open[MAXN];//标记一个房子的状态 
inline int read()//快读 
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
int main()
{
    n=read(),m=read();
    fill(open+1,open+1+n,1);
    //和memset没大区别，可供装*用 
    while(m--)
    {
        cin>>c;
        scanf("%d",&x);
        if(c=='D') open[x]=0,st.push(x);//摧毁一个房子：1.标记 2.push到栈里 
        if(c=='R') open[st.top()]=1,st.pop();//修复：1.标记 2.pop一下 
        if(c=='Q')
        {
            int ans=1;//初值为1，因为第x个房子本身也算一个 
            if(!open[x])//若第x个房子已被摧毁 
            {
                printf("0\n");//直接输出0 
                continue;
            }
            if(st.empty())//若没有房子被摧毁 
            {
                printf("%d\n",n);//直接输出n 
                continue;
            }
            for(register int i=x-1;i>=1;i--)//循环左边 
            {
                if(open[i]) ans++;
                else break;
            }
            for(register int i=x+1;i<=n;i++)//循环右边 
            {
                if(open[i]) ans++;
                else break;
            }
            printf("%d\n",ans);
        }
    }
}

这世界上不是没有水题，而是缺少发现水题的眼睛

看我写的这么认真，是否可以给我点个赞再走呢？