正題

$bzoj$題面鏈接:https://www.lydsy.com/JudgeOnline/problem.php?id=3758

---

題目大意

求$A～B$中有多少個數(shù)滿足數(shù)字上的位數(shù)可以分成兩個和相等的集合。

---

解題思路

首先我們考慮如何快速判斷一個數(shù)是否是滿足要求的數(shù)，我們可以用背包，設(shè)$f_i$表示$i$是否可行，若$f_{\frac{sum}{2}}$可行，就可行，那么有$$f_i=f_{i}or{f}_{i?nu{m}_i}$$。時間復雜度$:O(n?\frac{sum}{2})$其中$sum$最大為$81$，顯然不能勝任本題。

我們考慮優(yōu)化$f$，設(shè)$F$的第$i$位表示原來的$f_i$，那么我們將$F$左移$i$位就表示$F+i$的可行方案，也就有了$$F=ForF?2^{nu{m}_i}$$。時間復雜度$O(nlo{g}_{10}num)$

但是依舊不能勝任本題，我們考慮分段打表，數(shù)據(jù)最大為$10^9$那么讓初始數(shù)組$a_i$表示$i?10^6$時有多少個滿足條件的數(shù)字
那么每次處理讓前面一整塊的直接賦值，后面多余的暴力，時間復雜度$:O(N\%10^6)$

打表程序最后有

---

$ACcode$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int b[1100]={1, 376414,832548,1288829,1744957,2196801, 2647717,3090921,3526441,3951373,4366881, 4823016,5304767,5797145,6290673,6782005, 7272531,7758911,8238397,8710537,9182259, 9638540,10130919,10610576,11103530,11590746, 12080514,12565095,13045217,13523104,13996048, 14452176,14945704,15438659,15913606,16403908, 16892728,17371944,17858308,18339126,18810720, 19262564,19753896,20241112,20731415,21199400, 21684698,22170474,22655526,23128983,23601311, 24052227,24542753,25032521,25521341,26006640, 26480513,26967739,27450345,27929455,28401297, 28844501,29330881,29815462,30294678,30780454, 31267681,31727884,32207446,32681532,33151142, 33586662,34066148,34546270,35032634,35517686, 36000292,36479855,36928876,37398606,37865238, 38290170,38762310,39240197,39721015,40194472, 40673582,41147668,41617399,42050820,42514128, 42929636,43401358,43874302,44345896,44818224, 45290066,45759676,46226308,46689617,47111408, 47567543,48049294,48541672,49035200,49526532, 50017058,50503438,50982924,51455064,51926787, 52408538,52900917,53398018,53897102,54395977, 54894265,55390377,55882155,56370125,56858337, 57350716,57847817,58346902,58846683,59346651, 59846495,60345547,60842737,61337763,61832644, 62326172,62825257,63325038,63822619,64321882, 64821478,65319368,65818160,66315615,66811193, 67302525,67801400,68301369,68800632,69295187, 69792676,70292150,70790950,71286704,71781714, 72272240,72770528,73270372,73769969,74267458, 74763403,75261352,75759528,76256606,76751556, 77237936,77734048,78233100,78730990,79230465, 79728414,80220835,80714564,81209374,81704150, 82183636,82675414,83172604,83671396,84170196, 84668373,85162102,85646751,86134012,86626602, 87098742,87586712,88081738,88579193,89074947, 89572025,90066836,90554097,91029272,91513943, 91985665,92473877,92968758,93464336,93959346, 94454296,94949072,95441663,95926334,96400456, 96856737,97349116,97828773,98321727,98808943, 99298711,99783292,100263414,100741301,101214245, 101706624,102203725,102702810,103202591,103702559, 104202403,104701455,105198645,105693671,106188553, 106668210,107167294,107654510,108153409,108643572, 109140448,109631937,110124935,110615087,111104171, 111597126,112096907,112595805,113093028,113592811, 114091416,114589182,115087419,115585177,116080739, 116567955,117067924,117558087,118057869,118549358, 119048443,119540444,120037758,120529914,121025142, 121514910,122014754,122511631,123010236,123509320, 124005152,124504321,124999108,125496724,125991519, 126476100,126975152,127466641,127964408,128456409, 128955577,129444362,129941989,130432182,130927550, 131407672,131904862,132397860,132896097,133393412, 133888199,134385825,134870791,135365762,135853349, 136331236,136826262,137316414,137814172,138306328, 138803945,139294138,139789108,140268614,140761870, 141234814,141729695,142218779,142714341,143209569, 143704364,144199733,144687320,145180576,145654893, 146111021,146604549,147097504,147572451,148062753, 148551573,149030789,149517153,149997971,150469565, 150963093,151462178,151961959,152459540,152958803, 153458399,153956289,154455081,154952536,155448114, 155941069,156440850,156939748,157436971,157936754, 158435359,158933125,159431362,159929120,160424683, 160899630,161397210,161894433,162373649,162870480, 163366197,163847036,164342308,164834857,165316243, 165806546,166305809,166805591,167302422,167797534, 168296440,168794207,169291182,169787228,170282584, 170771404,171271001,171769606,172265322,172764228, 173259686,173756940,174255103,174749456,175244788, 175724004,176221894,176719661,177200500,177698266, 178195520,178676906,179174054,179669963,180151504, 180637868,181136660,181634897,182130170,182627145, 183125307,183622455,184112943,184610047,185104839, 185585657,186083112,186580870,187073419,187569466, 188063819,188559727,189056831,189540681,190034892, 190506486,191002064,191497626,191979012,192474368, 192969701,193451242,193946034,194440245,194913069, 195364913,195856245,196343461,196833764,197301749, 197787047,198272823,198757875,199231332,199703660, 200194992,200693867,201193836,201693099,202187654, 202685143,203184617,203683417,204179171,204674181, 205161397,205661366,206151529,206651311,207142800, 207641885,208133886,208631200,209123356,209618584, 210108887,210608150,211107932,211604763,212099875, 212598781,213096548,213593523,214089569,214584926, 215052911,215547465,216038954,216534066,217007523, 217499719,217990902,218484411,218959906,219446728, 219932027,220429516,220928600,221427506,221919702, 222413232,222911994,223409873,223904584,224393575, 224879351,225378826,225870827,226368593,226859776, 227358538,227847478,228346120,228838090,229333644, 229818696,230317496,230814811,231311786,231805294, 232303173,232801815,233291626,233787284,234281778, 234755235,235250989,235743145,236239192,236714687, 237209397,237701367,238197025,238673285,239165609, 239637937,240132947,240628175,241123531,241610354, 242099345,242594899,243089393,243581717,244056063, 244506979,244997505,245487273,245976093,246461392, 246935265,247422491,247905097,248384207,248856049, 249346575,249844863,250344707,250844304,251341793, 251837738,252335687,252833863,253330941,253825891, 254315659,254815503,255312380,255810985,256310069, 256805901,257305070,257799857,258297473,258792268, 259281088,259780685,260279290,260775006,261273912, 261769370,262266624,262764787,263259140,263754472, 264239771,264737260,265236344,265735250,266227446, 266720976,267219738,267717617,268212328,268701320, 269175193,269671137,270166969,270662427,271155957, 271637395,272132981,272626657,273118402,273606214, 274093441,274591390,275090558,275587812,276086574, 276582160,277074754,277572088,278069042,278564273, 279046879,279545056,280039843,280538005,281035884, 281529560,282026894,282513144,283009665,283502663, 283981773,284478851,284976468,285470821,285965531, 286457276,286954230,287450751,287934209,288427697, 288899539,289394489,289889284,290384617,290873608, 291361420,291856651,292349649,292843137,293317367, 293760571,294246951,294731532,295210748,295696524, 296183751,296643954,297123516,297597602,298067212, 298553592,299049704,299548756,300046646,300546121, 301044070,301536491,302030220,302525030,303019806, 303504387,304003439,304494928,304992695,305484696, 305983864,306472649,306970276,307460469,307955837, 308435053,308932943,309430710,309911549,310409315, 310906569,311387955,311885103,312381012,312862553, 313348329,313847804,314339805,314837571,315328754, 315827516,316316456,316815098,317307068,317802622, 318289849,318787798,319286966,319784220,320282982, 320778568,321271162,321768496,322265450,322760682, 323220885,323713305,324202090,324683476,325172416, 325665010,326128509,326618473,327104746,327585454, 328065017,328558746,329056372,329553520,330052162, 330549496,331039460,331524706,332017240,332510935, 332985021,333479832,333970025,334465933,334957903, 335454857,335941130,336433664,336912904,337405294, 337874904,338369680,338865049,339346590,339842144, 340337375,340818083,341311778,341804168,342276695, 342712215,343191701,343671823,344158187,344643239, 345125845,345605408,346054429,346524159,346990791, 347470277,347962055,348459245,348958037,349456837, 349955014,350448743,350933392,351420653,351913243, 352393365,352890555,353383553,353881790,354379105, 354873892,355371518,355856484,356351455,356839042, 357325406,357824198,358322435,358817708,359314683, 359812845,360309993,360800481,361297585,361792377, 362277429,362776229,363273544,363770519,364264027, 364761906,365260548,365750359,366246017,366740511, 367223117,367721294,368216081,368714243,369212122, 369705798,370203132,370689382,371185903,371678901, 372158464,372652193,373149819,373646967,374145609, 374642943,375132907,375618153,376110687,376604383, 377053404,377538052,378023018,378513506,379003317, 379489567,379974813,380427197,380908306,381388632, 381858363,382345624,382840594,383337698,383833356, 384329877,384822411,385303520,385778158,386266144, 386732776,387225367,387712954,388207746,388702240, 389195238,389688933,390169259,390657245,391130375, 391555307,392027447,392505334,392986152,393459609, 393938719,394412805,394882536,395315957,395779265, 396251405,396739375,397234401,397731856,398227610, 398724688,399219499,399706760,400181935,400666606, 401144493,401639519,402129671,402627429,403119585, 403617202,404107395,404602365,405081871,405575127, 406055945,406553400,407051158,407543707,408039754, 408534107,409030015,409527119,410010969,410505180, 410978637,411474391,411966547,412462594,412938089, 413432799,413924769,414420427,414896687,415389011, 415868121,416365199,416862816,417357169,417851879, 418343624,418840578,419337099,419820557,420314045, 420788131,421282942,421773135,422269043,422761013, 423257967,423744240,424236774,424716014,425208404, 425678135,426165396,426660366,427157470,427653128, 428149649,428642183,429123292,429597930,430085917, 430519338,430994512,431474018,431957868,432434128, 432917586,433396826,433871464,434306087,434779291, 435242600,435727271,436220527,436714738,437207062, 437700550,438192940,438680926,439154130,439626260, 440041768,440513490,440986434,441458028,441930356, 442402198,442871808,443338440,443801749,444223540, 444695262,445183474,445678355,446173933,446668943, 447163893,447658669,448151260,448635931,449110053, 449582997,450077878,450566962,451062524,451557752, 452052547,452547916,453035503,453528759,454003076, 454474670,454970248,455465810,455947196,456442552, 456937885,457419426,457914218,458408429,458881253, 459353581,459848591,460343819,460839175,461325998, 461814989,462310543,462805037,463297361,463771707, 464243549,464738499,465233294,465728627,466217618, 466705430,467200661,467693659,468187147,468661377, 469130987,469625763,470121132,470602673,471098227, 471593458,472074166,472567861,473060251,473532778, 473999410,474492001,474979588,475474380,475968874, 476461872,476955567,477435893,477923879,478397009, 478860318,479344989,479838245,480332456,480824780, 481318268,481810658,482298644,482771848,483243979, 483665770,484139892,484614209,485087033,485561379, 486035609,486508136,486981266,487453396,487875964}; const int T=1000000; bool check(int x) {int i=x,tot=0;long long f=1;while(i) tot+=i%10,i/=10;if(tot&1) return 0;tot>>=1;i=x;while(i) f|=(f<<i%10),i/=10;return (f>>tot)&1; } int solve(int x) {int ans=b[x/T];for(int i=x/T*T+1;i<=x;i++)ans+=check(i);return ans; } int main() {int A,B;scanf("%d%d",&A,&B);printf("%d",solve(B)-solve(A-1)); }

---

打表$code$

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<windows.h> using namespace std; int sum; bool check(int x) {int i=x,tot=0;long long f=1;while(i) tot+=i%10,i/=10;if(tot&1) return 0;tot>>=1;i=x;while(i) f|=(f<<i%10),i/=10;return (f>>tot)&1; } int main() {freopen("biao.out","w",stdout);printf("{");for(int i=0;i<=1000000000;i++){sum+=check(i);if(i%1000000==0){printf("%d,",sum);cerr<<(double)i/1000000000*100*1.0<<'%'<<endl;}if(i%5000000==0) printf("\n");}printf("}"); }

總結(jié)

以上是生活随笔為你收集整理的jzoj3362,bzoj3758-[NOI2013模拟]数数【分段打表,背包,状压】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。