花火的回文序列

limingyuan333 · 2025-01-20 11:33:25 · 个人记录

花火的回文序列

题意简述：给定一个长度为 2 \times n 的 1 \sim n 各出现 2 次的数列，每一次可以从左边或者右边取出一个数放在新序列末尾，使得最后的序列为回文序列，如果有解，输出字典序最小的，否则输出 -1 。

0x01 28pts

用两个指针来表示当前的原数列被取到了什么地方，然后每次都暴力的找要从左边还是右边更新，最后再检查判断是否可行。

期望复杂度：O(2^{2n})

#include<bits/stdc++.h>
#define int long long
#define m(x) memset(x,0,sizeof(x))
using namespace std;
const int MAXN=1e2+10;
int ans[MAXN],num[MAXN],a[MAXN];
int n,T;
bool flag;
bool check(){
    for(int i=1;i<=n;i++){
        if(num[i]!=num[2*n-i+1])    return 1;
    }
    return 0;
}
void dfs(int x,int l,int r){
    if(flag)    return ;
    if(x<=2*n){ 
        num[x]=a[l];ans[x]=0;
        dfs(x+1,l+1,r);
        if(flag)    return ;
        num[x]=a[r];ans[x]=1;
        dfs(x+1,l,r-1);
    }
    else{
        if(check()) return ;
        for(int i=1;i<=2*n;i++){
            if(ans[i])  cout<<"R";
            else    cout<<"L";
        }
        cout<<'\n';flag=1;
    } 
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=2*n;i++) cin>>a[i];
        dfs(1,1,2*n);
        if(!flag) cout<<-1<<'\n';
        m(ans),m(num);flag=0;
    }
    return 0;
}

0x02 56pts

与上述做法相似，但是需要一边检查，一边搜索即可

期望复杂度 O(2^n)

#include<bits/stdc++.h>
#define int long long
#define m(x) memset(x,0,sizeof(x))
using namespace std;
const int MAXN=1e2+10;
int ans[MAXN],num[MAXN],a[MAXN];
int n,T;
bool flag;
bool check(int x){
    return ((x>=n+1&&num[x]!=num[2*n-x+1])?0:1);
}
void dfs(int x,int l,int r){
    if(flag)    return ;
    if(x<=2*n){
        num[x]=a[l];ans[x]=0;
        if(check(x))    dfs(x+1,l+1,r);
        if(flag)    return ;
        num[x]=a[r];ans[x]=1;
        if(check(x))    dfs(x+1,l,r-1);
    }
    else{
        for(int i=1;i<=2*n;i++){
            if(ans[i])  cout<<"R";
            else    cout<<"L";
        }
        cout<<'\n';flag=1;
    } 
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=2*n;i++) cin>>a[i];
        dfs(1,1,2*n);
        if(!flag) cout<<-1<<'\n';
        m(ans),m(num);flag=0;
    }
    return 0;
}

0x03 72pts

判定性剪枝，上面的检查还远远不够，让我们来剖析题目的本质。

让我们来分析样例。如上图，若把开头的 4 移走，为了保证回文，另外一个 4 一定是最后一个移走的。因此，我们需要把红色方框内的数字全部移走才能保证合法。

现在考虑进行第二次操作。

显然，第二次操作只能拿走左边红框的第一个元素 1，或者右边红框最后的元素 5。到底应该取哪一个呢？我们可以从倒数第二次操作来分析。在上图中， 4 是最后移走的，又因为每次只能移动最左边或最右边的元素，因此倒数第二个移走的一定是上图中第二个 4 左边的 2 或者右边的 5。

之后以此类推，所以我们应该预处理出每一个元素对应的位置和另一个相同元素的位置。然后在搜索的时候再加上判断，如果中间区域无法扩展出来并且不是第一个位置，那么则说明当前位置怎样扩展都无法合法，看代码。

#include<bits/stdc++.h>
#define m(x,c) for(int i=1;i<=x;i++) c[i]=0;
using namespace std;
const int MAXN=5e5+10;
int a[MAXN<<1];
char ans[MAXN<<1];
int n,T,l1[MAXN],l2[MAXN],to[MAXN<<1],vis[MAXN];
bool flag;
void dfs(int x,int l,int r,int fi,int se){
    if(flag)    return ;
    if(x>2*n){
        for(int i=1;i<=2*n;i++){
            putchar(ans[i]);
        }
        cout<<'\n';flag=1;
        return ;
    }
    if(!vis[a[l]]&&(x==1||to[l]==se+1||to[l]==fi-1)){
        vis[a[l]]=x;ans[x]='L';
        dfs(x+1,l+1,r,min(to[l],fi),max(to[l],se));
        vis[a[l]]=0;
    }
    else if(n*2-vis[a[l]]+1==x){
        ans[x]='L';
        dfs(x+1,l+1,r,fi,se);
    }
    if(flag)    return ;
    if(!vis[a[r]]&&(x==1||to[r]==se+1||to[r]==fi-1)){
        vis[a[r]]=x;ans[x]='R';
        dfs(x+1,l,r-1,min(to[r],fi),max(to[r],se));
        vis[a[r]]=0;
    }
    else if(n*2-vis[a[r]]+1==x){
        ans[x]='R';
        dfs(x+1,l,r-1,fi,se);
    }
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=2*n;i++){
            cin>>a[i];
            if(!l1[a[i]]) l1[a[i]]=i;
            else    l2[a[i]]=i;
        }
        for(int i=1;i<=n;i++) to[l1[i]]=l2[i],to[l2[i]]=l1[i];
        flag=0;
        dfs(1,1,2*n,2*n+1,0);
        if(!flag) cout<<-1<<'\n';
        m(n,l1);m(n,l2);m(2*n,to);m(n,vis);
    }
    return 0;
}

0x04 100pts

最后一个部分，我们清楚只要确定了第一个就可以无限扩展，所以第一步没有限制，其余只做 L 操作或者 R ,这样就可以完成这个题目

期望复杂度 O(n \times 2)

#include<bits/stdc++.h>
#define m(x,c) for(int i=1;i<=x;i++) c[i]=0;
using namespace std;
const int MAXN=5e5+10;
int a[MAXN<<1];
char ans[MAXN<<1];
int n,T,l1[MAXN],l2[MAXN],to[MAXN<<1],vis[MAXN];
bool flag;
void dfs(int x,int l,int r,int fi,int se){
    if(flag)    return ;
    if(x>2*n){
        for(int i=1;i<=2*n;i++) putchar(ans[i]);
        cout<<'\n';flag=1;
        return ;
    }
    bool f=0;
    if(!vis[a[l]]&&(x==1||to[l]==se+1||to[l]==fi-1)){
        vis[a[l]]=x;ans[x]='L';
        dfs(x+1,l+1,r,min(to[l],fi),max(to[l],se));
        vis[a[l]]=0;f=1;
    }
    else if(n*2-vis[a[l]]+1==x){
        ans[x]='L';dfs(x+1,l+1,r,fi,se);
        f=1;
    }
    if(f&&x!=1) return ;
    if(flag)    return ;
    if(!vis[a[r]]&&(x==1||to[r]==se+1||to[r]==fi-1)){
        vis[a[r]]=x;ans[x]='R';
        dfs(x+1,l,r-1,min(to[r],fi),max(to[r],se));
        vis[a[r]]=0;
    }
    else if(n*2-vis[a[r]]+1==x){
        ans[x]='R';
        dfs(x+1,l,r-1,fi,se);
    }
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=2*n;i++){
            cin>>a[i];
            if(!l1[a[i]]) l1[a[i]]=i;
            else    l2[a[i]]=i;
        }
        for(int i=1;i<=n;i++) to[l1[i]]=l2[i],to[l2[i]]=l1[i];
        flag=0;
        dfs(1,1,2*n,2*n+1,0);
        if(!flag) cout<<-1<<'\n';
        m(n,l1);m(n,l2);m(2*n,to);m(n,vis);
    }
    return 0;
}

花火的回文序列

花火的回文序列

0x01 28pts

0x02 56pts

0x03 72pts

0x04 100pts

end