📝 核心思路

考虑回文串,单个数也是一个回文串
所以不管数字怎么排列,都能保证mex>=1,那我们只要考虑有没有mex大于1的回文串,那也就是考虑0的位置
因为有两个0,我们考虑三种情况:
1.0作为中心,双指针从两边出去,找回文串 因为有两个0 所以这有两种情况
2.两个0作为一对,首先保证两个0 之间的数是回文串,然后双指针从两边出去找回文串。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
    int n;
    cin>>n;
    vector<int> a(2*n);
    int pos1=-1;
    int pos2=-1;
    for(int i=0;i<2*n;i++){
        cin>>a[i];
        if(a[i]==0){
            if(pos1==-1) pos1=i;
            else pos2=i;
        }
    }

    vector<bool> vis(n+1,false);
    vis[0]=true;
    int ans=1;
    
    // 0作为中心;
    int l=pos1-1,r=pos1+1;
    int mex=1;
    while(l>=0 && r<2*n && a[l]==a[r]){
        vis[a[l]]=true;
        while(vis[mex]) mex++;
        l--;
        r++;
    }
    ans=max(ans,mex);

    vis.assign(n+1,false);
    l=pos2-1,r=pos2+1;
    mex=1;
    while(l>=0 && r<2*n && a[l]==a[r]){
        vis[a[l]]=true;
        while(vis[mex]) mex++;
        l--;
        r++;
    }
    ans=max(ans,mex);

    // 0作为一对
    vis.assign(n+1,false);
    mex-1;
    l=pos1+1,r=pos2-1;
    bool T=true;
    while(l<pos2 && r>pos1){
        if(a[l]!=a[r]){
            T=false;
            break;
        }
        vis[a[l]]=true;
        l++;
        r--;
    }
    if(T){
        while(vis[mex]) mex++;
        l=pos1-1;
        r=pos2+1;
        while(l>=0 && r<2*n && a[l]==a[r]){
            vis[a[l]]=true;
            while(vis[mex]) mex++;
            l--;
            r++;
        }
    }
    ans=max(ans,mex);
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ttt=1;
    cin>>ttt;
    while(ttt--){
        solve();
    }   
    //solve();
    return 0;
}