题解：CF2053B Outstanding Impressionist

lalaji2010 · 2024-12-29 17:10:39 · 题解

CF2053B Outstanding Impressionist

分析

对于第 i 个位置，我们可以选择将其设置为 [l_i,r_i] 区间中的任意一个数字，我们想要让其他的位置都不设置为当前位置 i 设置的数，看是否可行。

显然，当前位置 i 不可行当且仅当 [l_i,r_i] 中的每一个数字，都有至少一个其他的位置必须填；即 \forall j \in [l_i,r_i]，存在一个位置 k，满足 1 \leq k \leq n,k \neq i,l_k=r_k=j。

然后我们对于每一个形如 l_x=r_x 的限制进行标记，令 d[l_x]=1，令 c[l_x] 自增 1，然后前缀和处理就能在后面对于每一个位置的取值区间 O(1) 地来判断区间中的数字是否都被其他位置必须填。特别地，若某一个位置 i 满足 l_i=r_i，则特殊处理，判断 c[l_i] 是否大于等于 2 即可。

记得数组用多少清多少，不要使用 memset。

代码是赛时写的，有点丑，见谅。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int t;
int n,a[200005],b[200005],c[500005],d[500005];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int mx=0;
        for(int i=0;i<=2*n;i++){
            c[i]=0;
            d[i]=0;
        } 
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
            if(a[i]==b[i]){
                d[a[i]]=1;
                c[a[i]]++;
                mx=max(mx,a[i]);
            }
        }
        for(int i=1;i<=mx;i++){
            c[i]=c[i-1]+c[i];
            d[i]=d[i-1]+d[i];
        }
        for(int i=1;i<=n;i++){
            if((a[i]!=b[i]&&d[b[i]]-d[a[i]-1]>=b[i]-a[i]+1)||(a[i]==b[i]&&c[b[i]]-c[a[i]-1]-1>=b[i]-a[i]+1)) cout<<0;
            else cout<<1;
        }
        puts("");
    }
    return 0;
}