[CF2227D]
📝 核心思路 考虑回文串,单个数也是一个回文串 所以不管数字怎么排列,都能保证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; }