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

· · 题解

这场比赛太难了，我也太菜了，只做出来这一道题。

简化题目

初始有一个空字符串 s，问经过若干次操作后，能否变成字符串 str。

操作：

打个比方，s 现在为 ba，我们可以在后面加上 c，也可以把后面的 a 换成 c。

思路

第一个难点是长度，怎么把他变成 n 那么大呢？

很明显，只能用操作一，但是不能重复，所以我们可以一旦字符种类出现第三种，我们就用操作二把他给替换掉，然后再加一个第三种字符。我们把第三种字符种类称为其他字符。

注意到操作二只不能对第一个字符操作，所以在操作一的时候就应该加 str_0，我们把这个字符称为头字符。

所以流程就是先加入一个头字符，再加入另外两种字符中其中任意一种字符（让我们把它称为中字符），再加入其他字符，把其他字符串换成首字符后再加入其他字符，把其他字符串换成中字符后再加入其他字符······

然后就得到了一个长度为 n 的字符串 st，重复首字符和中字符）。

接下来看看 st_i 和 str_i 的关系，如果相等，就不操作。如果是其他字符，就能够通过操作二实现，因为 st 由首字符和中字符组成。

如果两类都不符，那就特殊一点，对前面那一个字符进行操作二，再对当前这一个字符进行操作二，然后又对前面那一个字符进行操作二（两次操作二相当于没变，和异或很像）。

记得从后往前判断，不然前面的答案会影响后面的。

然后交了一发，结果错了？

原来因为超过了限制，所以错了几个点。

卡常

见过对时间、空间卡常的，没见过对答案卡常的。

优化方法1

所以流程就是先加入一个首字符，再加入另外两种字符中其中任意一种字符（让我们把它称为中字符）

注意到是任意，那么答案肯定不会是百分之百最优的，所以我们可以看看两种情况的答案，然后选最优的就可以了。

优化方法2

如果两类都不符，那就特殊一点，对前面那一个字符进行操作二，再对当前这一个字符进行操作二，然后又对前面那一个字符进行操作二（两次操作二相当于没变，和异或很像）。

两次操作二相当于没变，那是不是如果前面那一个字符后面本来就是要进行操作二的，那就不重复操作了。

这些优化方法本来就很玄学，如果被卡了叫我，我再优化优化。

代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    int t,id;
    char ch;
};
vector<node> v1,v2,v;
string str,s1,s2;
int n;
char a,b,c;
int main(){
    ios::sync_with_stdio(0);
    cout.tie(0);cin.tie(0);
    cin>>str;
    a=str[0];n=str.size();
    str=" "+str;
    if(a=='a') b='b',c='c';
    else if(a=='b') b='c',c='a';
    else if(a=='c') b='a',c='b';
    //
    v1.push_back(node{1,-1,a});
    s1+=a;
    v1.push_back(node{1,-1,b});
    s1+=b;
    for(int i=3;i<=n;i++){
        v1.push_back(node{1,0,c});
        v1.push_back(node{2,i,' '});
        if(i%2==1) s1+=a;
        else s1+=b;
    }
    s1=" "+s1;
    for(int i=n;i>=2;i--){
        if(s1[i]==str[i]) continue;
        else if(str[i]==c) v1.push_back(node{2,i,' '});
        else{
            v1.push_back(node{2,i-1,' '}),v1.push_back(node{2,i,' '});
            if(str[i-1]!=c){
                v1.push_back({2,i-1,' '});
            }else{
                i--;
            }
        }
    }
    //
    swap(b,c);
    v2.push_back(node{1,-1,a});
    s2+=a;
    v2.push_back(node{1,-1,b});
    s2+=b;
    for(int i=3;i<=n;i++){
        v2.push_back(node{1,0,c});
        v2.push_back(node{2,i,' '});
        if(i%2==1) s2+=a;
        else s2+=b;
    }
    s2=" "+s2;
    for(int i=n;i>=2;i--){
        if(s2[i]==str[i]) continue;
        else if(str[i]==c) v2.push_back(node{2,i,' '});
        else{
            v2.push_back(node{2,i-1,' '}),v2.push_back(node{2,i,' '});
            if(str[i-1]!=c){
                v2.push_back({2,i-1,' '});
            }else{
                i--;
            }
        }
    }
    //
    if(v1.size()<v2.size()) v=v1;
    else v=v2;
    cout<<v.size()<<"\n";
    for(int i=0;i<v.size();i++){
        if(v[i].t==1) cout<<1<<" "<<v[i].ch<<"\n";
        else cout<<2<<" "<<v[i].id<<"\n";
    }
    return 0;
}

时间复杂度为线性，但是常数大，卡卡常应该可以拿最优解。