题解：CF2162E Beautiful Palindromes

Austin0116 · 2026-03-06 14:51:26 · 题解

分析

我们首先发现如果这个序列是一个排列的话，就直接将这个排列按顺序重复若干次即可。

我们考虑不是排列的情况，那么一定会有至少一个数没出现过。我们考虑将这个数填在序列之后的第一个，这样子之后的回文子串只能以这个数为对称轴。然后我们发现后面的数只要是类似于一个排列而有不和这个数相同即可，注意之后填的第一个数一定不能和初始序列的最后一个数相同。

代码

#include <cstdio>
#include <bitset>
#define N 200005
using namespace std;
int n,a[N],b[N],cnt,T,k,u,fl;
bitset<N> vis;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        cnt=fl=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            vis[a[i]]=1;
        }
        if((int)vis.count()!=n){//不是排列
            for(int i=1;i<=n;i++) if(!vis[i]){
                fl=i;
                break;
            }
            printf("%d ",fl);
            k--;
            for(int i=1;i<=n;i++) if(i!=fl) b[++cnt]=i;
            if(b[1]==a[n]) swap(b[1],b[2]);//避免初始序列的最后一个元素等于构造数组的第一个元素
        }
        else for(int i=1;i<=n;i++) b[++cnt]=a[i];//排列
        u=1;
        while(k--){
            printf("%d ",b[u]);
            if(u==cnt) u=1;
            else u++;
        }
        putchar('\n');
        for(int i=1;i<=n;i++) vis[i]=0;
    } 
    return 0;
}