首页 > 其他分享 >abc188F - +1-1x2

abc188F - +1-1x2

时间:2023-09-21 09:59:24浏览次数:39  
标签:abc188F dfs 1x2 include ll define

F - +1-1x2

做过好几道类似的题了,跟之前杭电的一道题很像。

反正就是在一个y的位置上下抖一抖再除2就行。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;

ll deep,n;
map<ll,ll> f; 
map<ll,bool> bz;

void dfs(ll y){
	if (y<=n) {
		f[y]=n-y;
		return;
	}
	if (y==2) {
 		f[2]=1;
 		return;
	}
	
	if (f.find(y)!=f.end()) return;
	
	if (y%2==0) {
		dfs(y/2);
		dfs(y/2+1);
		dfs(y/2-1);
		
		f[y]=min(min(y-n,f[y/2]+1),2+min(f[y/2+1],f[y/2-1]));
	}	
	else {
		dfs(y/2);
		dfs(y/2+1);
		
		f[y]=min(min(f[y/2],f[y/2+1])+2, y-n);
	}

}
int main(){
	
//	freopen("data.in","r",stdin);
	
	ll x,y;
	scanf("%lld %lld",&x,&y);
	n=x;
	
	f[x]=0;
	if (x>y) {
		printf("%lld",x-y);
		return 0;
	}
	dfs(y);
	
	printf("%lld",f[y]);
	
	return 0;
	
}

 
 
 

标签:abc188F,dfs,1x2,include,ll,define
From: https://www.cnblogs.com/ganking/p/17719158.html

相关文章