题解归档 - cf2236E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2236E
• 本地来源：problems/cf2236E/idea.md
• 题目链接：https://codeforces.com/contest/2236/problem/E
• 原始标题：cf2236E Friendly Gifts

思路

cf2236E Friendly Gifts

题意

给定长度 n 的数组 a。选两个不相交、等长的子段，各自重排后需为「好数组」（相邻差为 1 的连续整数）；两段拼接后整体重排也必须是好数组。求最大长度。

关键观察

• 长度为 L 的好数组，其 multiset 必须是 L 个互异且连续的整数。
• 两段各长 L，若拼接后长 2L 且为好数组，则两段数值集合必为 {x,…,x+L-1} 与 {x+L,…,x+2L-1}（两段 min 相差 L）。

做法

1. 预处理所有 [l,r] 是否为好数组；若是，记录它的最小值。
2. 从大到小枚举 L ∈ [1, n/2]。
3. 把所有长度为 L 的好子段按最小值放入 map<min,set<start>>。
4. 对每个最小值 x，只需要找 x-L 或 x+L 的桶；在桶内用 lower_bound 检查是否有起点与当前子段不重叠。

复杂度：预处理 O(n²)，所有长度的桶检查总计 O(n² log n)，n≤6000 可过。

样例

[2,1,4,3]：取 [2,1] 与 [4,3]，各自为 {1,2}、{3,4}，拼接为 {1,2,3,4}，答案 2。

实现注意

• a_i<=n，每个左端点重置一次频率数组即可。
• set 里存起点，检查右侧不重叠用 lower_bound(s+L)，左侧不重叠用 upper_bound(s-L) 后退一位。

代码

来源：problems/cf2236E/solution.cpp

/* Author: likely
 * Time: 2026-06-19 12:56:58
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=6005;
int a[maxn],freq[maxn],mnSeg[maxn][maxn];
map<int,set<int>>buck;
int main(){
    int t,n,i,j,L,ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++) mnSeg[i][j]=0;
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++) freq[j]=0;
            int distinct=0,mn=0,mx=0;
            for(j=i;j<=n;j++){
                if(!freq[a[j]]){
                    distinct++;
                    if(!mn or a[j]<mn) mn=a[j];
                    if(a[j]>mx) mx=a[j];
                }
                freq[a[j]]++;
                if(distinct==j-i+1 and mx-mn+1==j-i+1) mnSeg[i][j]=mn;
            }
        }
        ans=0;
        for(L=n/2;L>=1;L--){
            buck.clear();
            for(i=1;i+L-1<=n;i++){
                if(mnSeg[i][i+L-1]) buck[mnSeg[i][i+L-1]].insert(i);
            }
            bool ok=false;
            for(auto &p:buck){
                int x=p.first;
                for(int y:{x-L,x+L}){
                    if(y<1 or !buck.count(y)) continue;
                    set<int>&st=buck[y];
                    for(int s:p.second){
                        auto it=st.lower_bound(s+L);
                        if(it!=st.end()){
                            ok=true;
                            break;
                        }
                        it=st.upper_bound(s-L);
                        if(it!=st.begin()){
                            --it;
                            if(*it+L<=s){
                                ok=true;
                                break;
                            }
                        }
                    }
                    if(ok) break;
                }
                if(ok) break;
            }
            if(ok){
                ans=L;
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}