526互联

2058. 笨拙的手指

发布时间 2023-04-05 14:26:45作者: bujidao1128

2058. 笨拙的手指

奶牛贝茜正在学习如何在不同进制之间转换数字。

但是她总是犯错误，因为她无法轻易的用两个前蹄握住笔。

每当贝茜将数字转换为一个新的进制并写下结果时，她总是将其中的某一位数字写错。

例如，如果她将数字 14 转换为二进制数，那么正确的结果应为 1110，但她可能会写下 0110 或 1111。

贝茜不会额外添加或删除数字，但是可能会由于写错数字的原因，写下包含前导 0 的数字。

给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果，请确定 N 的正确初始值（十进制表示）。

输入格式

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

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

输出格式

输出正确的 N 的值。

数据范围

0≤N≤109，且存在唯一解。

输入样例：

1010
212

输出样例：

14

样例解释

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

时/空限制：1s / 64MB

来源：USACO 2011 November Contest Bronze Division

分析

提交答案

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>

using namespace std;

int base(string s,int b)//表示将b进制下的string s转化称十进制数
{
    int res=0;
    for(auto x:s)//从高到低位，枚举每一位
        res=res*b+x-'0';
    return res;
}

int main()
{
    string x,y;///原数可能有前导0，所以原数在读的时候要用string来读入二进制表示和三进制表示的结果
    cin>>x>>y;
    
    unordered_set<int> hash;//定义一个哈希表
    
    for(int i=0;i<x.size();i++)//然后先将二进制表示枚举的结果放到哈希表当中
    {
        //这一位的值不是0就是1
        string s=x;//先把原字符串复制一遍
        //复制完之后，这一位的值需要变一下，第二位的值需要变一下
        s[i]^=1;//变一下，异或一个1就可以了。0的ASCll码是48，1的ASCll码是49，48^1的ASCll码是49（因为48是偶数，异或一个1等于加上一个1）,49^1的ASCll码是48（因为49是奇数，异或一个1等于减去一个1）
        if(s.size()>1&&s[0]=='0') continue;//原来的字符串是不能有前导0的，要把原来含有前导0的数字去掉
        hash.insert(base(s,2));//然后将这个值加到哈希表当中，二进制下的结果转化成十进制之后放到哈希表当中
    }
    
    for(int i=0;i<y.size();i++)
        for(int j=0;j<3;j++)//三进制的话，每一位有两种选择，所以可以0到3枚举一遍
            if(y[i]-'0'!=j)//如果第i位不等于j的话
            {
                string s=y;//原字符串复制一遍
                s[i]=j+'0';//先把第i位恢复为j
                if(s.size()>1&&s[0]=='0') continue;
                int n=base(s,3);
                if(hash.count(n))//判断这个数之前如果出现了的话，就把这个数输出就可以了
                    cout<<n<<endl;
            }
    
    return 0;
}