Archaeology

Created by LXC on Wed Jul 19 09:09:36 2023

https://codeforces.com/problemset/problem/1178/E

ranting: 1900

tag: brute force, constructive algorithms, greedy, strings

problem

给出一个仅由a b c三种字符组成的字符串s，且s的任意两个相邻字符都不相同。

求s的一个长度至少为$\lfloor \frac{|s|}{2} \rfloor$回文子序列

solution

注意到字符串只有三种字符组成，那么s的首两个字符和末两个字符中一定有两个相同的字符，由于相邻的字符不相同，所以首两个字符中有一个字符会出现在末两个字符中。

在原串每四个字符就可以构造回文串的两个字符。不足四个的可以任意选一个作为回文串的中心。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    string s;
    cin >> s;
    int n = s.size();
    if (n <= 3) {
        cout << s[0] << "\n";
        return;
    }
    string ans;
    for (int i = 0; i + 1 < n / 2; i += 2) {
        if (s[i] == s[n - 1 - i] || s[i] == s[n - 2 - i])
            ans.push_back(s[i]);
        else
            ans.push_back(s[i + 1]);
    }
    cout << ans;
    reverse(ans.begin(), ans.end());
    if (n / 2 % 2)
        cout << s[n / 2];
    cout << ans;
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}