题解：P16323 【MX-J29-T2】区间选取

lucasaa · 2026-04-21 21:24:42 · 题解

水题。每个数可以不动或者 +1，相当于每个 a_i 都能管住 \{a_i, a_i+1\} 这两个值。 我们可以把值域切成一段一段的，相邻两段中间差 \ge 3 就断开，这样每段内部互不干扰。然后在这段里跑个 DP：dp_{i,0/1} 表示走到值 i 时，我是「必须用 i+1 接着走」还是「手头有多个 i 可以原地耗着」。转移就按 cnt_i 的情况来：要是压根没有 i 那就断了；要是有 \ge 2 个 i 就能维持状态 1 继续苟。最后扫一遍所有起点，看看能跑多远，取个最大值就完事了。复杂度 O(n\log n)，注意 \sum n\le 2\times 10^6。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int c,t;
    cin>>c>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int>a(n);
        for(int i=0;i<n;++i){
            cin>>a[i];
        }
        sort(a.begin(),a.end());
        vector<pair<int,int>>vals;
        for(int i=0;i<n;){
            int j=i;
            while(j<n&&a[j]==a[i])++j;
            vals.emplace_back(a[i],j-i);
            i=j;
        }
        vector<int>u;
        for(auto&p:vals){
            int v=p.first;
            if(v>1)u.push_back(v-1);
            u.push_back(v);
            u.push_back(v+1);
        }
        sort(u.begin(),u.end());
        u.erase(unique(u.begin(),u.end()),u.end());
        int ans=0;
        int m_u=u.size();
        int seg_start=0;
        for(int i=1;i<=m_u;++i){
            if(i==m_u||u[i]-u[i-1]>=3){
                int start=u[seg_start];
                int end=u[i-1];
                int len=end-start+1;
                vector<int>cnt(len,0);
                for(auto&p:vals){
                    int v=p.first;
                    if(v>=start&&v<=end){
                        cnt[v-start]=p.second;
                    }
                }
                vector<int>dp0(len),dp1(len);
                for(int i=len-1;i>=0;--i){
                    {
                        int nxt_state;
                        if(cnt[i]==0)nxt_state=0;
                        else nxt_state=1;
                        if(i==len-1)dp1[i]=i;
                        else dp1[i]=(nxt_state==0?dp0[i+1]:dp1[i+1]);
                    }
                    {
                        bool ok=true;
                        int nxt_state;
                        if(cnt[i]==0)ok=false;
                        else if(cnt[i]==1)nxt_state=0;
                        else nxt_state=1;
                        if(!ok)dp0[i]=i-1;
                        else if(i==len-1)dp0[i]=i;
                        else dp0[i]=(nxt_state==0?dp0[i+1]:dp1[i+1]);
                    }
                }
                for(int L_idx=0;L_idx<len;++L_idx){
                    int init_state=(L_idx>0&&cnt[L_idx-1]>0)?1:0;
                    int R_idx=(init_state==0?dp0[L_idx]:dp1[L_idx]);
                    if(R_idx>=L_idx){
                        int cur_len=R_idx-L_idx+1;
                        if(cur_len>ans)ans=cur_len;
                    }
                }

                seg_start=i;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}