HDOJ 5802 windows 10

这波黑windows黑得很好我给满分，题目链接：HDOJ5802

看到两个数字的题，而且p，q都很大，不超过1e9，很明显数学题，先找规律，要么是公式，要么是打表，要么是贪心之类的算法

题意：p和q两个数，要求用最小步数从p走到q

如果选择减少，那么第一个单位时间减少1，如果前一个单位时间减少的是x，那么该单位时间减少2*x（相当于连击）

如果选择增加，那么每个单位时间增加1

如果选择休息，那么没有变化、

增加和休息对于减少来说都是打破连击

这样读完题，有一个很坑的边界条件，估计是比赛的时候很多队伍没有注意到的细节：

最大值无限，最小值不小于0

那么意味着什么呢？

100 95和6 1这两组数据的答案不一样！虽然都是差值都是5，但是走的路径是不一样的

100-99-97-93-94-95：需要5步

6-5-3-0-1：需要4步

因为最多到0，所以当减不动了的时候，直接跳到0

贪心的思路其实很明显：先判断p和q的大小，如果q不小于p，那么答案是q-p，因为只能一步一步往上爬

要么就是一直不断的减，减过分（减到不超过为止），然后再补回来，就是100 95的走法

要么就是减着减着停一下，减着减着加一下

减的次数其实是确定的，为int（log2（End-Start+1）），因为不能超过呗

细节有两个：

关注到0的细节，那么在判断的时候需要和0作判断

关注的停和加的细节，如果可以加，那么优先作加（因为如果停，最后再加，是浪费一步），需要从起点p到终点q，当前走了多少步，停了多少下作记录

代码如下：

int t;
__int64 q,p;
__int64 powtwo[1000];
__int64 dfs(__int64 S,__int64 T,__int64 step,__int64 stop){
	if (S==T) return step;
	__int64 x=S-T;
	int two=(int)log2(x+1);
	if (S-powtwo[two]+1==T) return step+two;
	two++;
	__int64 up=T-max((long long)0,S-powtwo[two]+1);
	__int64 tmp=two+max((long long)0,up-stop);
	return min(tmp+step,dfs(S-powtwo[two-1]+1,T,step+two,stop+1));
}

int main(){
	//freopen("input.txt","r",stdin);
	memset(powtwo,0,sizeof(powtwo));
	powtwo[0]=1;
	for(int i=1;;i++){
		powtwo[i]=2*powtwo[i-1];
		if (powtwo[i]>1e9) break;
	}
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%I64d%I64d",&p,&q);
		if (q>=p) cout<<q-p<<endl;
		else cout<<dfs(p,q,0,0)<<endl;
	}
	return 0;
}

有个类似的题：codeforces #356 div2 D

这个题也是类似的思路，因为数据量很大，也是几个数字，每次需要删除尽可能大的

如何制定正确的贪心策略？

其实这个题不要看m最多是1e15，其实立方数就1e6个，然后因为证明的数学规律给剪枝了很大一部分，每一步骤的选择，其实最多就是两种方案，所以，可以直接像贴的题解一样暴力搞好

贴个泰神的题解膜拜一发：泰神题解