题目链接:http://codeforces.com/problemset/problem/279/E
题目大意:
给定一个长度不超过10^6的二进制数n,求至少要用几个(+ 或 -)2^k(k为整数)加起来才等于n.
题目思路
太久没做题了,理思路理了好久...
(1)可以知道一串连续的1最多只要2个数即可表示( 2^x + (-2^0) ),当然咯,单个1只要1个数即可.
(2)设串的长度为n,借鉴表示连续1的方法,那么需要个数为该串止于最后一个1中0的个数+2,
例如: 1110101011010000
10000000000000000
- 1110101011010000
= 1010100110000
由于最后一个1借位,使得2^x,与其对应的位起之前的全为1(除了最高位).
(3)设串110..01..1,(..表示不确定个数),我们要判断是否对整个串进行(2)的方法得到n能否更优,只要判断
0..0中0的个数和1..1的个数即可,很显然0的个数肯定不可以大于1的个数,且由(1)可得0的个数不能大于2,
因为不论几个1连续,最多只要2个数即可表示.
代码:
#include <stdlib.h> #include <string.h> #include <stdio.h> #include <ctype.h> #include <math.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <string> #include <iostream> #include <algorithm> using namespace std; //#define ll __int64 #define ls rt<<1 #define rs ls|1 #define lson l,mid,ls #define rson mid+1,r,rs #define middle (l+r)>>1 #define eps (1e-8) #define clr_all(x,c) memset(x,c,sizeof(x)) #define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1)) #define MOD 1000000007 #define INF 0x3f3f3f3f #define PI (acos(-1.0)) #define _mod(x,y) ((x)>0? (x)%(y):((x)%(y)+(y))%(y)) #define _abs(x) ((x)<0? (-(x)):(x)) #define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x)) #define getmax(x,y) (x= ((y)>(x))? (y):(x)) template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;} template <class T> T _max(T x,T y){return x>y? x:y;} template <class T> T _min(T x,T y){return x<y? x:y;} int TS,cas=1; const int M=1000000+5; char str[M]; void run(){ int i,j; int ret=0,len=strlen(str); for(i=0;i<len;i++){ if(str[i]=='1'){ int cnt=0; for(;str[i]=='1';i++) cnt++; if(cnt==1) ret++; else{ ret+=2; while(1){ cnt=0; for(;str[i]=='0';i++) cnt++; if(i>=len) break; if(cnt==1){ for(;str[i]=='1';i++); ret++; } else if(cnt==2){ cnt=0; for(;str[i]=='1';i++) cnt++; if(cnt==1){ret++;break;} else ret+=2; }else{i--;break;} } } } } printf("%d\n",ret); } void preSof(){ } int main(){ //freopen("inputxt","r",stdin); //freopen("outputxt","w",stdout); preSof(); //run(); while(~scanf("%s",str)) run(); //for(scanf("%d",&TS);cas<=TS;cas++) run(); return 0; }