题解：P10653 「ROI 2017 Day 2」存储器

· · 题解

题意

有两个由 + 和 - 组成的字符串 S 和 T，你需要进行若干次操作，每次可以将 S 中一段极长串翻转，满足这个极长串的长度小于其任意一个相邻的极长串的长度。问 S 是否能经过变换得到 T。多组数据。

题解

我们从特殊性质开始考虑：T 中没有 -。

对于 S 中任意一个极长的、由 - 构成的串，我们必须想办法将其翻转。

首先有一个接近 O(n^2) 的暴力：将所有的极长串用链表连接，每次枚举一段由 + 组成的串，判断其右边的串是否能翻转。若能，则将这段串右边、右边的右边的串都删掉，并增加这段串的长度。最后，若不能操作时仍有 -，则输出 No，否则输出 Yes，代码如下：


void link(int u,int v){
    nxt[u]=v, pre[v]=u;
}

bool check(){
    s[n+1]=t[n+1]='\0';
    cnt=0;
    if(s[1]=='-') cnt=1, siz[1]=0;
    int tmp=1;
    rep(i, 2, n+1){
        if(s[i]!=s[i-1]) siz[++cnt]=tmp, tmp=1;
        else ++tmp;
    }
    if(cnt%2==0) siz[++cnt]=0;
    rep(i, 1, cnt-1) link(i, i+1);
    nxt[cnt]=0;
    while(nxt[1]){
        bool flag=0;
        for(int i=1, j; nxt[i];){
            j=nxt[nxt[i]];
            if(siz[j]>siz[nxt[i]] || siz[i]>siz[nxt[i]]){
                siz[i]+=siz[j]+siz[nxt[i]];
                link(i, nxt[j]);
                flag=1;
            }
            i=j;
        }
        if(!flag) break;
    }
    return !nxt[1];
}

这段代码在随机数据下的复杂度应该是 O(n)，仅当 S 存在类似 --+--+--+-++ 的串时，复杂度退化为 O(n^2)。因此考虑添加一个优化：当一次翻转成功时，我们回退到上一个极长 + 串，再进行判断。这样就变成 O(n) 了。只要改动for循环中的一部分内容就好了:

            j=nxt[nxt[i]];
            if(siz[j]>siz[nxt[i]] || siz[i]>siz[nxt[i]]){
                siz[i]+=siz[j]+siz[nxt[i]];
                link(i, nxt[j]);
                flag=1;
                if(pre[i]) i=pre[pre[i]];
            } else i=j;

接下来正解就水到渠成啦！！对于 T 的每一个极长段，我们可以对其分开讨论，这样就变成了若干个特殊性质的叠加。

需要注意的一点是，若对于 T 的某一个极长串，s 在对应的位置的两边并不属于一个独立的极长串，就无法操作了。此时直接输出 No 就好。

于是，这道题就做完了。

Code

const int N=1e6+7;
int n;
char s[N], t[N];

namespace sub{
int n;
char s[N], t[N];
int siz[N], pre[N], nxt[N], cnt;

void link(int u,int v){
    nxt[u]=v, pre[v]=u;
}

bool check(){
    s[n+1]=t[n+1]='\0';
    // cout<<s+1<<' '<<t+1<<endl;
    if(t[1]=='-'){
        rep(i, 1, n)
            s[i]=s[i]=='-'?'+':'-';
    }
    cnt=0;
    if(s[1]=='-') cnt=1, siz[1]=0;
    int tmp=1;
    rep(i, 2, n+1){
        if(s[i]!=s[i-1]) siz[++cnt]=tmp, tmp=1;
        else ++tmp;
    }
    if(cnt%2==0) siz[++cnt]=0;
    rep(i, 1, cnt-1) link(i, i+1);
    nxt[cnt]=0;
    while(nxt[1]){
        bool flag=0;
        for(int i=1, j; nxt[i];){
            j=nxt[nxt[i]];
            if(siz[j]>siz[nxt[i]] || siz[i]>siz[nxt[i]]){
                siz[i]+=siz[j]+siz[nxt[i]];
                link(i, nxt[j]);
                flag=1;
                if(pre[i]) i=pre[pre[i]];
            } else i=j;
        }
        if(!flag) break;
    }
    return !nxt[1];
}
}

void run(){
    cin>>s+1>>t+1;
    n=strlen(s+1);
    for(int i=1; i<=n;){
        int pos=i;
        while(pos<=n && t[pos]==t[i]) ++pos;
        if(i!=1 && s[i]==s[i-1] || pos!=n+1 && s[pos]==s[pos-1]){
            cout<<"No\n";
            return;
        }
        sub::n=pos-i;
        rep(j, 1, pos-i)   
            sub::s[j]=s[i+j-1], sub::t[j]=t[i+j-1];
        if(!sub::check()){
            cout<<"No\n";
            return;
        }
        rep(j, i, pos-1) s[j]=t[j];
        i=pos;
    }
    cout<<"Yes\n";
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin>>t;
    while(t--) run();
}

都看到这里了，点个赞再走呗。