CSP-S 2021 T3 palin 愚蠢的做法
AThousandSuns
2021-10-24 10:56:06
我们来看看这个小丑在考场上都推了些什么破东西，结果还有边界情况没考虑挂分了，还导致 T4 没调出来，身败名裂。
**前排提示：只是想知道这题怎么做的可以不用看。**
既然是回文，比较直接的想法是枚举前 $n$ 个数是哪些，后 $n$ 个数是哪些。容易发现前 $n$ 个数占据了一个前缀和一个后缀（可以为空），后 $n$ 个数一定是一个区间，且里面的数互不相同。
下文把 $[i,i+n-1]$ 且满足里面的数互不相同的这个区间叫做“$i$ 窗口”。
那么我们只需要枚举窗口，就可以贪心求。从前缀和后缀的开始部分贪心取（先试前缀再试后缀），要求在窗口里已取的对应的永远是一个区间。
这时时间复杂度是 $O(n^2)$，稍微推一推发现特殊性质也能过。
现在我们考虑如果 $i$ 窗口和 $j$ 窗口相交了会怎样（不妨设 $i<j$）。我们可以把整个序列划分成 $\texttt{ABCDE}$ 五个部分（$\texttt{A}$ 和 $\texttt{E}$ 可为空），其中窗口 $i$ 是 $\texttt{BC}$，窗口 $j$ 是 $\texttt{CD}$。
用定义瞎推推，有 $\{\texttt{B}\}=\{\texttt{D}\}$，和 $\{\texttt{C}\}=\{\texttt{A}\}+\{\texttt{E}\}$。
如果 $\texttt{A}$ 和 $\texttt{E}$ 均**不空**（**哈哈考场上就是没注意到这个**），那么无论第一步选了前缀还是后缀，对应到的都是 $\texttt{C}$ 里的位置。
因为 $\texttt{A}+\texttt{E}$ 能且仅能归属到 $\texttt{C}$，所以窗口 $i$ 有解当且仅当 $\texttt{A}+\texttt{E}$ 能把 $\texttt{C}$ 贪心取完，然后 $\texttt{B}$ 和 $\texttt{D}$ 子串完全一样。
然后我们发现窗口 $j$ 的条件也是这个，说明**窗口 $i$ 有解当且仅当窗口 $j$ 有解**。
如果有解，再考虑两个答案的结构。窗口 $i$ 可以看成是先用 $\texttt{A}+\texttt{E}$ 把 $\texttt{C}$ 取完，然后最后才用一堆 `R` 把 $\texttt{B}$ 取完（因为全是 `R` 中间就操作肯定不如放到最后）。而窗口 $j$ 可以看成是 $\texttt{A}+\texttt{E}$ 把 $\texttt{C}$ 取完前的某一个时刻，直接用一堆 `L` 把 $\texttt{D}$ 取完（原因同上）。
所以说，**窗口 $i$ 永远不优于窗口 $j$**。
那么现在只有三种可能的最优解：窗口 $1$，窗口 $n+1$，$2$ 到 $n$ 中最右边的窗口。
时间复杂度 $O(n)$。
考场代码写的不知道什么鬼，稍微改得能看了一点，也不用想着有多好看。
```cpp
#include<bits/stdc++.h>
#define FNAME "palin" // remember!
using namespace std;
const int maxn=1111111,mod=998244353; // remember!
#define PB push_back
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
int x=0,f=0;char ch=getchar();
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
inline void setfile(){
freopen(FNAME".in","r",stdin);
freopen(FNAME".out","w",stdout);
}
int n,a[maxn],pos[maxn];
string ans;
bool vis[maxn];
void ext(string s,string t,int x,int y,int L,int R,int l,int r){
bool flag=true;
while(y>=r){
while(x<l){
if(L>=l && a[L]==a[x]) L--,t.PB('L');
else if(R<=r && a[R]==a[x]) R++,t.PB('R');
else break;
x++;s.PB('L');
}
if(y==r){flag=x>=l;break;}
if(L>=l && a[L]==a[y]) L--,t.PB('L');
else if(R<=r && a[R]==a[y]) R++,t.PB('R');
else{flag=false;break;}
y--;s.PB('R');
}
reverse(t.begin(),t.end());
if(flag) ans=min(ans,s+t);
}
void work(int l,int r){
bool flag=true;
FOR(i,l,r){
if(pos[a[i]]) flag=false;
pos[a[i]]=i;
}
if(flag){
if(l!=1) ext("L","L",2,2*n,pos[a[1]]-1,pos[a[1]]+1,l,r);
if(r!=2*n) ext("R","L",1,2*n-1,pos[a[2*n]]-1,pos[a[2*n]]+1,l,r);
}
FOR(i,l,r) pos[a[i]]=0;
}
void solve(){
n=read();
FOR(i,1,2*n) a[i]=read();
ans=string(2*n,'R');
int j=2*n;
ROF(i,2*n,1){
while(j && !vis[a[j]]) vis[a[j]]=true,j--;
if(i-j==n){
work(j+1,i);
if(i!=2*n){
while(i>j) vis[a[i]]=false,i--;
i++;
}
}
vis[a[i]]=false;
}
work(1,n);
if(ans==string(2*n,'R')) printf("-1");
else FOR(i,0,2*n-1) putchar(ans[i]);
puts("");
}
int main(){
// setfile(); // remember!
int T=read();
while(T--) solve();
}
```