解题思路:
首先需要枚举,枚举方式有很多,最暴力的是将1e9内的数字全部枚举一遍其二进制形式和
a,b进行对比找到两者都相差一位二进制位数,当然这样肯定过不了,因为这样时间>1e8
在这里采用的枚举方式,也是容易想到的一种,变化a,b中的每一位数,得出对应的十进制数,并存入哈希表set中,找到两者唯一相交的那个十进制数,即是答案,这样时间复杂度是O(10^3)
10^9的二进制位数最多为30位,三进制位最多也就是30位。所以这样枚举时间复杂度很低
注意->秦九韶算法
代码:
#include<iostream>
#include<algorithm>
#include<unordered_set>
using namespace std;
int get(string s,int b){
int res=0;
for(auto &t:s){
res=res*b+t-'0';
}
return res;
}
int main(){
string a,b;
cin>>a>>b;
unordered_set<int>res;
for(auto &i:a){ //引用!!!
i=i^1; //这里是异或,'0'的ASCII码是48,'1'的ASCII码为49,异或后直接+1/-1
res.insert(get(a,2));
i=i^1;
//要变回原值,更改下一位数值
}
for(auto &j:b){ //这里一定要引用,因为要更改j的值,但是传入get函数的值是b,
//即b要通过引用更变数值
auto p=j;
for(int i=0;i<3;i++){
if(p!=i+'0'){
j=i+'0';
int t=get(b,3);
if(res.count(t)>0){
cout<<t<<endl;
return 0;
}
}
else{
continue;
}
}
j=p;//一定要记得变回来
}
return 0;
}