将0,1, 2^k-1 这些数分成M份，每份的值为该份的1的数字之和 ，求使最大的那一份最小 K <=100 ,M<=100
最大值最小化，二分的经典应用
思路：二分这个最大值X，然后看能不能组成M份 ，然后再调整
Cal(x)：求出0-x这些数字当中1出现的次数。
其实实际分析一下就很简单，把x化作是二进制的数，那么从高位往低位走，遇见一个1,假使这个位置在i位置，那么答案ans=ans+F[i-1]+j*2^(i-1)+1,其中j表示的是到现在位置所遇见的1的个数，F[i]表示的是0-2^i-1中所出现的1的个数，然后再加上之前出现的1的个数乘以该位出现1所经历的次数，再加上这个位置上自己出现的1的个数1，那么就是0-x出现1的次数。
Get(t):从高位往下走，看该位置是否可以添加一个1，跟上面类似。
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 using namespace std; 8 9 const int MAXN = 110; 10 int const N = 120; 11 12 struct bign 13 { 14 int len, s[MAXN]; 15 bign () 16 { 17 memset(s, 0, sizeof(s)); 18 len = 1; 19 } 20 bign (int num) 21 { 22 *this = num; 23 } 24 bign (const char *num) 25 { 26 *this = num; 27 } 28 bign operator = (const int num) 29 { 30 char s[MAXN]; 31 sprintf(s, "%d", num); 32 *this = s; 33 return *this; 34 } 35 bign operator = (const char *num) 36 { 37 for(int i = 0; num[i] == '0'; num++);//去前导0 38 len = strlen(num); 39 for(int i = 0; i < len; i++) 40 s[i] = num[len-i-1] - '0'; 41 return *this; 42 } 43 bign operator + (const bign &b) const //+ 44 { 45 bign c; 46 c.len = 0; 47 for(int i = 0, g = 0; g || i < max(len, b.len); i++) 48 { 49 int x = g; 50 if(i < len) x += s[i]; 51 if(i < b.len) x += b.s[i]; 52 c.s[c.len++] = x % 10; 53 g = x / 10; 54 } 55 return c; 56 } 57 bign operator += (const bign &b) 58 { 59 *this = *this + b; 60 return *this; 61 } 62 void clean() 63 { 64 while(len > 1 && !s[len-1]) len--; 65 } 66 bign operator * (const bign &b) //* 67 { 68 bign c; 69 c.len = len + b.len; 70 for(int i = 0; i < len; i++) 71 for(int j = 0; j < b.len; j++) 72 c.s[i+j] += s[i] * b.s[j]; 73 for(int i = 0; i < c.len; i++) 74 { 75 c.s[i+1] += c.s[i]/10; 76 c.s[i] %= 10; 77 } 78 c.clean(); 79 return c; 80 } 81 bign operator *= (const bign &b) 82 { 83 *this = *this * b; 84 return *this; 85 } 86 bign operator - (const bign &b) 87 { 88 bign c; 89 c.len = 0; 90 for(int i = 0, g = 0; i < len; i++) 91 { 92 int x = s[i] - g; 93 if(i < b.len) x -= b.s[i]; 94 if(x >= 0) g = 0; 95 else 96 { 97 g = 1; 98 x += 10; 99 } 100 c.s[c.len++] = x; 101 } 102 c.clean(); 103 return c; 104 } 105 bign operator -= (const bign &b) 106 { 107 *this = *this - b; 108 return *this; 109 } 110 bign operator / (const int b) 111 { 112 bign c; 113 int f = 0; 114 for(int i = len-1; i >= 0; i--) 115 { 116 f = f*10+s[i]; 117 c.s[i]=f/b; 118 f=f%b; 119 } 120 c.len = len; 121 c.clean(); 122 return c; 123 } 124 bign operator / (const bign &b) 125 { 126 bign c, f = 0; 127 for(int i = len-1; i >= 0; i--) 128 { 129 f = f*10; 130 f.s[0] = s[i]; 131 while(f >= b) 132 { 133 f -= b; 134 c.s[i]++; 135 } 136 } 137 c.len = len; 138 c.clean(); 139 return c; 140 } 141 bign operator /= (const bign &b) 142 { 143 *this = *this / b; 144 return *this; 145 } 146 bign operator % (const bign &b) 147 { 148 bign r = *this / b; 149 r = *this - r*b; 150 return r; 151 } 152 bign operator %= (const bign &b) 153 { 154 *this = *this % b; 155 return *this; 156 } 157 bign operator ^ (const int & n) //大数的n次方运算 158 { 159 bign t(*this),ret(1); 160 if(n<0) exit(-1); 161 if(n==0) return 1; 162 int m=n; 163 while (m) 164 { 165 if (m&1) ret=ret*t; 166 t=t*t; 167 m>>=1; 168 } 169 return ret; 170 } 171 bool operator < (const bign &b) 172 { 173 if(len != b.len) return len < b.len; 174 for(int i = len-1; i >= 0; i--) 175 if(s[i] != b.s[i]) return s[i] < b.s[i]; 176 return false; 177 } 178 bool operator > (const bign &b) 179 { 180 if(len != b.len) return len > b.len; 181 for(int i = len-1; i >= 0; i--) 182 if(s[i] != b.s[i]) return s[i] > b.s[i]; 183 return false; 184 } 185 bool operator == (const bign &b) 186 { 187 return !(*this > b) && !(*this < b); 188 } 189 bool operator != (const bign &b) 190 { 191 return !(*this == b); 192 } 193 bool operator <= (const bign &b) 194 { 195 return *this < b || *this == b; 196 } 197 bool operator >= (const bign &b) 198 { 199 return *this > b || *this == b; 200 } 201 string str() const 202 { 203 string res = ""; 204 for(int i = 0; i < len; i++) res = char(s[i]+'0') + res; 205 return res; 206 } 207 }; 208 209 istream& operator >> (istream &in, bign &x) 210 { 211 string s; 212 in >> s; 213 x = s.c_str(); 214 return in; 215 } 216 217 ostream& operator << (ostream &out, const bign &x) 218 { 219 out << x.str(); 220 return out; 221 } 222 bign pow2[N],F[N]; 223 int m,k; 224 void pre() 225 { 226 pow2[0]=1; 227 for(int i=1; i<=100; i++)pow2[i]=pow2[i-1]*2; 228 F[1]=1; 229 for(int i=2; i<=100; i++)F[i]=F[i-1]*2+pow2[i-1]; 230 return ; 231 } 232 bign cal(bign x) 233 { 234 bign p=0; 235 int num[110]; 236 int top=0; 237 while(x.len>1||x.s[0]) 238 { 239 num[top++]=(x.s[0]%2)?1:0; 240 x=x/2; 241 } 242 bign ans=0; 243 int j=0; 244 for(int i=top-1; i>=0; i--) 245 { 246 if(num[i]) 247 { 248 ans+=(F[i]+pow2[i]*j+1); 249 j++; 250 } 251 } 252 return ans; 253 } 254 bign get(bign t) 255 { 256 bign ans=0; 257 int j=0; 258 for(int q=k; q>=0; q--) 259 { 260 bign num; 261 if(q==0) 262 num=j+1; 263 else 264 num=(F[q]+pow2[q]*j+1); 265 if(t>=num) 266 { 267 ans=ans+pow2[q]; 268 t-=num; 269 j=j++; 270 } 271 } 272 return ans; 273 } 274 int main() 275 { 276 pre(); 277 cin>>k>>m; 278 bign l=1,r=F[k],sta=pow2[k]-l; 279 while(l<r) 280 { 281 bign now=0; 282 bign mid=(l+r)/2; 283 int i; 284 for(i=1; i<=m; i++) 285 { 286 now=get(now+mid); 287 if(now>=sta)break; 288 now=cal(now); 289 } 290 if(i>m)l=mid+1; 291 else r=mid; 292 } 293 cout<<l<<endl; 294 return 0; 295 }