AGC036E
有个由(A,B,C)组成的字符串，要找到其中最长的一个子序列，满足：
(A,B,C)出现次数相等。
子序列中相连的字母不同。
(|S|le 10^6)
似乎杂题的时候遇见过呢。。。
这题是个乱搞好题，反正看网上若干篇博客都感觉不一样。
这里说说我的乱搞做法：
显然有这样一条性质：对于一个字符串来说，如果有个子序列满足相连的字母不同，那么它一定可以通过如此操作：每次删去形如(BAC)中的(A)，或者(BAB)中的(AB)（或(BA)）得到，并且满足删的过程中一直满足相连的字母不同。
接下来假设(cnt_Age cnt_B ge cnt_C)。
假如只删(AB)或(AC)，设(z)为每一个字母剩下的出现次数，那么有(cnt_A-z=cnt_B-z+cnt_C-z)，即(z=cnt_B+cnt_C-cnt_A)
我们先只做删(A)的操作，再只做(AB)或(AC)的操作。那么我们就要最小化(cnt_A)（当然最小也要大于等于(cnt_B)），所以在(cnt_A>cnt_B)时尽量找可以删的(A)，然后删之。
假如删去的所有的可以删的(A)，那么不存在形如(BAC)的结构，只会存在(BABABdots AB)这样的。可以发现，无论后面怎么操作，都不会出现必须做删(A)操作才能够到达的状态（也就是说即使有也可以通过删(AB)之类的替换），所以只操作删(AB)操作在当前状况下是最优的。这时候(z)可以直接取到(cnt_B+cnt_C-cnt_A)。证明：设(L_B,L_C)分别为可以删(AB)和(AC)最多次数。如果(z)符合条件，必有(B-zle L_B)，也就是(A-L_Ble C)，此时存在的(A)要么夹在(B)之间要么夹在(C)之间，(A-L_B)意味着夹在(C)之间的(A)的个数，所以显然不会超过(C)。(L_C)的证明同理。设(S_A)表示删(A)操作的最多次数，那么(cnt_B+cnt_C-cnt_A+S_A)是此时的答案。这样在当前状况下得到的最优的答案。
这同时也是全局状况下最优解的答案，证明（这里的证明比较感性，不够严谨，期待更好的证明）：假如我们通过这个方法确定了一个方案，不难发现改变操作顺序没有任何影响，所以这是只有删(A)、(AB)、(AC)操作下的最优解。如果要更优，那么就可能要引入删(B)或(C)甚至(BC)的操作。不考虑删(C)或(BC)操作（这种操作一眼就感觉不存在。。。），设删(B)操作要做(x)次，删(A)操作要做(y)次。那么有(z=cnt_C+cnt_B-cnt_A+y-x)，如果它更优，就有(y-x>S_A)，所以(y>x+S_A)，之前定义了(S_A)是删(A)操作的最多次数，要是满足这个条件，这个最多次数一定在操作过程中发生了增加，增加无非就是(BABC o BAC)这种形式，又因为(BAC)中的(A)是消耗品，所以最终变成(BC)。这和直接删(AB)是等价的。于是引入(B)操作就是相当于(AB)拆成删(B)和删(A)，没有本质突破。所以最优解由删(A)、(AB)和(AC)的得到，即上面所述答案。
假如没有删去所有可以删的(A)，那么这时候一定有(cnt_A=cnt_Bge cnt_C)。(z)可以取到(cnt_B+cnt_C-cnt_A=cnt_C)，以下证明(cnt_A-cnt_Cle L_B)：变一下就是(cnt_A-L_B-L_Cle cnt_C-L_C)，这样可以等价成一个只有所有(A)都在形如(BAC)形式的字符串，且不存在(ABA)和(ACA)。假如不成立，由于一个(BAC)带着一个(A)和(C)，我们希望(cnt_A'>cnt_C')，自然是要让(C)被出现在两组(BAC)之中，就会出现形如(BACAB)的结构，然而这个时候是存在了一个(ACA)的，于是就矛盾了。证完之后，我们得到：如果只删(AB)，那么能够达到答案是(cnt_C)。显然(cnt_C)同时也是答案的上限，所以这样在当前状况下也能得到最优答案，同时也是全局状况下的最优答案。
综上，我们得到了一个策略：先做删(A)的操作，删到不能删或者(cnt_A=cnt_B)为止。然后取(z=cnt_B+cnt_C-cnt_A)，适当得删些(AB)和(AC)。这样就得到了一个正确的做法。
话说有些证明都是我写题解的时候脑补出来的呢，当时切题的时候拍了好久没有问题就直接干了。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 1000010
int n;
char str[N];
int cnt[3],p[3],re[3];
void adjust(int &A,int &B,int &C){
memset(cnt,0,sizeof cnt);
for (int i=1;i<=n;++i)
cnt[str[i]-'A']++;
for (int i=0;i<3;++i)
p[i]=i;
for (int i=0;i<3;++i)
for (int j=1;j<3;++j)
if (cnt[p[j-1]]<cnt[p[j]])
swap(p[j-1],p[j]);
for (int i=0;i<3;++i)
re[p[i]]=i;
for (int i=1;i<=n;++i)
str[i]=re[str[i]-'A']+'A';
A=cnt[p[0]],B=cnt[p[1]],C=cnt[p[2]];
}
struct LIST{
LIST *pre,*suc;
char c;
} s[N];
void erase(LIST *p){
p->pre->suc=p->suc;
p->suc->pre=p->pre;
}
bool BAC(LIST *p){return p->c=='A' && p->pre->c!=p->suc->c;}
bool BAB(LIST *p){return !p->pre->c || !p->suc->c || p->pre->c==p->suc->c;}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%s",str+1);
n=strlen(str+1);
int tmp=0;
for (int i=1;i<=n;++i)
if (str[i]!=str[i-1])
str[++tmp]=str[i];
n=tmp;
str[n+1]=0;
int A,B,C;
adjust(A,B,C);
if (C==0)
return 0;
// printf("%s
",str+1);
s[0].suc=&s[1];
s[n+1].pre=&s[n];
for (int i=1;i<=n;++i)
s[i]={&s[i-1],&s[i+1],str[i]};
for (LIST *p=s[0].suc;p!=&s[n+1] && A>B;p=p->suc)
if (BAC(p)){
A--;
erase(p);
}
// for (LIST *p=s[0].suc;p!=&s[n+1];p=p->suc)
// putchar(p->c);
// printf("
");
int z=B+C-A;
int neB=B-z,neC=C-z;
for (LIST *p=s[0].suc;p!=&s[n+1];p=p->suc){
if (BAB(p)){
// for (LIST *p=s[0].suc;p!=&s[n+1];p=p->suc)
// putchar(p->c);
// printf("
");
if (p->c=='A'){
if ((p->pre->c|p->suc->c)=='B')
{if (neB) erase(p->pre->c?p->pre:p->suc),erase(p),neB--;}
else
{if (neC) erase(p->pre->c?p->pre:p->suc),erase(p),neC--;}
}
else if ((p->pre->c|p->suc->c)=='A'){
if (p->c=='B')
{if (neB) erase(p->pre->c?p->pre:p->suc),erase(p),neB--;}
else
{if (neC) erase(p->pre->c?p->pre:p->suc),erase(p),neC--;}
}
}
}
for (LIST *q=s[0].suc;q!=&s[n+1];q=q->suc)
putchar(p[q->c-'A']+'A');
return 0;
}