CSP-S 2021 T3 palin 愚蠢的做法

· · 个人记录

我们来看看这个小丑在考场上都推了些什么破东西，结果还有边界情况没考虑挂分了，还导致 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)。

考场代码写的不知道什么鬼，稍微改得能看了一点，也不用想着有多好看。

#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();
}