Codeforces Round 703 (Div. 2) A-D

EdGrass / 2023-05-18 / 原文

Codeforces Round 703 (Div. 2)

A. Shifting Stacks

int a[N];
void solve(){
    int n=read(),ans=1;
    for(int i=1;i<=n;i++)a[i]=read();
    int rest=0,last=-1;
    for(int i=1;i<=n;i++){
        a[i]+=rest;
        rest=a[i]-last-1;
        last++;
        if(rest<0){
            ans=0;
            break;
        }
    }  
    puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Eastern Exhibition

int x[N],y[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        x[i]=read(),y[i]=read();
    }
    if(n%2){
        cout<<1<<'\n';
        return ;
    }
    sort(x+1,x+1+n);sort(y+1,y+1+n);
    cout<<(x[n/2+1]-x[n/2]+1)*(y[n/2+1]-y[n/2]+1)<<'\n';
    
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C1&&C2. Guessing the Greatest

这题很明显需要通过第二大的值的位置来找最大值

先询问整体的第二大值然后通过询问知道最大值在第二大值的哪一边

然后二分这一边即可

注意：询问的时候注意l,r不能相等需要一些特判

int ask(int l,int r){
    cout<<"? "<<l<<" "<<r<<endl;
    return read(); 
}
void solve(){
    int n=read(),l=1,r=n;
    while(l<r){
        int secpoi=ask(l,r);
        int left=0;
        if(secpoi==n||(secpoi!=1&&secpoi==ask(1,secpoi)))left=1,r=secpoi-1;
        else l=secpoi+1;
        if(left==1){
            while(l+1<r){
                int mid=l+r>>1;
                if(ask(mid,secpoi)==secpoi) l=mid;
                else {
                    r=mid-1;
                }
            }
        }else {
            while(l+1<r){
                int mid=l+r>>1;
                if(ask(secpoi,mid)==secpoi) r=mid;
                else {
                    l=mid+1;
                }
            }
        }
        if(l+1==r){
            if(l==secpoi){l=r;
                break;}
            else if(r==secpoi){ r=l;
                break;}
        }
        if(l+1==r){
           int p=ask(l,r);
            if(l==p)l=r;
            else if(r==p) r=l;
        }
        
    }
    cout<<"! "<<l<<endl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D. Max Median

明显的答案具有二分性所有选择二分答案

将mid小的值赋值为-1 比mid大的值赋值为1

然后求前缀和和前缀最小值如果前缀和减去前缀最小值大于0 说明是可行的

因为前缀最小值代表了前面有几个数小于mid 前缀和则是代表了有x个数大于等于mid 相减就去除了之前的数组造成的影响

int a[N],b[N],sum[N],minn[N],n,m;
bool check(int x) {
    for(int i=1;i<=n;i++)b[i]=(a[i]>=x?1:-1);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i],minn[i]=min(minn[i-1],sum[i]);
    for(int i=m;i<=n;i++)if(sum[i]-minn[i-m]>0)return true;
    return false;
}
int bs2(int l, int r){ 
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
void solve(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    cout<<bs2(1,n)<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}