E. Archaeology(纯思维)

Problem - E - Codeforces

爱丽丝买了一个刚果总理视频的订阅，正在看一部关于苏格兰卡特林湖的因子岛的考古发现的纪录片。考古学家发现了一本书，其年代和来源都不明。也许爱丽丝可以对它进行一些解释？

这本书包含一串字符 "a"、"b "和 "c"。有人指出，没有两个连续的字符是相同的。还有人猜测，这个字符串包含一个异常长的子序列，从两边看都是一样的。

帮助爱丽丝验证这一点，找到这样的子序列，它至少包含原始字符串的一半的字符，并向下取整。请注意，你不一定要把它的长度最大化。

如果一个字符串aa可以通过删除几个（可能是0个或全部）字符从bb中得到，那么这个字符串就是bb的一个子序列。

输入
输入包括一个字符串ss(2≤|s|≤1062≤|s|≤106)。字符串ss仅由字符 "a"、"b"、"c "组成。保证没有两个连续的字符是相等的。

输出
输出一个宫锁链tt，它是ss的子序列，并且|t|≥⌊|s|2⌋|t|≥⌊|s|2⌋。

如果有多个解决方案，你可以打印其中任何一个。你不必使tt的长度最大化。

如果没有解决方案，则输出一个字符串 "IMPOSSIBLE"（为清晰起见，加引号）。

例子
输入
cacbac
输出
aba
输入
abc
输出
a
输入
cbacacacbcbababacbcb
输出
cbaaacbcaaabc
注意
在第一个例子中，其他有效的答案包括 "cacac"、"caac"、"aca "和 "ccc"。
题解:

(不得不说,cf思维题出的是真的好,如果你写这种题时,一个条件没怎么用到,思路肯定是不对的)

 题目的关键:没有相邻的两个字母,字母只有三个,从这句话你能领悟到什么?(...)

首先第一点:字母只有三个,每相邻四个肯定有两个

第二点:没有相邻的两个字母,从字符串中,任意截取两段字符长度为2的子串,这两个子串一定有字符相同

接着我们就可以从两边开始找了,模拟这个过程(第二点)即可

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII; 
const int N = 1e6 + 10;
int f[N]; 
void solve()
{string s;cin >> s;int n = s.size();s = " " + s;int l = 1,r = n;while(l < r){if(r - l + 1 < 4){f[l] = 1;break;}if(s[l] == s[r]){f[l] = f[r] = 1;l ++;r --;}else if(s[l + 1] == s[r]){f[l + 1] = f[r] = 1;l += 2;r--;}else if(s[l] == s[r - 1]){f[l] = f[r - 1] = 1; l ++;r -= 2;}else if(s[l + 1] == s[r - 1]){f[l + 1] = f[r - 1] = 1;l += 2;r -= 2;}}for(int i = 1;i <= n;i++){if(f[i])cout << s[i];}
}signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve(); }
}