专栏文章

CF2162F题解

PPenguinJ
CF2162F题解参与者 1已保存评论 0

文章操作

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

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

题目大意

给定正整数 nn 和 mm，和 mm 个区间。要求构造一个 00 到 n−1n-1 的排列，一个区间的代价为区间内所有数的 mexmex ，排列的代价为所有区间代价的 mexmex，最小化排列的代价。3≤n≤3000,1≤m≤30003\leq n \leq 3000,1 \leq m \leq 3000。
一个集合的 mexmex 指未出现在该集合中的最小非负整数。

思路

假如某个位置能被所有区间包含，在该位置填 00，则所有区间的代价 ≥1\geq 1，排列的代价为 00。
否则一定有区间不含 00，使其代价为 00，最终排列的价值 ≥1\geq 1。
若存在某个位置未被任何区间包含，在该位置填 00 ，最终的的答案为 11。
否则，考虑填 00 的位置，对于所有包含这个位置的区间，如果还存在一位置也同时被这些区间包含，在该位置填 11，这样构造可使最终答案为 11；如果不存在，只要满足排列中 22 在 00 和 11 之间，其它随便填即可。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T,n,m,ans,pos_0,pos_1;
struct Node{
	int l,r;
}a[3001];
vector<Node>st;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			cin>>a[i].l>>a[i].r;
		}
		ans=2;
		for(int i=1;i<=n;i++){
			bool ok_all=1;
			for(int j=1;j<=m;j++){
				if(a[j].r<i||a[j].l>i)ok_all=0;
			}
			if(ok_all){
				ans=0,pos_0=i;
				break;
			}
		}
		if(ans==0){
			for(int i=1,j=1;i<=n;i++){
				if(i==pos_0)cout<<"0 ";
				else cout<<j++<<" ";
			}
			cout<<"\n";
			continue;
		}
		for(int i=1;i<=n;i++){
			bool ok_none=1;
			for(int j=1;j<=m;j++){
				if(a[j].r>=i&&a[j].l<=i)ok_none=0;
			}
			if(ok_none){
				ans=1,pos_0=i;
				break;
			}
		}
		if(ans==1){
			for(int i=1,j=1;i<=n;i++){
				if(i==pos_0)cout<<"0 ";
				else cout<<j++<<" ";
			}
			cout<<"\n";
			continue;
		}
		for(int i=1;i<=n;i++){
			st.clear();
			for(int j=1;j<=m;j++){
				if(a[j].r>=i&&a[j].l<=i)st.push_back(a[j]);
			}
			bool ok_l=1,ok_r=1;
			if(i==1)ok_l=0;
			if(i==n)ok_r=0;
			for(auto[l,r]:st){
				if(ok_l){
					if(r<i-1||l>i-1)ok_l=0;
				}
				if(ok_r){
					if(r<i+1||l>i+1)ok_r=0;
				}
			}
			if(ok_l){
				ans=1;
				pos_1=i-1,pos_0=i;
				break;
			}
			if(ok_r){
				ans=1;
				pos_1=i+1,pos_0=i;
				break;
			}
		}
		if(ans==1){
			for(int i=1,j=2;i<=n;i++){
				if(i==pos_0)cout<<"0 ";
				else if(i==pos_1)cout<<"1 ";
				else cout<<j++<<" ";
			}
			cout<<"\n";
			continue;
		}
		cout<<"0 ";
		for(int i=3;i<=n;i++)cout<<i-1<<" ";
		cout<<1<<"\n";
	}
	return 0;
}

评论

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

正在加载评论...