专栏文章

题解：CF2162H Beautiful Problem

zzxh923
CF2162H题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mineb3ad
此快照首次捕获于
2025/12/02 01:00
3 个月前
此快照最后确认于
2025/12/02 01:00
3 个月前
查看原文

思路

若一个区间被另一个区间完全包含，则这个区间没有任何作用，我们可以去掉它，这是不难发现的。
首先发现对于一个 xx，这个式子的要求就是给出某些区间，这个区间里的数要么都 ≤x\le x，要么都 ≥x\ge x。
我们定义一个所有数都 ≤x\le x 为小区间，所有数都 ≥x\ge x 的大区间。
然后对于一个位置，有 44 种可能。分别是只被小区间覆盖，只被大区间覆盖，同时被两种区间覆盖，不被任何区间覆盖。
我们先考虑没有第 44 种位置的做法。
假设现在有 aa 个比 xx 小的数，bb 个比 xx 大的数，然后我们要求有 p1p_1 个位置为类型 11，p2p_2 个位置为类型 22，剩下的位置都是类型 33。
那么当且仅当 a≤p1,b≤p2a\le p_1,b\le p_2 的时候是可行的。因为比方说 a>p1a>p_1 了，那么剩下的 <x<x 的数你没有地方放，因为类型 33 的位置必须放 xx。
那么现在加上类型 44 的位置，设它有 p4p_4 个，那么要求就变为了 max⁡(0,a−p1)+max⁡(0,b−p2)≤p4\max(0,a-p_1)+\max(0,b-p_2)\le p_4 才可行。这相当于把多出来的数放在没有任何要求的位置上。
所以说，我们希望在 p1p_1 确定时，p2p_2 尽可能大。于是设 fi,j,0/1f_{i,j,0/1} 表示前 ii 个区间，已经有 jj 个位置为类型 11，最后一个区间是大区间还是小区间时，最多能有多少个位置为类型 22。
但是你发现有可能 ii 区间和 i−2i-2 区间可能也有交，那我这样 dp 不就错了吗？但是注意到这种情况下，如果你中间的颜色和两端的不同，那把这个 i−2,i−1,ii-2,i-1,i 这三个区间弄成同一种一定不劣。也就是说，不合法状态一定不优，会被覆盖掉，所以不需要管这种情况。
然后直接用上面的方法对于每个 xx 进行判断即可。

代码

CPP
#include<bits/stdc++.h>
#define int long long
#define N 2005
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
#define pct __builtin_popcount
#define mpi make_pair
#define inf 2e18
using namespace std;
int T=1,n,m,cnt,a[N],f[N][N][2];
pii b[N];
bool st[N];
void solve(int cs){
    if(!cs)return;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	st[i]=0;
	}
	for(int i=1;i<=m;i++){
		cin>>b[i].x>>b[i].y;
	}
	sort(b+1,b+m+1);
	cnt=0;
	int mx=0;
	for(int i=1;i<=m;i++){
		if(mx>=b[i].y)continue;
		mx=max(mx,b[i].y);
		b[++cnt]=b[i];
	}
	m=cnt;
	int free=0;
	for(int i=1;i<=m;i++){
		for(int j=b[i].x;j<=b[i].y;j++){
			st[j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		if(!st[i])free++;
	}
	for(int j=0;j<=n;j++){
		f[1][j][0]=f[1][j][1]=-inf;
	}
	f[1][0][0]=b[1].y-b[1].x+1;
	f[1][b[1].y-b[1].x+1][1]=0;
	for(int i=2;i<=m;i++){
		int len=b[i].y-b[i].x+1;
		int cap=0;
		if(b[i-1].y>=b[i].x)cap=b[i-1].y-b[i].x+1;
		for(int j=0;j<=n;j++){
			f[i][j][0]=f[i][j][1]=-inf;
		}
		for(int j=0;j<=n;j++){
			int &v0=f[i][j][0],&v1=f[i][j][1];
			v0=max(v0,f[i-1][j][0]+len-cap);
			if(j+cap<=n)v0=max(v0,f[i-1][j+cap][1]+len-cap);
			if(j>=len-cap)v1=max(v1,f[i-1][j-(len-cap)][0]-cap);
			if(j>=len-cap)v1=max(v1,f[i-1][j-(len-cap)][1]);
		}
	}
	for(int x=1;x<=n;x++){
		int s=0,b=0;
		for(int i=1;i<=n;i++){
			if(a[i]<x)s++;
			if(a[i]>x)b++;
		}
		bool flag=0;
		for(int i=0;i<=n;i++){
			int t1=max(0ll,s-i),t2=max(0ll,b-max(f[m][i][0],f[m][i][1]));
			if(t1+t2<=free){
				flag=1;
				break;
			}
		}
		cout<<flag;
	}
	cout<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
//	init(1e5);
	for(int cs=1;cs<=T;cs++){
		solve(cs);
	}
    // cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...