题解：CF1178E Archaeology

ZHANGHUAYU666 · 2026-10-20 15:00:04 · 题解

神神秘秘的构造题。

解题思路

我们可以很容易发现字符串 s 只有三种字母而且相邻两个字符互不相同。

由此我们可以推出一个神秘性质：任意两个相邻字符对中，都存在一个字符与另一对中的某个字符相等。

因为根据鸽巢原理，将三种字母填入两个相邻字符对（四个位置）中必然有一种字母填了两遍。

因为一个相邻字符对中两个字符互不相同，所以必然存在一个字符与另一对相邻字符对中的某个字符相等。

根据这个性质我们就可以来构造这道题的答案了。

步骤 1：先从字符串的两边各选一对相邻字符对，然后输出这两个字符对中相同的字符。

步骤 2：然后将字符串去除两边相邻字符对，继续进行步骤 1。

持续进行步骤一和步骤二直到字符串不能再次选择两对相邻字符对，则停止。

我们会发现有时候字符串遍历终止时，字符串还剩两三位，所以答案少输出一位。

这个时候多输出一个字符串最中间的字母即可。

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
string s;
ll cnt;
char ans[N];
int main ()
{
    cin >> s;
    s = "~" + s;
    ll l = 1, r = s.size () - 1;
    while (l + 1 < r - 1)
    {
        if (s[l] == s[r]) ans[++ cnt] = s[l];
        else if (s[l] == s[r - 1]) ans[++ cnt] = s[r - 1];
        else if (s[l + 1] == s[r]) ans[++ cnt] = s[l + 1];
        else ans[++ cnt] = s[l + 1];
        l += 2, r -= 2;
    }
    for (int i = 1; i <= cnt; i ++)
        cout << ans[i];
    if (r - l + 1 >= 2)
        cout << s[(s.size() - 1) / 2 + 1];
    for (int i = cnt; i >= 1; i --)
        cout << ans[i];
    return 0;
}