P6908 [ICPC 2015 WF] Evolution in Parallel 题解

· · 题解

题面解释：

老实说看了 20 分钟没看懂题，给个好理解的把。

维护 2 个栈，栈底元素为现在的生物的基因，需保证栈中上层元素为下层的子序列（怎么不算一种单调性呢）。

思路分析：

首先，若 A 是 B 的子序列，B 是 C 的子序列，那么显然 A 是 C 的子序列，那么保证栈的单调性只需要保证每次入栈元素是栈顶元素的子序列。

继续思考子序列的性质，若 A 是 B 的子序列则 A 一定不比 B 长，若一样长则二者必然相等。那么我们可以先按长度从大到小排序，正确性显然。

在保证前面策略正确的情况下，如果当前字符串不是两个栈顶中任意一个的子序列，无解。

我们发现，在一个字符串同时可以加入两边时，我们不知道如何安置这个字符串。那我们就建立一个缓存队列，队列一样满足单调性，里面存的字符串就是同时可以加入两个栈的，等到后面有更多信息再考虑。

那么这时，如果一个字符串只能加入其中一个栈，那么同时要把缓存压入另一个栈。因为如果缓存能压在这个字符串上当且仅当当前字符串与缓存里的字符串相同，那么必然可以进入缓存。

再进一步思考，我们就能发现，能同时加入两个栈的字符串不一定能加入缓存，这个时候我们随便压入一个栈，缓存压入另一个栈即可。不论这时候压入哪边，都是等价的。

最后输出的时候注意不要把最开始加入的初始元素输出即可。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int N=4e3+10;
string S,s[N];
int n,len[N],id[N];
stack<string>s1,s2;
deque<string>_s;
inline bool cmp(int p,int q){
    return len[p]>len[q];
}
inline bool In(string p,string q){
    for(int i=0,j=0;j<q.size();j++){
        if(p[i]==q[j])i++;
        if(i==p.size())return 1;
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>S;
    for(int i=1;i<=n;i++)
        cin>>s[i],id[i]=i,
        len[i]=s[i].size();
    sort(id+1,id+n+1,cmp);
    s1.push(S);s2.push(S);
    for(int _i=1;_i<=n;_i++){
        int i=id[_i];
        bool bk1=In(s[i],s1.top());
        bool bk2=In(s[i],s2.top());
        if(bk1&&bk2){
            if(_s.empty()||In(s[i],_s.back()))
                _s.push_back(s[i]);
            else{
                s1.push(s[i]);
                while(!_s.empty())
                    s2.push(_s.front()),
                    _s.pop_front();
            }
        }
        else if(bk1){
            s1.push(s[i]);
            while(!_s.empty())
                s2.push(_s.front()),
                _s.pop_front();
        }
        else if(bk2){
            s2.push(s[i]);
            while(!_s.empty())
                s1.push(_s.front()),
                _s.pop_front();
        }
        else{cout<<"impossible";return 0;}
    }
    while(!_s.empty())
        s1.push(_s.front()),
        _s.pop_front();
    cout<<s1.size()-1<<' '<<s2.size()-1<<'\n';
    while(s1.size()>1)cout<<s1.top()<<'\n',s1.pop();
    while(s2.size()>1)cout<<s2.top()<<'\n',s2.pop();
    return 0;
}

有双倍经验，但是不知道为什么过不了。

完结撒花！！！