自动搬运

查看原文

来自洛谷，原作者为

	Dog_Two **

搬运于2025-08-24 21:37:38，当前版本为作者最后更新于2018-10-19 10:11:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

与原题题解相对地，我们考虑倒序减。

用一个k位全为1的整数val表示初始的月饼集合，根据进制知识易知，这个整数的值就是这些月饼的重量和。

这个整数应当是第一个恰好不小于B的二进制全1数字。

此后，我们从这个数的最高位(恰好是2^(k-1))开始向低位考虑，算法流程如下：

• 减去这个数（2^(k-1)）后，月饼的重量和小于A,则不考虑这一位；
• 否则，使这一位变成0，也即减去2^(k-1)；
• 如果月饼集合恰好不大于B，跳出。

下面说明算法的正确性：

对于初始的月饼集合取值来说：

• 最优解一定能表示为一个若干位为1的二进制数。初始值取全1二进制数不会导致更差的解，因为在集合的角度，最优解是val的一个子集；

• 同上，初始值如果取小于B的全1二进制数，可能不包含最优解集合，而val不会带来错误的解，故初始值不应当小于B；

• 如果我们取了大于题设val的全1二进制数（设为S）作初始值，易知，S的最高位表示(val+1)*2，删去后仍然大于B，在算法流程中，我们会将其删去，它一定不会为解带来贡献，故不选大于val的值作初始值。

综上，我们通过全1二进制数作初始值的 正确性、决策（答案）包容性、不冗余性说明了恰好不小于B的全1二进制数作初始值的正确性。

对于算法流程本身来说

• 如果当前只需按照算法流程再减去1位（a=2^k）即求得最优解，设当前的值为num,应当有num-a∈[A,B]。

• 不妨设num-a'∈[A,B]。可以发现，a'!=a时，不存在花费不超过1的转移方法，故a取2^k时是“临界”状态的最优解。

• 对于上述可以导致最优解的num，设从num+b转移而来（num=num+b-b）。

• 显然，num+b->num的转移以1为代价时，解最优，所以，b是2的幂次。

• 根据归纳法，一个能导致最优解的状态，一定是从初态val不断减去2的一个幂次转移来的。

• 初态val(全1二进制数)包含正解的正确性我们已经证明。

论毕

代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
ULL A,B;
int main(){
	cin>>A>>B;
	ULL val=1;
	while(val<B) val=(val<<1)+1;
	ULL Bit=(val+1)>>1;
	for(;val>B;Bit>>=1){
		val=val-Bit<A?val:val-Bit;
	}
	int cnt=0;
	for(;val;val>>=1) if(val&1) ++cnt;
	cout<<cnt;
	return 0;
}