Problem - E - Codeforces

愛(ài)麗絲買(mǎi)了一個(gè)剛果總理視頻的訂閱，正在看一部關(guān)于蘇格蘭卡特林湖的因子島的考古發(fā)現(xiàn)的紀(jì)錄片?？脊艑W(xué)家發(fā)現(xiàn)了一本書(shū)，其年代和來(lái)源都不明。也許愛(ài)麗絲可以對(duì)它進(jìn)行一些解釋？

這本書(shū)包含一串字符 "a"、"b "和 "c"。有人指出，沒(méi)有兩個(gè)連續(xù)的字符是相同的。還有人猜測(cè)，這個(gè)字符串包含一個(gè)異常長(zhǎng)的子序列，從兩邊看都是一樣的。

幫助愛(ài)麗絲驗(yàn)證這一點(diǎn)，找到這樣的子序列，它至少包含原始字符串的一半的字符，并向下取整。請(qǐng)注意，你不一定要把它的長(zhǎng)度最大化。

如果一個(gè)字符串a(chǎn)a可以通過(guò)刪除幾個(gè)（可能是0個(gè)或全部）字符從bb中得到，那么這個(gè)字符串就是bb的一個(gè)子序列。

輸入
輸入包括一個(gè)字符串ss(2≤|s|≤1062≤|s|≤106)。字符串ss僅由字符 "a"、"b"、"c "組成。保證沒(méi)有兩個(gè)連續(xù)的字符是相等的。

輸出
輸出一個(gè)宮鎖鏈tt，它是ss的子序列，并且|t|≥?|s|2?|t|≥?|s|2?。

如果有多個(gè)解決方案，你可以打印其中任何一個(gè)。你不必使tt的長(zhǎng)度最大化。

如果沒(méi)有解決方案，則輸出一個(gè)字符串 "IMPOSSIBLE"（為清晰起見(jiàn)，加引號(hào)）。

例子
輸入
cacbac
輸出
aba
輸入
abc
輸出
a
輸入
cbacacacbcbababacbcb
輸出
cbaaacbcaaabc
注意
在第一個(gè)例子中，其他有效的答案包括 "cacac"、"caac"、"aca "和 "ccc"。
題解:

(不得不說(shuō),cf思維題出的是真的好,如果你寫(xiě)這種題時(shí),一個(gè)條件沒(méi)怎么用到,思路肯定是不對(duì)的)

?題目的關(guān)鍵:沒(méi)有相鄰的兩個(gè)字母,字母只有三個(gè),從這句話你能領(lǐng)悟到什么?(...)

首先第一點(diǎn):字母只有三個(gè),每相鄰四個(gè)肯定有兩個(gè)

第二點(diǎn):沒(méi)有相鄰的兩個(gè)字母,從字符串中,任意截取兩段字符長(zhǎng)度為2的子串,這兩個(gè)子串一定有字符相同

接著我們就可以從兩邊開(kāi)始找了,模擬這個(gè)過(guò)程(第二點(diǎn))即可

#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(); }
}