CF2162F题解

PenguinJ · 2025-11-12 21:54:31 · 题解

题目大意

给定正整数 n 和 m，和 m 个区间。要求构造一个 0 到 n-1 的排列，一个区间的代价为区间内所有数的 mex ，排列的代价为所有区间代价的 mex，最小化排列的代价。3\leq n \leq 3000,1 \leq m \leq 3000。

一个集合的 mex 指未出现在该集合中的最小非负整数。

思路

假如某个位置能被所有区间包含，在该位置填 0，则所有区间的代价 \geq 1，排列的代价为 0。

否则一定有区间不含 0，使其代价为 0，最终排列的价值 \geq 1。

若存在某个位置未被任何区间包含，在该位置填 0 ，最终的的答案为 1。

否则，考虑填 0 的位置，对于所有包含这个位置的区间，如果还存在一位置也同时被这些区间包含，在该位置填 1，这样构造可使最终答案为 1；如果不存在，只要满足排列中 2 在 0 和 1 之间，其它随便填即可。

代码

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