题解 P6303 【[eJOI2018]AB 串】

xtx1092515503 · 2020-06-09 18:56:53 · 题解

这里介绍一种不需要特判的算法。

首先，很容易想到的性质是，假如有一些连续的a或b在某次操作中连起来了，那么，最优策略中它们将不再分开。

这点非常显然，因为你不会想着把已经连一起的东西拆开吧？

这就意味着我们可以把相邻的a或b看做一个字符，即aa...aa=a。我们可以重载一个deque<pair<int,int> >来维护此种串，其中第一维是字符类型，第二维是有几个同类型的字符被并到了一起。

struct DEQUE:deque<pair<int,int> >{
    void PUSH_FRONT(char ip){
        if(empty())push_front(make_pair(ip-'a',1));
        else if(front().first==ip-'a')front().second++;
        else push_front(make_pair(ip-'a',1));
    }
    void PUSH_FRONT(pair<int,int>ip){
        if(empty())push_front(ip);
        else if(front().first==ip.first)front().second+=ip.second;
        else push_front(ip);
    }
    void PUSH_BACK(char ip){
        if(empty())push_back(make_pair(ip-'a',1));
        else if(back().first==ip-'a')back().second++;
        else push_back(make_pair(ip-'a',1));
    }
    void PUSH_BACK(pair<int,int>ip){
        if(empty())push_back(ip);
        else if(back().first==ip.first)back().second+=ip.second;
        else push_back(ip);
    }
}

我们还可以写出交换串p中前f个字符（合并后）和串q中前g个字符（合并后），并将操作存入vector<pair<int,int> > v的代码：

stack<pair<int,int> >s,t;
void SWAP(int f,int g,vector<pair<int,int> >&v){
    int i=0,j=0;
    while(f--)i+=p.front().second,s.push(p.front()),p.pop_front();
    while(g--)j+=q.front().second,t.push(q.front()),q.pop_front();
    v.push_back(make_pair(i,j));
    while(!s.empty())q.PUSH_FRONT(s.top()),s.pop();
    while(!t.empty())p.PUSH_FRONT(t.top()),t.pop();
}

当你这么并完后，会发现，两个串中的a和b都将是交错出现的！

我们就可以考虑设计算法了。

我们可以将一组状态分成两种可能，即首字母相同或不同的情况。

考虑当两个串p和q的首字母相同的情况，除非交换的时候一个串的长度为奇而另一个串的长度为0，否则两个串的首字母将会保持相同。因此，我们在总过程中，总要这么来一次（不然首字母将会一直相同）。所以我们不如就在一开始来一次，这样就能转成首字母不同的情况。

当首字母不同的情况。这时，当你交换两个串同奇偶的前缀时，将会在两个串中各消掉一个字符。

例：

但是这一操作也有例外。当两个串中有一个被交换整个串时，一共只会消去一个字符。

例：

因此我们设计的算法要尽量避免交换整个串的情况。

我们可以发现，除非有一个串的长度已经只剩1了，否则是不会交换整个串的。

具体而言，我们每次最简单的方法就是两边交换的前缀都为1，这时两个串的长度差不变。而如果长度差\geq 2且更长的那个串的长度>3，我们就可以考虑交换(1,3)或(3,1)来平衡两个串。（两个串的长度差越小，出现长度为1的串的时间就会越靠后）

于是我们可以写出这样的代码：

void func(vector<pair<int,int> >&v){
    while(p.size()>1||q.size()>1){
        if(abs((int)p.size()-(int)q.size())<2||p.size()<=3&&q.size()<=3)SWAP(1,1,v);        
        else{
            if(p.size()<q.size())SWAP(1,3,v);
            else SWAP(3,1,v);
        }
    }   
}

最后的最后，是关于如何把首字母相同的情况转成首字母不同的情况。显然，只需要交换(1,0)或(0,1)即可。但究竟要交换哪一个呢？

一个naive的想法是把长的往短的转。这样只能拿到89\%，因为有反例：

bababa
bab

如果按照naive的想法的话，需要5步；但是反着来，就只需要4步。

那到底应该怎么办呢？

那就两个都试一遍就行了！

重要代码已经在之前都贴过了，贴个主函数就得了。

int main(){
    scanf("%s%s",a,b),A=strlen(a),B=strlen(b);
    for(int i=0;i<A;i++)c.PUSH_BACK(a[i]);
    for(int i=0;i<B;i++)d.PUSH_BACK(b[i]);
    if(c.size()==1&&d.size()==1){puts("0");return 0;}
    if(c.front().first!=d.front().first)p=c,q=d,func(v);
    else{
        if(d.size()>1){
            p=c,q=d;
            SWAP(0,1,v);
            func(v);            
        }else v.resize(500001);
        if(c.size()>1){
            p=c,q=d;
            SWAP(1,0,u);
            func(u);            
        }else u.resize(500001);
        if(u.size()<v.size())swap(u,v);
    }                                
    printf("%d\n",v.size());
    for(auto x:v)printf("%d %d\n",x.first,x.second);
    return 0;
}