二进制解题思路:
因为字符串太长,即使是unsigned long long
也没法存下,所以使用C++的bitset来进行操作,我们把字符串转换成二进制字符串,然后再转换成128位的bitset
。
bitset
遍历是从低位开始的,所以我们每次让fac
左移i
位和i+1
位,这样就把当前位置和下一个位置上的值变成了1
,其他位为0
,再与原字符串(二进制)进行异或,异或运算的性质是相同为0
,不同为1
,这样我们就模拟了翻转硬币的过程,在异或过程中其他位不受影响,只有翻转的这两位会进行改变。
#include <bits/stdc++.h>
using namespace std;
void change_binary(string &s1) {
for(auto &x: s1) {
if(x == '*') x = '1';
else x = '0';
}
}
int main() {
string s1, s2;
cin >> s1 >> s2;
change_binary(s1), change_binary(s2); // 将字符串变成二进制字符串
bitset<128> bs1(s1), bs2(s2), fac("1"); // 因为字符串长度不超过100位,所以我们设置为128位二进制
int tot = 0;
for(int i = 0; i < bs1.size() - 1; i++) {
if(bs1[i] != bs2[i]) {
bs1 ^= ((fac << i + 1) | (fac << i)); // 右边式子是把当前位置和下一位置成1,然后进行异或运算,相同为0,不同为1,这样就变成了翻转的过程了。
tot++;
}
}
cout << tot << endl;
}
tql
膜拜神犇