把二进制数10换成01可以让10异或11，一个二进制数中相邻的两位如果不同，可以对应的异或0……0110……0，就可以把这两位换个位置。异或是个很好的运算，满足交换律和结合律，而且若有a xor b=c，则有a xor c=b,b xor c=a。
　　把输入的字符串转化成二进制串，源串和目标串异或就得到转化所需的0……0110……0操作序列的异或结果，把这个结果拆成操作序列就行了。由于操作序列的顺序不影响异或结果，所以从高位往低位拆就行了。拆不出来的，就是无解。
　　Submit 1: WA on 4。不仅拆不出来无解，拆得出来也可能无解。比如：

++++
----

就可以拆出来，但显然是无解的。
　　Submit 2: WA on 4。算法是错误的。只知道异或结果是无法把操作序列拆分出来的，比如：1100到0011需要4个操作:0110,1100,0011,0110，这四个操作中有两个重复的，他们异或结果为0，就导致了无法被拆分出来。
　　任意两个不同的位都可以通过异或的方式交换，异或0……010……010……0就可以，而这个数可以拆成若干个0……0110……0。想来可以贪心，从源串左边开始，找到一对不同且各自与目标串相反的位，异或一下0……010……010……，然后再找，一直找到最后，如果源串不能变成目标串，那就无解。
　　Submit 3: AC。
　　后记：其实这题做起来完全没有必要牵扯到二进制和异或，但多想想总归是有益的。做题的意义不在于最后那个AC多么好看，而在于从看题开始到AC的所感所思。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//AC
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    bool chain1[5000],chain2[5000];
    int n,c(0);
    string ts;
    cin>>ts;
    n=ts.length();
    for (int i(0);i<n;++i) chain1[i]=ts[i]=='+';
    cin>>ts;
    if (ts.length()-n)
    {
        cout<<-1<<endl; return 0;
    }
    for (int i(0);i<n;++i) chain2[i]=ts[i]=='+';
    bool find(false);
    for (int i(0);i<n-1;++i) if (chain1[i]!=chain2[i])
    {
        find=false;
        for (int j(i+1);j<n;++j)
            if (chain1[j]!=chain1[i] && chain1[j]!=chain2[j])
            {
                find=true;
                c+=j-i;
                chain1[j]^=1;
                break;
            }
        if (!find)
        {
            cout<<-1<<endl; return 0;
        }
    }
    cout<<c<<endl;
    return 0;
}