Codeforces 1178E. Archaeology

传送门

首先一定有解，考虑归纳法证明

首先 $n<=3$ 时显然

考虑 $n=4$ 时，那么因为 $s[1]!=s[2],s[3]!=s[4]$ ，并且 $s[i] \in {a,b,c}$ 由鸽巢原理显然意味着 $s[1],s[2]$ 至少有一个等于 $s[3]$ 或 $s[4]$

那么我们从中间往两边延伸，每左边两个就和右边两个组合，这样每四个位置就有两个位置会贡献回文字符，那么一定有解

注意如果 $n \mod 4=2$ 或者 $n \mod 4=3$ 时最后会剩下几个不能组成左边两个右边两个，那么我们回文长度搞成奇数即可（中间先选择一个作为回文中心）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e6+;

int n;

char s[N];

vector <int> ans;

void work(int l,int r)

{

    for(; l>=&&r<=n-; l-=,r+=)

    {

        vector <int> cnt[];

        cnt[s[l-]-'a'].push_back(l-);

        cnt[s[r+]-'a'].push_back(r+);

        cnt[s[l]-'a'].push_back(l);

        cnt[s[r]-'a'].push_back(r);

        for(int k=;k<;k++)

            if(cnt[k].size()>)

            {

                ans.push_back(cnt[k][]),

                ans.push_back(cnt[k][]);

                break;

            }

    }

}

int main()

{

    scanf("%s",s+); n=strlen(s+);

    int mid=+n>>;

    if(n%) { ans.push_back(mid); work(mid-,mid+); }

    else work(mid,mid+);

    sort(ans.begin(),ans.end());

    for(auto p: ans) printf("%c",s[p]);

    puts(""); return ;

}