题目
思路
题目意思是给一个数用不同进制表示的两串数,一串是二进制表示,一串是三进制表示,这两串数中都有一位写错了,求都写对的情况下,这个数是什么?
原数范围是$0<=N<=10^{9}$
用二进制表示的话,串长最多不超过$30$
可以直接枚举两串数的所有可能正确的情况,先枚举完一串的所有情况,把每种情况存入哈希表,然后再去枚举另一串,再枚举第二串的过程中,只要发现了相同的,就打印结果并退出。
代码
#include<iostream>
#include<string.h>
#include<unordered_set>
using namespace std;
const int N=35;
string bin,ter;
unordered_set<int> s;
void convert(int num) //算出三进制数某位出错后的结果,加入到s中
{
string t=ter;
int key=ter[num]-'0'; //锁定是什么出错了
for(int i=0;i<=2;i++) //遍历0,1,2,循环注定只会走两遍
{
if(i==key) continue;
t[num]=i+'0'; //转化成字符
int sum=0;
for(int j=0;j<t.size();j++)
sum=sum*3+t[j]-'0';
s.insert(sum);
}
}
int main()
{
cin>>bin>>ter;
for(int i=0;i<ter.size();i++)
convert(i);
for(int i=0;i<bin.size();i++)
{
string t=bin;
t[i]=1-(bin[i]-'0')+'0'; //最后要转化成字符
int sum=0;
for(int j=0;j<t.size();j++)
sum=sum*2+t[j]-'0';
if(s.count(sum))
{
printf("%d",sum);
return 0;
}
}
return 0;
}
易错点:
这里用string类型存每一串,每一串中的每一位都是字符,在字符和数字之间转换,要注意$+‘0’$和$-‘0’$的运用。非常容易出错!