题目背景

Bessie 刚刚学会了不同进制数之间的转换，但是她总是犯错误，因为她的两个前蹄不能轻松的握住钢笔。

题目描述

每当 Bessie 将一个数转换成新的进制时，她总会写错一位数字。例如，她将 14 转化成 2 进制数，正确的结果是 1110，但她可能会写成 0110 或 1111。Bessie 从不会意外的增加或删减数字，所以她可能会写出以 0 开头的错误数字。

给出 Bessie 转换后 NNN 的 2 进制形式和 3 进制形式，请计算出 NNN 的正确数值（用十进制表示）。NNN 可能会达到 10910^9109，输入数据保证解的存在唯一性。

输入格式

第一行，NNN 的 2 进制表示（有一位是错误的数字）。

第二行，NNN 的 3 进制表示（有一位是错误的数字）。

输出格式

NNN 的正确值。

样例 #1

样例输入 #1

1010
212

样例输出 #1

14

解题思路：

最容易想到的就是暴力枚举，将二进制的每一种可能错误与三进制的每一种可能错误比较，相同则为答案

这里不对这种方法进行说明，采用另一种方法

利用异或^的性质，枚举每一种二进制的可能错误

考虑到在三进制只错一位的前提下，如果得出的N是正确值

那么将abs(正确数 - 三进制错误数)写成i∗3ji * 3^ji∗3j的形式，一定可以得到i<3i < 3i<3

从而得出时间复杂度接近o(n)的算法

AC代码如下

#include 
#include 
using namespace std;long long binTodec(string str) {//二进制转十进制int len = int(str.size());int power = 1;long long sum = 0;for (int i = len - 1; i >= 0; i--) {sum += power * (str[i] - '0');power *= 2;}return sum;
}long long threeTodec(string str) {//三进制转十进制int len = int(str.size());int power = 1;long long sum = 0;for (int i = len - 1; i >= 0; i--) {sum += power * (str[i] - '0');power *= 3;}return sum;
}int main() {string str_1, str_2;cin >> str_1 >> str_2;long long t_1 = binTodec(str_1);long long t_2 = threeTodec(str_2);int power = pow(2, int(str_1.size()) - 1);for (int i = 0; i < int(str_1.size()); i++, power /= 2) {//枚举二进制错误long long t_3, t_4;if ((str_1[i] - '0') ^ 1)//异或操作t_3 = abs((t_4 = t_1 + power) - t_2);elset_3 = abs((t_4 = t_1 - power) - t_2);while (t_3 % 3 == 0) t_3 /= 3;//检测是否正确if (t_3 < 3) {cout << t_4 << endl;break;}}return 0;
}

这里简单说明一下，为什么不可能有第二个N使得判定条件成立

众所周知，暴力枚举一定可以得出正确答案

如果有第二个N可以使得差值写成i∗3ji * 3^ji∗3j，那么对于暴力枚举，这个N同样也是正确的

因为暴力枚举可以把三进制的j+1j+1j+1位修改，使得二进制修改后的值与之相等