acwing-2058. 笨拙的手指(acwing-2058. Clumsy fingers)

奶牛贝茜正在学习如何在不同进制之间转换数字。
但是她总是犯错误,因为她无法轻易的用两个前蹄握住笔。
每当贝茜将数字转换为一个新的进制并写下结果时,她总是将其中的某一位数字写错。
例如,如果她将数字 14 转换为二进制数,那么正确的结果应为 1110,但她可能会写下 0110 或 1111。
贝茜不会额外添加或删除数字,但是可能会由于写错数字的原因,写下包含前导 0 的数字。
给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果,请确定 N 的正确初始值(十进制表示)。

输入格式

第一行包含 N 的二进制表示,其中一位是错误的。
第二行包含 N 的三进制表示,其中一位是错误的。

输出格式

输出正确的 N 的值。

数据范围

0≤N≤10^9,且存在唯一解。

输入样例:

1010
212

输出样例:

14

样例解释

14 在二进制下的正确表示为 1110,在三进制下的正确表示为 112。

本质:遍历所有出错组合

方法一:遍历每种出错的可能

比如样例共有4*3种可能,复杂度=n^2

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s1, s2;
    scanf("%s%s", &s1, &s2);
    int i, j;
    unsigned int num1 = 0, num2 = 0;
    unsigned int r = 1;
    for (i = s1.length() - 1; i >= 0; i--) {
        num1 += r * (s1[i] - '0');
        r <<= 1;
    }
    r = 1;
    for (i = s2.length() - 1; i >= 0; i--) {
        num2 += r * (s2[i] - '0');
        r *= 3;
    }
    unsigned int r2; r = 1;
    for (i = s1.length() - 1; i >= 0; i--) {
        int t = s1[i] - '0';
        if (t) num1 -= r; else num1 += r;
        r2 = 1;
        for (j = s2.length() - 1; j >= 0; j--) {
            for (int k = 0; k <= 2; ++k) {
                int u = s2[j] - '0';
                if(u == k) continue;
                num2 += (k - u) * r2;
                if (num1 == num2){
                    printf("%d", num1);
                    break;
                }
                num2 += (u - k) * r2;
            }
            r2 *= 3;
        }
        if (t) num1 += r; else num1 -= r;
        r <<= 1;
    }
}

方法二:借助unordered_set

借助unordered_set先记录所有可能的二进制数,在遍历三进制数时进行逐个对比

#include <bits/stdc++.h>
using namespace std;

// 秦九昭算法,仅限base<=10
int convert(string s, int base) {
    int res = 0;
    for (const auto &item : s)
        res = res * base + item - '0';
    return res;
}

int main() {
    string a, b;
    unordered_set<int> S;
    cin >> a >> b;
    for (auto &item : a) {
        item ^= 1; // 48->49 or 49->48
        S.insert(convert(a, 2));
        item ^= 1;
    }
    for (auto &item : b) {
        char t = item;
        for (char i = '0'; i < '3'; i++) {
            if (t == i) continue;
            item = i;
            int x = convert(b, 3);
            if (S.count(x)) {
                printf("%d", x);
                return 0;
            }
        }
        item = t;
    }
}
————————

Bessie the cow is learning how to convert numbers between different bases.
But she always makes mistakes because she can’t easily hold the pen with her two front feet.
Whenever Bessie converts a number to a new base and writes down the result, she always writes one of the numbers wrong.
For example, if she converts the number 14 to a binary number, the correct result would be 1110, but she might write 0110 or 1111.
Bessie will not add or delete additional numbers, but may write down numbers with leading zeros due to wrong numbers.
Given the result of Bessie’s conversion of the number n to binary and ternary digits, please determine the correct initial value of n (decimal representation).

Input format

The first line contains the binary representation of N, one of which is wrong.
The second line contains the ternary representation of N, one of which is wrong.

Output format

Output the correct value of n.

Data range

0 ≤ n ≤ 10 ^ 9, and there is a unique solution.

Input example:

1010
212

Output example:

14

Example explanation

14 is correctly represented as 1110 in binary and 112 in ternary.

Essence: traverse all error combinations

Method 1: traverse every possible error

For example, there are 4 * 3 possibilities in the sample, and the complexity = n ^ 2

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s1, s2;
    scanf("%s%s", &s1, &s2);
    int i, j;
    unsigned int num1 = 0, num2 = 0;
    unsigned int r = 1;
    for (i = s1.length() - 1; i >= 0; i--) {
        num1 += r * (s1[i] - '0');
        r <<= 1;
    }
    r = 1;
    for (i = s2.length() - 1; i >= 0; i--) {
        num2 += r * (s2[i] - '0');
        r *= 3;
    }
    unsigned int r2; r = 1;
    for (i = s1.length() - 1; i >= 0; i--) {
        int t = s1[i] - '0';
        if (t) num1 -= r; else num1 += r;
        r2 = 1;
        for (j = s2.length() - 1; j >= 0; j--) {
            for (int k = 0; k <= 2; ++k) {
                int u = s2[j] - '0';
                if(u == k) continue;
                num2 += (k - u) * r2;
                if (num1 == num2){
                    printf("%d", num1);
                    break;
                }
                num2 += (u - k) * r2;
            }
            r2 *= 3;
        }
        if (t) num1 += r; else num1 -= r;
        r <<= 1;
    }
}

方法二:借助unordered_set

With unordered_ Set first records all possible binary numbers and compares them one by one when traversing the ternary system

#include <bits/stdc++.h>
using namespace std;

// 秦九昭算法,仅限base<=10
int convert(string s, int base) {
    int res = 0;
    for (const auto &item : s)
        res = res * base + item - '0';
    return res;
}

int main() {
    string a, b;
    unordered_set<int> S;
    cin >> a >> b;
    for (auto &item : a) {
        item ^= 1; // 48->49 or 49->48
        S.insert(convert(a, 2));
        item ^= 1;
    }
    for (auto &item : b) {
        char t = item;
        for (char i = '0'; i < '3'; i++) {
            if (t == i) continue;
            item = i;
            int x = convert(b, 3);
            if (S.count(x)) {
                printf("%d", x);
                return 0;
            }
        }
        item = t;
    }
}