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

CPP

#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;
}

题解：CF2053B Outstanding Impressionist

文章操作

CF2053B Outstanding Impressionist

分析

AC CODE

相关推荐

评论

题解：CF2053B Outstanding Impressionist