LuoguP2161题解

YaliKiWi · 2019-06-06 16:00:17 · 题解

友链(与此题无关)

模拟苟过

随机跳题就找到这道题了...

观察了一下tags：平衡树/树状数组/高精，然后是紫题

我一个蒟蒻就特(bu)别(xiang)慌(da)

所以决定... 打模拟骗分

觉得骗它二三十差不多了，运气好还有五六十

介绍下沙雕思路：

需要用到的变量：

记录当前会议编号

• ans

记录当前幸存(当前有效预约)会议数量

然后...该干嘛干嘛，上fake代码(码风超丑)

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+10
int a[maxn],cnt,n,ans;
bool canc[maxn+maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(register int i=1;i<=n;i++){
        char c;
        cin>>c;
        if(c=='B'){
            cout<<ans<<endl;
        }
        if(c=='A'){
            int x,y,sum=0;
            cin>>x>>y;
            cnt++;//会议编号+1
            ans++;//当前新增加会议为幸存
            for(register int j=x;j<=y;j++){
                if(a[j]){//若当前日期有预约过会议
                    if(canc[a[j]]==0){//且该会议未被取消过
                        ans--;//当前幸存会议数量-1
                        canc[a[j]]=1;//取消该会议
                        sum++;//因当前会议需要而取消的会议个数+1
                    }
                }
                a[j]=cnt;//当前日期被当前会议占用
            }
            cout<<sum<<endl;
        }
    }
    return 0;
}

这个居然有80-90！(测了两次，看运气)

玄学优化即将来临！(自己找不同吖)

然鹅这是并没有正确性的

虽然可以过

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+10
int a[maxn],cnt,n,ans;
bool canc[maxn+maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(register int i=1;i<=n;i++){
        char c;
        cin>>c;
        if(c=='B'){
            cout<<ans<<endl;
        }
        if(c=='A'){
            int x,y,sum=0;
            cin>>x>>y;
            cnt++;
            ans++;
            for(register int i=x;i<=y;i++){
                if(a[i]){
                    if(canc[a[i]]==0){
                        ans--;
                        canc[a[i]]=1;
                        sum++;
                    }
                }
                a[i]=cnt;
            }
            cout<<sum<<endl;
        }
    }
    return 0;
}

所以这是一篇鸡肋题解

本题解仅供娱乐