CF题解

📝 核心思路 合法括号序列: ‘ ( ’ : 1 ‘ ) ’ : -1 在1,3,5奇数位置,前缀和要为奇数且大于0 在2,4,6偶数位置,前缀和要为偶数且大于等于0 且在末尾前缀和为0 由上述规律考虑: 我们考虑a和b的总前缀和 则奇数位置 前缀和为偶数 且大于等于2 偶数位置 前缀和为偶数 且大于等于0 且到末尾 要为0 考虑交换:如果当前位置不同,则让前缀和小的加上1,大的减去1 代码 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 #include<bits/stdc++.h> using namespace std; typedef long long ll; void solve(){ int n; cin>>n; string a,b; cin>>a; cin>>b; a=" "+a; b=" "+b; int sum=0; for(int i=1;i<=n;i++){ sum+=(a[i]=='(')?1:-1; sum+=(b[i]=='(')?1:-1; if( ( i&1 && sum<2 ) || ( !(i&1) && sum<0 ) ){ cout<<"NO"<<"\n"; return; } } if(sum!=0) cout<<"NO\n"; else cout<<"YES\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; }

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