P7915 [CSP-S 2021] 回文

· · 题解

题传

很有意思的一道题，不过我考场上一直刚 T2 导致压根没时间看（）。

这题拿到看起来很离谱的样子，先考虑怎么暴力吧。

最朴素的暴力显然就是 2^n \times n 的暴力搜索判断，无法通过所有测试数据。

思考：我们每次都是搜完所有方案再去判断是否正确，这十分耗时，能否用一种方法，边搜边判呢？

继续往下思考：我们怎么判断这是一个解，肯定是拿个指针从两边向中间扫，如果有不匹配的就返回非解，那么搜索的时候能不能也像这样做呢？

我们珂以枚举 b 中开头的值（显然它只能是 a 的开头和末位），然后在 a 中找到与之对应的值 （即 b 的末位），这就相当于一个区间往里面缩，一个区间往外拓展，这样搜索的复杂度是 O(2^{n/2})。

考虑对其再来一个贪心，显然优先级为 LL --> LR --> RL --> RR，只要有一个可行我们就只搜这一条路，那么复杂度为 O(n) （每次只移动一次，每移动一次数组长度 -2 ），但是这么做正确性？比较显然，无论怎样最终的指针还是会匹配到这个位置，所以前面无论怎样改，不行就是不行。

然后你就发现这其实跟 T1 一样是个猜了结论就会做的题。。。

Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mo=1e9+7;
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(!isdigit(ch)) f=(ch=='-'?-1:f), ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
    return x*f; 
}
const int N=5e5+5;
int n, L[N], R[N], a[2*N], b[2*N];
char ans[2*N];
bool doit(int lst, int Li, int Ri){
    if(Li==2) ans[1]='L';
    else ans[1]='R';
    int l=lst, r=lst, st=2, ed=2*n-1;
    for(int i=1; i<n; i++){
        if(R[a[Li]]==l-1) l--, Li++, ans[st++]='L', ans[ed--]='L';
        else if(R[a[Li]]==r+1) r++, Li++, ans[st++]='L', ans[ed--]='R';
        else if(L[a[Ri]]==l-1) l--, Ri--, ans[st++]='R', ans[ed--]='L';
        else if(L[a[Ri]]==r+1) r++, Ri--, ans[st++]='R', ans[ed--]='R';
        else return 0;
    }
    ans[2*n]='L';printf("%s\n", ans+1);return 1;
}
void solve(){
    memset(L, 0, sizeof(L));
    memset(R, 0, sizeof(R));
    memset(b, 0, sizeof(0));
    memset(ans, 0, sizeof(ans));
    n=read();for(int i=1; i<=2*n; i++)
    a[i]=read(), L[a[i]]?R[a[i]]=i:L[a[i]]=i;
    if(doit(R[a[1]], 2, 2*n)) return ;
    if(doit(L[a[2*n]], 1, 2*n-1)) return ;
    puts("-1");return ;
}
signed main(){
    int T=read();while(T--) solve();
    return 0;
}