比較簡單的一道E，只不過特殊情況有點多，需要考慮全面，
有個比較顯然的貪心:
從后往前處理，如果后面的后綴某兩個位置洗掉了，前面的后綴一定需要洗掉，(因為刪不刪某兩個位置的字符，只跟他們后面的字符有關)
然后就是簡單的處理了，這里給出一些情況，方便大家調錯：(最左邊的字符是當前處理的字符)
bba 刪去bb； --> a
aab 不洗掉； --> aab
aabba 洗掉aabb; --> a
aabbab 洗掉bb; --> aaab //wa46大概率是這組樣例錯了！
abba 洗掉bb; --> aa
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
//#define m (l+r)/2
#define pb push_back
typedef pair<int,int> pii;
const double PI= acos(-1.0);
const int M = 1e5+7;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
char s[M],p[M],cp[M];
int len,n,sz=0;
int ansl[M];
string ans[M],r;
void add(char c){
if(cp[sz]!=c)cp[++sz]=c;
r+=c;len++;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>(s+1);
n=strlen(s+1);s[n+1]=0;
char lst=0;
int bk=0;
for(int i=n;i>=1;i--){
if(s[i]!=s[i+1]){
if(len==0)lst=0;else lst=r[len-1];
add(s[i]);bk=i;
}
else{
if(len==0)add(s[i]);
else if(r[len-1]==s[i] && ((bk-i)&1) ){
int id=sz;
if(cp[sz]==s[i])id--;
if(cp[id]<s[i]){
r.erase(--r.end()),len--;
if(sz!=0&&len==0||r[len-1]!=cp[sz])sz--;
}
else add(s[i]);
}
else add(s[i]);
}
string tp;
ansl[i]=len;
if(len>10){
for(int i=0;i<5;i++)tp+=r[len-i-1];
tp+="...";
tp+=r[1];
tp+=r[0];
}
else {
for(int i=0;i<len;i++)
tp+=r[len-i-1];
}
ans[i]=tp;
}
for(int i=1;i<=n;i++)cout<<ansl[i]<<" "<<ans[i]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/161169.html
標籤：python