考试的时候打的表
数据比较水竟然有90分 -_-
以后还是尽量不要打表了 >_<
毕竟我辛辛苦苦打了个表
还是把代码贴出来一下 >_<
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 typedef long long LL; 6 7 LL a[210]={ 8 483212, 9 912008, 10 1496047, 11 1936710, 12 2497049, 13 2953836, 14 3372377, 15 3666046, 16 4224609, 17 4888435, 18 5470687, 19 5985204, 20 6473508, 21 6997710, 22 7407121, 23 7759888, 24 8114246, 25 8841202, 26 9418915, 27 9988999, 28 10387703, 29 10975302, 30 11401951, 31 11825190, 32 12093372, 33 12647109, 34 13090291, 35 13513784, 36 13806423, 37 14173972, 38 14478373, 39 14726176, 40 14902859, 41 15366960, 42 16201541, 43 16950748, 44 17658367, 45 18268984, 46 18993614, 47 19575038, 48 20140363, 49 20548986, 50 21286246, 51 21888932, 52 22491383, 53 22921271, 54 23499961, 55 23944182, 56 24358905, 57 24649517, 58 25239333, 59 25899457, 60 26483106, 61 26967731, 62 27475420, 63 27991458, 64 28403584, 65 28751667, 66 29097194, 67 29645428, 68 30054847, 69 30430558, 70 30692950, 71 31084403, 72 31322215, 73 31584664, 74 31722784, 75 32527953, 76 33310112, 77 34055961, 78 34701584, 79 35395499, 80 36047985, 81 36635786, 82 37121164, 83 37692107, 84 38382504, 85 38971194, 86 39498926, 87 39958625, 88 40492390, 89 40907482, 90 41282752, 91 41573188, 92 42308110, 93 42882438, 94 43478493, 95 43906876, 96 44492036, 97 44934441, 98 45350847, 99 45627800, 100 46146335, 101 46616525, 102 47028856, 103 47334412, 104 47671874, 105 48002942, 106 48259763, 107 48448125, 108 48799637, 109 49508491, 110 50092717, 111 50647285, 112 51071367, 113 51639722, 114 52038237, 115 52431729, 116 52694622, 117 53287273, 118 53720987, 119 54139486, 120 54415411, 121 54804200, 122 55096784, 123 55348037, 124 55513038, 125 55922617, 126 56415984, 127 56836115, 128 57174501, 129 57496304, 130 57845934, 131 58089661, 132 58302816, 133 58498196, 134 58876476, 135 59121009, 136 59354387, 137 59477906, 138 59739331, 139 59878002, 140 60014029, 141 60076643, 142 60832929, 143 61739336, 144 62607725, 145 63415911, 146 64214443, 147 65027775, 148 65781109, 149 66473788, 150 67140388, 151 67984879, 152 68727353, 153 69442860, 154 70048316, 155 70777285, 156 71356714, 157 71927618, 158 72320180, 159 73203960, 160 73972480, 161 74726814, 162 75349646, 163 76062801, 164 76700591, 165 77294730, 166 77764296, 167 78374089, 168 79037922, 169 79616994, 170 80132387, 171 80621812, 172 81145062, 173 81554249, 174 81907967, 175 82276494, 176 83133241, 177 83872636, 178 84609414, 179 85185284, 180 85934320, 181 86540180, 182 87140810, 183 87576880, 184 88275274, 185 88900647, 186 89499996, 187 89967525, 188 90493471, 189 90975179, 190 91381110, 191 91701463, 192 92183365, 193 92877836, 194 93467319, 195 93999860, 196 94444353, 197 94999986, 198 95405882, 199 95788119, 200 96047470, 201 96620172, 202 97037422, 203 97462900, 204 97725833, 205 98136940, 206 98409864, 207 98663526, 208 }; 209 210 LL b[200]={ 211 5968886, 212 11243116, 213 15728885, 214 19977450, 215 23742586, 216 26825321, 217 29988136, 218 37722887, 219 44348908, 220 49885247, 221 55952873, 222 61179791, 223 65848128, 224 70605759, 225 76279689, 226 81087875, 227 84768321, 228 89532783, 229 92834015, 230 95389860, 231 100753595, 232 105845979, 233 110681368, 234 114754247, 235 118861938, 236 122113796, 237 124202254, 238 129175850, 239 132634835, 240 135215616, 241 138151826, 242 140103761, 243 142159061, 244 145676223, 245 154286892, 246 162229171, 247 169004383, 248 176847065, 249 183627622, 250 189525338, 251 196226774, 252 203077572, 253 209560954, 254 215092768, 255 221053707, 256 226125509, 257 229711631, 258 237020858, 259 243818679, 260 249959946, 261 255808107, 262 261213302, 263 265920538, 264 270128667, 265 276330227, 266 281336425, 267 285120550, 268 289566980, 269 293272103, 270 296218783, 271 301017637, 272 308160727, 273 314607356, 274 319934458, 275 326328478, 276 331267910, 277 335276713, 278 340980145, 279 346103089, 280 350890778, 281 354914181, 282 359013078, 283 362228743, 284 364513480, 285 371015226, 286 376109973, 287 380220045, 288 384665356, 289 388003472, 290 391380940, 291 394583215, 292 398729717, 293 402024407, 294 403997903, 295 407419640, 296 409494154, 297 410929557, 298 416914502, 299 425059616, 300 432960740, 301 440011953, 302 447454766, 303 454136937, 304 459359934, 305 466916430, 306 473706592, 307 479725007, 308 485658073, 309 490963408, 310 495757923, 311 500152917, 312 507806886, 313 514423482, 314 519867197, 315 525902906, 316 531237422, 317 535765939, 318 540739878, 319 }; 320 321 int main() { 322 int l,r; 323 scanf("%d%d",&l,&r); 324 if (l==1 && r==2000000000) { 325 printf("937891981"); 326 return 0; 327 } 328 if (r-l<=1000000) { 329 LL ans=0; 330 for (int i=l;i<=r;i++) { 331 char ch[40]; 332 itoa(i,ch,2); 333 int aa=0,bb=0; 334 for (int j=0;j<strlen(ch);j++) { 335 if (ch[j]=='0') aa++; 336 else bb++; 337 } 338 if (aa>=bb) ans++; 339 } 340 printf("%lld",ans); 341 return 0; 342 } 343 344 l--; 345 LL ansl=0,ansr=0; 346 if (l/1000000==0) { 347 for (int i=1;i<=l;i++) { 348 char ch[40]; 349 itoa(i,ch,2); 350 int aa=0,bb=0; 351 for (int j=0;j<strlen(ch);j++) { 352 if (ch[j]=='0') aa++; 353 else bb++; 354 } 355 if (aa>=bb) ansl++; 356 } 357 } 358 else { 359 if (l/1000000>200) { 360 ansl=a[199]; 361 if ((l-200000000)/10000000==0) { 362 for (int i=200000001;i<=l;i++) { 363 char ch[40]; 364 itoa(i,ch,2); 365 int aa=0,bb=0; 366 for (int j=0;j<strlen(ch);j++) { 367 if (ch[j]=='0') aa++; 368 else bb++; 369 } 370 if (aa>=bb) ansl++; 371 } 372 } 373 else { 374 ansl+=b[(l-200000000)/10000000-1]; 375 for (int i=((l-200000000)/10000000)*10000000+1;i<=l;i++) { 376 char ch[40]; 377 itoa(i,ch,2); 378 int aa=0,bb=0; 379 for (int j=0;j<strlen(ch);j++) { 380 if (ch[j]=='0') aa++; 381 else bb++; 382 } 383 if (aa>=bb) ansl++; 384 } 385 } 386 } 387 else { 388 ansl=a[l/1000000-1]; 389 for (int i=(l/1000000)*1000000+1;i<=l;i++) { 390 char ch[40]; 391 itoa(i,ch,2); 392 int aa=0,bb=0; 393 for (int j=0;j<strlen(ch);j++) { 394 if (ch[j]=='0') aa++; 395 else bb++; 396 } 397 if (aa>=bb) ansl++; 398 } 399 } 400 } 401 402 403 404 405 if (r==2000000000) ansr=937891981; 406 else { 407 if (r/1000000==0) { 408 for (int i=1;i<=r;i++) { 409 char ch[40]; 410 itoa(i,ch,2); 411 int aa=0,bb=0; 412 for (int j=0;j<strlen(ch);j++) { 413 if (ch[j]=='0') aa++; 414 else bb++; 415 } 416 if (aa>=bb) ansr++; 417 } 418 } 419 else { 420 if (r/1000000>200) { 421 ansr=a[199]; 422 if ((r-200000000)/10000000==0) { 423 for (int i=200000001;i<=r;i++) { 424 char ch[40]; 425 itoa(i,ch,2); 426 int aa=0,bb=0; 427 for (int j=0;j<strlen(ch);j++) { 428 if (ch[j]=='0') aa++; 429 else bb++; 430 } 431 if (aa>=bb) ansr++; 432 } 433 } 434 else { 435 ansr+=b[(r-200000000)/10000000-1]; 436 for (int i=((r-200000000)/10000000)*10000000+1;i<=r;i++) { 437 char ch[40]; 438 itoa(i,ch,2); 439 int aa=0,bb=0; 440 for (int j=0;j<strlen(ch);j++) { 441 if (ch[j]=='0') aa++; 442 else bb++; 443 } 444 if (aa>=bb) ansr++; 445 } 446 } 447 } 448 else { 449 ansr=a[r/1000000-1]; 450 for (int i=(r/1000000)*1000000+1;i<=r;i++) { 451 char ch[40]; 452 itoa(i,ch,2); 453 int aa=0,bb=0; 454 for (int j=0;j<strlen(ch);j++) { 455 if (ch[j]=='0') aa++; 456 else bb++; 457 } 458 if (aa>=bb) ansr++; 459 } 460 } 461 } 462 } 463 464 printf("%lld",ansr-ansl); 465 }
下面是正解
对于 x
先取位数比x小的数 用组合数就能求解
再用类似数位dp的思想
对于每一个为1的位
把他取成0
再对剩下的位数用组合数求解
详见程序
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define N 40 5 6 int c[N][N]; 7 int num[N]; 8 9 int _make(int x) { 10 if (x==0) return 0; 11 int k=0; 12 while (x!=0) { 13 k++; 14 num[k]=x%2; 15 x=x/2; 16 } 17 int ans=0; 18 for (int i=1;i<k;i++) { 19 for (int j=i-1;j>=0 && j>=i-j;j--) { 20 ans+=c[i-1][j]; 21 } 22 } 23 int a=1,b; 24 for (int i=k-1;i>1;i--) { 25 if (num[i]==1) { 26 b=k-i-a+1; 27 for (int j=i-1;j>=0 && j+b>=a+i-1-j;j--) { 28 ans+=c[i-1][j]; 29 } 30 a++; 31 } 32 } 33 if (num[1]==1) { 34 b=k-a; 35 if (b>=a) ans++; 36 a++; 37 } // 标程没有这一段 不过如果不特判最后一位我的程序有错 38 if (k-a>=a) ans++; 39 return ans; 40 } 41 42 int main() { 43 memset(c,0,sizeof(c)); 44 for (int i=1;i<N;i++) { 45 c[i][i]=c[i][0]=1; 46 for (int j=1;j<i;j++) { 47 c[i][j]=c[i-1][j]+c[i-1][j-1]; 48 } 49 } 50 51 int l,r; 52 scanf("%d%d",&l,&r); 53 printf("%d",_make(r)-_make(l-1)); 54 }