题目链接
题意:
在写代码时，我们经常要用到类似 x × a 这样的语句( a 是常数)。众所周知，计算机进行乘法运算是非常慢的，所以我们需要用一些加法、减法和左移的组合来实现乘一个常数这个操作。具体来讲， 我们要把 x × a 替换成：(x<<a0) op1 (x<<a1) op2 (x<<a2) ... opn (x<<an) 这样的形式，其中opi 是+或者-。
举个例子：x × 15 = (x<<4) - (x<<0)。
在本题中，假设左移（包括左移0）和加法、减法所需要的时间都是一个单位的时间，上述的例子所需要的时间是3。
现在给定常数 a 的二进制形式，求实现 x × a 最少需要多少单位的时间。
思路:
二幂拆分问题
看了上面的博客,就知道怎么做了,那位大佬分析的很详细,很彻底。
可以发现,所有的后缀都是x或者~x+1的后缀,而且所需要进行递归的次数就是所有的尾数-末尾0的个数.
这里我们采取记忆话搜索的逆递推.
u,d 分别代表x和~x+1的答案,然后自底向上进行递推
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; string s; int main() { cin>>s; int l=0,r=s.size()-1; while(s[l]=='0'&&l<s.size()) l++; while(r&&s[r]=='0') r--; if(r==0) { Pi(0); return 0; } int u=1,d=1; for(int i=r;i>=l;i--) { if(s[i]=='1')//这里因为x中为0的~x+1中正好为1,所以当x为1,是x中的后缀,为0是~x+1的后缀 u=min(u,d)+1; else d=min(u,d)+1; } Pi(2*u-1); return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
