P7915 [CSP-S 2021] 回文 先考虑第一个选 L 的情况，第一个选 R 的情况是同理的。 找到与 a1a_1 相等的数 axa_x，把 [2,x)[2,x) 和 (x,2n](x,2n] 看成两个双端队列， 按照字典序分类讨论，每次取两个队列的一个顶部和一个底部， 然后往答案字符串两边加字符即可。 代码： #include using namespace std; #define int long long const int N=1e6+5; int T,n; int a[N]; string solve(){ deque s1,s2; string ans="L"; for(int i=1;i1&&s1.front()==s1.back()){ ans[++l]='L',ans[--r]='L'; s1.pop_front(),s1.pop_back(); } else if(s1.size()&&s2.size()&&s1.front()==s2.back()){ ans[++l]='L',ans[--r]='R'; s1.pop_front(),s2.pop_back(); } else if(s1.size()&&s2.size()&&s2.front()==s1.back()){ ans[++l]='R',ans[--r]='L'; s2.pop_front(),s1.pop_back(); } else if(s2.size()>1&&s2.front()==s2.back()){ ans[++l]='R',ans[--r]='R'; s2.pop_front(),s2.pop_back(); } else return "-1"; } return ans; } string solve2(){ deque s1,s2; string ans="R"; for(int i=1;i1&&s1.front()==s1.back()){ ans[++l]='L',ans[--r]='L'; s1.pop_front(),s1.pop_back(); } else if(s1.size()&&s2.size()&&s1.front()==s2.back()){ ans[++l]='L',ans[--r]='R'; s1.pop_front(),s2.pop_back(); } else if(s1.size()&&s2.size()&&s2.front()==s1.back()){ ans[++l]='R',ans[--r]='L'; s2.pop_front(),s1.pop_back(); } else if(s2.size()>1&&s2.front()==s2.back()){ ans[++l]='R',ans[--r]='R'; s2.pop_front(),s2.pop_back(); } else return "-1"; } return ans; } signed main(){ cin>>T; while(T--){ cin>>n; for(int i=1;i>a[i]; string ans=solve(); if(ans!="-1"){ cout `#include using namespace std; #define int long long const int N=1e6+5; int T,n; int a[N]; string solve(){ dequeint> s1,s2; string ans="L"; for(int i=1;i2*n-2;i++) ans+=" "; ans+="L"; int x=a[1],y,idx=1; for(int i=2;i2*n;i++) if(a[i]==x){ y=i; break; } for(int i=2;is1.push_back(a[i]); for(int i=y+1;i2*n;i++) s2.push_front(a[i]); int l=0,r=2*n-1; while(s1.size()||s2.size()){ if(s1.size()>1&&s1.front()==s1.back()){ ans[++l]='L',ans[--r]='L'; s1.pop_front(),s1.pop_back(); } else if(s1.size()&&s2.size()&&s1.front()==s2.back()){ ans[++l]='L',ans[--r]='R'; s1.pop_front(),s2.pop_back(); } else if(s1.size()&&s2.size()&&s2.front()==s1.back()){ ans[++l]='R',ans[--r]='L'; s2.pop_front(),s1.pop_back(); } else if(s2.size()>1&&s2.front()==s2.back()){ ans[++l]='R',ans[--r]='R'; s2.pop_front(),s2.pop_back(); } else return "-1"; } return ans; } string solve2(){ dequeint> s1,s2; string ans="R"; for(int i=1;i2*n-2;i++) ans+=" "; ans+="L"; int x=a[2*n],y,idx=1; for(int i=1;i2*n;i++) if(a[i]==x){ y=i; break; } for(int i=1;is1.push_back(a[i]); for(int i=y+1;i2*n;i++) s2.push_front(a[i]); int l=0,r=2*n-1; while(s1.size()||s2.size()){ if(s1.size()>1&&s1.front()==s1.back()){ ans[++l]='L',ans[--r]='L'; s1.pop_front(),s1.pop_back(); } else if(s1.size()&&s2.size()&&s1.front()==s2.back()){ ans[++l]='L',ans[--r]='R'; s1.pop_front(),s2.pop_back(); } else if(s1.size()&&s2.size()&&s2.front()==s1.back()){ ans[++l]='R',ans[--r]='L'; s2.pop_front(),s1.pop_back(); } else if(s2.size()>1&&s2.front()==s2.back()){ ans[++l]='R',ans[--r]='R'; s2.pop_front(),s2.pop_back(); } else return "-1"; } return ans; } signed main(){ cin>>T; while(T--){ cin>>n; for(int i=1;i2*n;i++) cin>>a[i]; string ans=solve(); if(ans!="-1"){ cout"\n"; continue; } ans=solve2(); cout"\n"; } return 0; }`
P7915 [CSP-S 2021] 回文
笔记