题解：P15036 「chaynOI R2 T1」构造字符串

· · 题解

题目传送门

题目大意

题目已经够简短的了，没什么好说的了 qwq。

思路分析

先不顾一切地让 |S|=|T|，可以构造 ababab...，也可以构造 acacac...。

接下来 从后向前 修改答案，以构造 ababab... 为例，进行分类讨论：

  1. 若 S_{i}=T_{i}，无需进行修改；
  2. 若 S_{i}=\text{c}\text{且}T_{i}\ne S_{i-1}，对 S_{i} 进行一次操作二。
  3. 若 S_{i}=\text{c}\text{且}T_{i}=S_{i-1}，对 S_{i} 进行一次操作二，然后对 S_{i-1} 进行一次操作二，最后再对 S_{i} 进行一次操作二。
  4. 若 S_{i}\ne\text{c}\text{且}T_{i}=S_{i-1}，对 S_{i-1} 进行一次操作二，再对 S_{i} 进行一次操作二。
  5. 若 S_{i}\ne\text{c}\text{且}T_{i}\ne S_{i-1}，对 S_{i} 进行一次操作二。

情况 3 和情况 4 会把 S_{i-1} 修改为 \text{c}，所以会有 情况 1 和情况 2。

WA Code

#include<bits/stdc++.h>
using namespace std;
string s=" ",t;
struct answer{//用结构体存答案，原因见后文
    int p,x;//p 表示是操作几，如果是操作 2，记录修改位置为 x
    string s;//如果是操作1，直接记录要输出的东西
};
vector<answer>ans;
int n;
int main(){
    cin>>t,n=t.size(),t=' '+t;
    ans.push_back({1,-1,"1 a\n"}),ans.push_back({1,-1,"1 b\n"});
    for(int i=3;i<=n;i++)
        ans.push_back({1,-1,"1 c\n"}),ans.push_back({2,i,""});//构造初始字符串
    for(int i=1;i<=n;i++)
        s+=((i&1)?'a':'b');
    for(int i=n;i;i--)//修改
        if(s[i]==t[i])
            continue;
        else{
            if(s[i]=='c'&&s[i-1]!=t[i])
                s[i]=t[i],ans.push_back({2,i,""});
            else if(s[i]=='c')
                s[i]=t[i],s[i-1]='c',ans.push_back({2,i,""}),ans.push_back({2,i-1,""}),ans.push_back({2,i,""});
            else if(s[i-1]==t[i])
                s[i]=t[i],s[i-1]='c',ans.push_back({2,i-1,""}),ans.push_back({2,i,""});
            else
                ans.push_back({2,i,""});
        }
    cout<<ans.size()<<"\n";//输出
    for(auto x:ans)
        if(x.p==1)
            cout<<x.s;
        else
            cout<<"2 "<<x.x<<"\n";
    return 0;
}

优化答案

可以发现，上面的代码 WA 了。

分析原因，可以发现，当 T 为 abbaba... 时，每一位最多会被修改 5 次！我们只有 10^{6} 次修改机会，而上面的代码会进行约 1.1\times10^{6} 次修改，超出题目限制。

然而，我们也可以发现，能 HACK 构造 ababab... 的方法的数据 HACK 不了构造 acacac... 的方法，能 HACK 构造 acacac... 的方法的数据 HACK 不了构造 ababab... 的方法，两个方法一起用就过了呀！

AC Code

#include<bits/stdc++.h>
using namespace std;
string s=" ",t;
struct answer{
    int p,x;
    string s;
};
vector<answer>ans;
int n;
int main(){
    cin>>t,n=t.size(),t=' '+t;
    ans.push_back({1,-1,"1 a\n"}),ans.push_back({1,-1,"1 b\n"});
    for(int i=3;i<=n;i++)
        ans.push_back({1,-1,"1 c\n"}),ans.push_back({2,i,""});
    for(int i=1;i<=n;i++)
        s+=((i&1)?'a':'b');
    for(int i=n;i;i--)
        if(s[i]==t[i])
            continue;
        else{
            if(s[i]=='c'&&s[i-1]!=t[i])
                s[i]=t[i],ans.push_back({2,i,""});
            else if(s[i]=='c')
                s[i]=t[i],s[i-1]='c',ans.push_back({2,i,""}),ans.push_back({2,i-1,""}),ans.push_back({2,i,""});
            else if(s[i-1]==t[i])
                s[i]=t[i],s[i-1]='c',ans.push_back({2,i-1,""}),ans.push_back({2,i,""});
            else
                ans.push_back({2,i,""});
        }
    if(ans.size()>1e6){//超出限制，换方案 B！
        ans.clear(),s=" ";
        ans.push_back({1,-1,"1 a\n"}),ans.push_back({1,-1,"1 c\n"});
        for(int i=3;i<=n;i++)
            ans.push_back({1,-1,"1 b\n"}),ans.push_back({2,i,""});
        for(int i=1;i<=n;i++)
            s+=((i&1)?'a':'c');
        for(int i=n;i;i--)
            if(s[i]==t[i])
                continue;
            else{
                if(s[i]=='b'&&s[i-1]!=t[i])
                    s[i]=t[i],ans.push_back({2,i,""});
                else if(s[i]=='b')
                    s[i]=t[i],s[i-1]='b',ans.push_back({2,i,""}),ans.push_back({2,i-1,""}),ans.push_back({2,i,""});
                else if(s[i-1]==t[i])
                    s[i]=t[i],s[i-1]='b',ans.push_back({2,i-1,""}),ans.push_back({2,i,""});
                else
                    ans.push_back({2,i,""});
            }
    }
    cout<<ans.size()<<"\n";
    for(auto x:ans)
        if(x.p==1)
            cout<<x.s;
        else
            cout<<"2 "<<x.x<<"\n";
    return 0;
}