尴尬的数字（C++，数学）

<>题目背景

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

<>题目描述

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

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

<>输入格式

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

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

<>输出格式

N N N 的正确值。

<>样例 #1

<>样例输入 #1
1010 212
<>样例输出 #1
14
<>解题思路：

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

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

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

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

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

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

AC代码如下
#include <iostream> #include <cmath> 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); else t_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 ∗ 3 j i * 3^j i∗3j，那么对于暴力枚举，这个N同样也是正确的

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

• « 上一篇：Go基础知识巩固
• » 下一篇：十大排序（Java版本）