欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

B. Applejack and Storages(模拟)

程序员文章站 2022-04-16 22:24:04
有 n 条边,给出对应的长度,有 m 次询问,每次会 ‘+’:添加一根木棒,或 ‘-’:减少一根木棒,问是否可以组成一个正方形和一个长方形,这两个四边形不可以重合,减少时,保证一定拥有这种长度的木棒一开始以为是到水题,开始暴力,期间穿插了能想到的优化,但 T 到我怀疑人生后,发觉这个题不大对头,开始换思路超时代码:const int N=2e5+5; int n,m,t; int i,j,k; int a[N]; map

 B. Applejack and Storages(模拟)

B. Applejack and Storages(模拟) 

有 n 条边,给出对应的长度,有 m 次询问,每次会 ‘+’:添加一根木棒,或 ‘-’:减少一根木棒,问是否可以组成一个正方形和一个长方形,这两个四边形不可以重合,减少时,保证一定拥有这种长度的木棒 

一开始以为是到水题,开始暴力,期间穿插了能想到的优化,但 T 到我怀疑人生后,发觉这个题不大对头,开始换思路  

超时代码: 

const int N=2e5+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];
    map<int,int> mp;
    int minn,maxx;
int go()
{
    int f4=0;
    int f2=0;
    for(int i=minn;i<=maxx;i++){
        if(mp[i]>=4){
            if(mp[i]>=6){
                int res=mp[i]/4;
                f4+=res;
                if(mp[i]-res*4>=2) f2++;
            }
            else f4++;
        }
        else if(mp[i]>=2) f2++;
        if(f4 && f2>=2) return 1;
        if(f4>=2) return 1;
    }
    if(f4 && f2>=2) return 1;
    if(f4>=2) return 1;
    return 0;
}
int ans;
void print()
{
    if(ans==1) puts("YES");
    else puts("NO");
}
int main()
{
    //IOS;
    while(~sd(n)){
        mp.clear();
        minn=inf;
        maxx=0;
        for(i=1;i<=n;i++){
            sd(a[i]),mp[a[i]]++;
            maxx=max(maxx,a[i]);
            minn=min(minn,a[i]);
        }
        sd(m);
        ans=-1;
        while(m--){
            char ch[3];
            ss(ch);
            int x;
            sd(x);
            if(ch[0]=='+'){
                mp[x]++;
                minn=min(minn,x);
                maxx=max(maxx,x);
                if(ans==1){ puts("YES"); continue; }
                if(mp[x]==1 || mp[x]==3){ print(); continue; }
            }
            else{
                mp[x]--;
                if(mp[x]==0){
                    if(minn==x) for(i=minn;i<=maxx;i++) if(mp[i]) minn=i;
                    if(maxx==x) for(i=maxx;i>=minn;i--) if(mp[i]) maxx=i;
                }
                if(ans==0){ puts("NO"); continue; }
                if(mp[x]==0 || mp[x]==2){ print(); continue; }
            }
            //dbg(mp[x]);
            ans=go();
            print();
        }
    }
    //PAUSE;
    return 0;
}

AC 代码 :

const int N=2e5+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];
    map<int,int> mp;

int main()
{
    //IOS;
    while(~sd(n)){
        mp.clear();
        int f2=0,f4=0;
        for(i=1;i<=n;i++){
            sd(a[i]);
            mp[a[i]]++;
            if(mp[a[i]]==4) f4++,mp[a[i]]=0;
            if(mp[a[i]]==2) f2++;
        }
        sd(m);
        while(m--){
            char ch[3];
            int x;
            ss(ch);
            sd(x);
            if(ch[0]=='+'){
                mp[x]++;
                if(mp[x]==4) f4++,mp[x]=0;
                if(mp[x]==2) f2++;
            }
            else{
                mp[x]--;
                if(mp[x]==-1) mp[x]=3;
                if(mp[x]==3) f4--;
                if(mp[x]==1) f2--;
            }
            if(f4>=2 || (f4==1 && f2>2)) puts("YES");
            else puts("NO");
        }
    }
    //PAUSE;
    return 0;
}

 

本文地址:https://blog.csdn.net/C_Dreamy/article/details/107874417

相关标签: CF