字符串经过一次操作以后,首尾字符一定只能是1,根据这一点,就可以写判断语句:
当目标字符串的最后一个字符的值为0的话,那么一定不可能,输出NO,然后结束即可
然后不论是使用dfs还是bfs搜索的方式,都需要限制字符串长度,10^18是60个二进制位,所以长度限制在70就可以了。
其他的也没什么要注意的地方,总之这个题2000的难度个人觉得打的偏高了一些。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
inline string toBi(ll x){
if(x==0)return "";
string s=toBi(x>>1);
s.push_back((x&1)+'0');
return s;
}
inline string chang(string p){
while(p.back()=='0') p.pop_back();
reverse(p.begin(),p.end());
return p;
}
map<string,int> mp;
queue<string> q;
bool bfs(string s,string en){
q.push(s);
mp[s]=1;
while(!q.empty()){
string tmp=q.front();
q.pop();
if(tmp==en) return 1;
if(tmp.size()>100) continue;
for(int i=0;i<=1;i++){
string p="";
if(i==0){
p=tmp+'0';
}
else{
p=tmp+'1';
}
string pc=chang(p);
if(pc==en) return 1;
if(!mp.count(pc)){
mp[pc]=1;
q.push(pc);
}
}
}
return 0;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
ll x,y; cin>>x>>y;
string st=toBi(x);
string en=toBi(y);
// cout<<st<<" "<<en<<endl;
if(st==en||st+'1'==en){
cout<<"YES"<<endl;
return 0;
}
// cout<<*en.begin()<<" "<<*(en.end()-1);
if(*en.begin()=='0'||*(en.end()-1)=='0'){
cout<<"NO"<<endl;
return 0;
}
if(bfs(st,en)) cout<<"YES"<<endl;
else{
cout<<"NO"<<endl;
}
return 0;
}