打表法：
优化： O3 #pragma GCC optimize(3,"Ofast","inline")
O2 #pragma GCC optimize(2)
将一些数据暴力枚举要很久的，就提前打表出来后直接调用就行了。
分段打表 可以减少 空间， 直接暴力剩下的东西嘿嘿;
分段打表例题：
神犇最近闲来无事，于是就思考哲学，研究数字之美。在神犇看来，如果一个数的各位能够被分成两个集合，而且这两个集合里的数的和相等，那么这个数就是优美的（具体原因就只有神犇才知道了）。现在神犇在思考另一个问题，在区间[a,b]中有多少个数是优美的？这个问题对于神犇来说很简单，相信对于你来说也不难。 Input 输入只有一行，包含两个整数a和b。 Output 输出只有一行，包含一个整数，代表区间[a,b]中优美的数的个数。 Sample Input 1 11 Sample Output 1 Hint 1<=A<=B<=10^9View Code
打表代码：
#include <bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int M = 100005;
const int N = 10000;
#define ri register int
long long ans;
bool getans(int x)
{
int sum=0;
long long f=1;
for(ri i=x;i;i/=10)
{
f|=(f<<i%10);
sum+=i%10;
}
if(sum&1) return 0;
return f&1ll<<(sum/2);
}
int p=500000;
int main(){
freopen("233.txt","w",stdout); // txt 记住了
for(ri i=1;i<=1000000000;i++)
{
ans+=getans(i);
if(i%p==0)
printf("%d,",ans);
}
}
View Code
提交代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int M = 100005;
const int N = 100005;
const int P = 500000;
#define ri register int
long long f[]={0,191240,376413,606393,832547,1061551,1288828,1517324,1744956,1970036,2196800,2423909,2647716,2870872,3090920,3310802,3526440,3740289,3951372,4160377,4366880,4596860,4823015,5064902,5304766,5551357,5797144,6043920,6290672,6536086,6782004,7027632,7272530,7516599,7758910,7999993,8238396,8475668,8710536,8946961,9182258,9411262,9638539,9885130,10130918,10370370,10610575,10857207,11103529,11346494,11590745,11836003,12080513,12322393,12565094,12806029,13045216,13284181,13523103,13759909,13996047,14224543,14452175,14698951,14945703,15192335,15438658,15676246,15913605,16158300,16403907,16648567,16892727,17132423,17371943,17614884,17858307,18098734,18339125,18575075,18810719,19035799,19262563,19507977,19753895,19996860,20241111,20485806,20731414,20963975,21199399,21442069,21684697,21926884,22170473,22412414,22655525,22890558,23128982,23365117,23601310,23828419,24052226,24297854,24542752,24788010,25032520,25277180,25521340,25764010,26006639,26244302,26480512,26724666,26967738,27209797,27450344,27690193,27929454,28165732,28401296,28624452,28844500,29088569,29330880,29572760,29815461,30055157,30294677,30536864,30780453,31024607,31267680,31498059,31727883,31968836,32207445,32444905,32681531,32916754,33151141,33371023,33586661,33827744,34066147,34307082,34546269,34789210,35032633,35274574,35517685,35759744,36000291,36241244,36479854,36705884,36928875,37165243,37398605,37632957,37865237,38079086,38290169,38527441,38762309,39001274,39240196,39480623,39721014,39956047,40194471,40434320,40673581,40911041,41147667,41384035,41617398,41834651,42050819,42283577,42514127,42723132,42929635,43166060,43401357,43638163,43874301,44110251,44345895,44582030,44818223,45054501,45290065,45525288,45759675,45994027,46226307,46459065,46689616,46900780,47111407,47341387,47567542,47809429,48049293,48295884,48541671,48788447,49035199,49280613,49526531,49772159,50017057,50261126,50503437,50744520,50982923,51220195,51455063,51691488,51926786,52168673,52408537,52655128,52900916,53149584,53398017,53647584,53897101,54146492,54395976,54645189,54894264,55142591,55390376,55636899,55882154,56126834,56370124,56614469,56858336,57104927,57350715,57599383,57847816,58097383,58346901,58596793,58846682,59096667,59346650,59596574,59846494,60096069,60345546,60594329,60842736,61090545,61337762,61585284,61832643,62079419,62326171,62575738,62825256,63075148,63325037,63573818,63822618,64072178,64321881,64571683,64821477,65070423,65319367,65568716,65818159,66066915,66315614,66563425,66811192,67056606,67302524,67551915,67801399,68051384,68301368,68550928,68800631,69047555,69295186,69543914,69792675,70042426,70292149,70541429,70790949,71038425,71286703,71534188,71781713,72027341,72272239,72521452,72770527,73020451,73270371,73520173,73769968,74018696,74267457,74515521,74763402,75012475,75261351,75510555,75759527,76008115,76256605,76504125,76751555,76995624,77237935,77486262,77734047,77983622,78233099,78482045,78730989,78980740,79230464,79479537,79728413,79974939,80220834,80468185,80714563,80962346,81209373,81456880,81704149,81945232,82183635,82430158,82675413,82924196,83172603,83421952,83671395,83920675,84170195,84419399,84668372,84915723,85162101,85405377,85646750,85891274,86134011,86380684,86626601,86863873,87098741,87343421,87586711,87834520,88081737,88330493,88579192,88826668,89074946,89323534,89572024,89819807,90066835,90311359,90554096,90792612,91029271,91272212,91513942,91750367,91985664,92230009,92473876,92721398,92968757,93216568,93464335,93711820,93959345,94206865,94454295,94701802,94949071,95195744,95441662,95684603,95926333,96163508,96400455,96629459,96856736,97103327,97349115,97588567,97828772,98075404,98321726,98564691,98808942,99054200,99298710,99540590,99783291,100024226,100263413,100502378,100741300,100978106,101214244,101460835,101706623,101955291,102203724,102453291,102702809,102952701,103202590,103452575,103702558,103952482,104202402,104451977,104701454,104950237,105198644,105446453,105693670,105941192,106188552,106428004,106668209,106917776,107167293,107410258,107654509,107903984,108153408,108397759,108643571,108892112,109140447,109385424,109631936,109878641,110124934,110369321,110615086,110859687,111104170,111350802,111597125,111847017,112096906,112346381,112595804,112844429,113093027,113342921,113592810,113842151,114091415,114340302,114589181,114838373,115087418,115336315,115585176,115832981,116080738,116323703,116567954,116817939,117067923,117312274,117558086,117807980,118057868,118302845,118549357,118798923,119048442,119293664,119540443,119789180,120037757,120283054,120529913,120777539,121025141,121270399,121514909,121764833,122014753,122263294,122511630,122760971,123010235,123259801,123509319,123757373,124005151,124254751,124504320,124751903,124999107,125247948,125496723,125744193,125991518,126233398,126476099,126725674,126975151,127220128,127466640,127715527,127964407,128209629,128456408,128706008,128955576,129199269,129444361,129693300,129941988,130186397,130432181,130679890,130927549,131168484,131407671,131656454,131904861,132151566,132397859,132647051,132896096,133144833,133393411,133640994,133888198,134137137,134385824,134628921,134870790,135118633,135365761,135609808,135853348,136092313,136331235,136579044,136826261,137070648,137316413,137565310,137814171,138059468,138306327,138555168,138803944,139048353,139294137,139541980,139789107,140028735,140268613,140515517,140761869,140998675,141234813,141482335,141729694,141974295,142218778,142466583,142714340,142961966,143209568,143457038,143704363,143952072,144199732,144443779,144687319,144934223,145180575,145417785,145654892,145883388,146111020,146357796,146604548,146851180,147097503,147335091,147572450,147817145,148062752,148307412,148551572,148791268,149030788,149273729,149517152,149757579,149997970,150233920,150469564,150716340,150963092,151212659,151462177,151712069,151961958,152210739,152459539,152709099,152958802,153208604,153458398,153707344,153956288,154205637,154455080,154703836,154952535,155200346,155448113,155694745,155941068,156190960,156440849,156690324,156939747,157188372,157436970,157686864,157936753,158186094,158435358,158684245,158933124,159182316,159431361,159680258,159929119,160176924,160424682,160662270,160899629,161148410,161397209,161645834,161894432,162134128,162373648,162621951,162870479,163118393,163366196,163606652,163847035,164094462,164342307,164588608,164834856,165075563,165316242,165560937,165806545,166056105,166305808,166555702,166805590,167053893,167302421,167549547,167797533,168046939,168296439,168545310,168794206,169042415,169291181,169538766,169787227,170034870,170282583,170527243,170771403,171021205,171271000,171520341,171769605,172017519,172265321,172514727,172764227,173012066,173259685,173508325,173756939,174006100,174255102,174502285,174749455,174997153,175244787,175484483,175724003,175972949,176221893,176470780,176719660,176960116,177200499,177449370,177698265,177946905,178195519,178436226,178676905,178925419,179174053,179422043,179669962,179910734,180151503,180394444,180637867,180887216,181136659,181385851,181634896,181882323,182130169,182378378,182627144,182876305,183125306,183373820,183622454,183867282,184112942,184361466,184610046,184857544,185104838,185345265,185585656,185834412,186083111,186332008,186580869,186827170,187073418,187321003,187569465,187816648,188063818,188311808,188559726,188808250,189056830,189298637,189540680,189787837,190034891,190270841,190506485,190754296,191002063,191249868,191497625,191738332,191979011,192226654,192474367,192722065,192969700,193210472,193451241,193698739,193946033,194193190,194440244,194676680,194913068,195138148,195364912,195610326,195856244,196099209,196343460,196588155,196833763,197066324,197301748,197544418,197787046,198029233,198272822,198514763,198757874,198992907,199231331,199467466,199703659,199949073,200194991,200444382,200693866,200943851,201193835,201443395,201693098,201940022,202187653,202436381,202685142,202934893,203184616,203433896,203683416,203930892,204179170,204426655,204674180,204917145,205161396,205411381,205661365,205905716,206151528,206401422,206651310,206896287,207142799,207392365,207641884,207887106,208133885,208382622,208631199,208876496,209123355,209370981,209618583,209863278,210108886,210358446,210608149,210858043,211107931,211356234,211604762,211851888,212099874,212349280,212598780,212847651,213096547,213344756,213593522,213841107,214089568,214337211,214584925,214817486,215052910,215299834,215547464,215792441,216038953,216286079,216534065,216769098,217007522,217253376,217499718,217744528,217990901,218237094,218484410,218720287,218959905,219203148,219446727,219689397,219932026,220180754,220429515,220679081,220928599,221178005,221427505,221673359,221919701,222166555,222413231,222662644,222911993,223160948,223409872,223656877,223904583,224149106,224393574,224635761,224879350,225129101,225378825,225624047,225870826,226119697,226368592,226613402,226859775,227109188,227358537,227602272,227847477,228096725,228346119,228591326,228838089,229085848,229333643,229575584,229818695,230067975,230317495,230566232,230814810,231063019,231311785,231557978,231805293,232054248,232303172,232552420,232801814,233046288,233291625,233538986,233787283,234034537,234281777,234516810,234755234,235002710,235250988,235496285,235743144,235990729,236239191,236475068,236714686,236961691,237209396,237454603,237701366,237948727,238197024,238433198,238673284,238919180,239165608,239401743,239637936,239885421,240132946,240380572,240628174,240875817,241123530,241366773,241610353,241854876,242099344,242347103,242594898,242842152,243089392,243335288,243581716,243818897,244056062,244283171,244506978,244752606,244997504,245242762,245487272,245731932,245976092,246218762,246461391,246699054,246935264,247179418,247422490,247664549,247905096,248144945,248384206,248620484,248856048,249101676,249346574,249595787,249844862,250094786,250344706,250594508,250844303,251093031,251341792,251589856,251837737,252086810,252335686,252584890,252833862,253082450,253330940,253578460,253825890,254071148,254315658,254565582,254815502,255064043,255312379,255561720,255810984,256060550,256310068,256558122,256805900,257055500,257305069,257552652,257799856,258048697,258297472,258544942,258792267,259036927,259281087,259530889,259780684,260030025,260279289,260527203,260775005,261024411,261273911,261521750,261769369,262018009,262266623,262515784,262764786,263011969,263259139,263506837,263754471,263997141,264239770,264488498,264737259,264986825,265236343,265485749,265735249,265981103,266227445,266474299,266720975,266970388,267219737,267468692,267717616,267964621,268212327,268456850,268701319,268938982,269175192,269423256,269671136,269919190,270166968,270414807,270662426,270909280,271155956,271397028,271637394,271885328,272132980,272380058,272626656,272872649,273118401,273362488,273606213,273850367,274093440,274342513,274591389,274840989,275090557,275339197,275587811,275837224,276086573,276334507,276582159,276828704,277074753,277323585,277572087,277820623,278069041,278316675,278564272,278806331,279046878,279296082,279545055,279792638,280039842,280289003,280538004,280786959,281035883,281282961,281529559,281778391,282026893,282270543,282513143,282761528,283009664,283256369,283502662,283742511,283981772,284230360,284478850,284727691,284976467,285223650,285470820,285717825,285965530,286211523,286457275,286705811,286954229,287202614,287450750,287692419,287934208,288181028,288427696,288663974,288899538,289147058,289394488,289641958,289889283,290136981,290384616,290629139,290873607,291117694,291361419,291609053,291856650,292103355,292349648,292596468,292843136,293080313,293317366,293540522,293760570,294004639,294246950,294488830,294731531,294971227,295210747,295452934,295696523,295940677,296183750,296414129,296643953,296884906,297123515,297360975,297597601,297832824,298067211,298311280,298553591,298801918,299049703,299299278,299548755,299797701,300046645,300296396,300546120,300795193,301044069,301290595,301536490,301783841,302030219,302278002,302525029,302772536,303019805,303261685,303504386,303753961,304003438,304248415,304494927,304743814,304992694,305237916,305484695,305734295,305983863,306227556,306472648,306721587,306970275,307214684,307460468,307708177,307955836,308195532,308435052,308683998,308932942,309181829,309430709,309671165,309911548,310160419,310409314,310657954,310906568,311147275,311387954,311636468,311885102,312133092,312381011,312621783,312862552,313104739,313348328,313598079,313847803,314093025,314339804,314588675,314837570,315082380,315328753,315578166,315827515,316071250,316316455,316565703,316815097,317060304,317307067,317554826,317802621,318046775,318289848,318538921,318787797,319037397,319286965,319535605,319784219,320033632,320282981,320530915,320778567,321025112,321271161,321519993,321768495,322017031,322265449,322513083,322760681,322991060,323220884,323467410,323713304,323956997,324202089,324442796,324683475,324927210,325172415,325418960,325665009,325896607,326128508,326374028,326618472,326861122,327104745,327345128,327585453,327826406,328065016,328312367,328558745,328807684,329056371,329304885,329553519,329802767,330052161,330300993,330549495,330795015,331039459,331282929,331524705,331771568,332017239,332264259,332510934,332748394,332985020,333232803,333479831,333724240,333970024,334218014,334465932,334711139,334957902,335206438,335454856,335697506,335941129,336187992,336433663,336673234,336912903,337159404,337405293,337640516,337874903,338122410,338369679,338617388,338865048,339105820,339346589,339594348,339842143,340089777,340337374,340577757,340818082,341065102,341311777,341558278,341804167,342040510,342276694,342496576,342712214,342953297,343191700,343432635,343671822,343914763,344158186,344400127,344643238,344885297,345125844,345366797,345605407,345831437,346054428,346290796,346524158,346758510,346990790,347231873,347470276,347716799,347962054,348210837,348459244,348708593,348958036,349207316,349456836,349706040,349955013,350202364,350448742,350692018,350933391,351177915,351420652,351667325,351913242,352154177,352393364,352642147,352890554,353137259,353383552,353632744,353881789,354130526,354379104,354626687,354873891,355122830,355371517,355614614,355856483,356104326,356351454,356595501,356839041,357081982,357325405,357574754,357824197,358073389,358322434,358569861,358817707,359065916,359314682,359563843,359812844,360061358,360309992,360554820,360800480,361049004,361297584,361545082,361792376,362034317,362277428,362526708,362776228,363024965,363273543,363521752,363770518,364016711,364264026,364512981,364761905,365011153,365260547,365505021,365750358,365997719,366246016,366493270,366740510,366982569,367223116,367472320,367721293,367968876,368216080,368465241,368714242,368963197,369212121,369459199,369705797,369954629,370203131,370446781,370689381,370937766,371185902,371432607,371678900,371919853,372158463,372405814,372652192,372901131,373149818,373398332,373646966,373896214,374145608,374394440,374642942,374888462,375132906,375376376,375618152,375865015,376110686,376357706,376604382,376830412,377053403,377296679,377538051,377781148,378023017,378267845,378513505,378757979,379003316,379246966,379489566,379733036,379974812,380202153,380427196,380668970,380908305,381149301,381388631,381624999,381858362,382102886,382345623,382593466,382840593,383089117,383337697,383585058,383833355,384081740,384329876,384576739,384822410,385064184,385303519,385541917,385778157,386022842,386266143,386500495,386732775,386979448,387225366,387469413,387712953,387960451,388207745,388454999,388702239,388948944,389195237,389442257,389688932,389929928,390169258,390413943,390657244,390894111,391130374,391344223,391555306,391792578,392027446,392266411,392505333,392745760,392986151,393221184,393459608,393699457,393938718,394176178,394412804,394649172,394882535,395099788,395315956,395548714,395779264,396016536,396251404,396496084,396739374,396987183,397234400,397483156,397731855,397979331,398227609,398476197,398724687,398972470,399219498,399464022,399706759,399945275,400181934,400424875,400666605,400905570,401144492,401392301,401639518,401883905,402129670,402378567,402627428,402872725,403119584,403368425,403617201,403861610,404107394,404355237,404602364,404841992,405081870,405328774,405575126,405815553,406055944,406304700,406553399,406802296,407051157,407297458,407543706,407791291,408039753,408286936,408534106,408782096,409030014,409278538,409527118,409768925,410010968,410258125,410505179,410740212,410978636,411226112,411474390,411719687,411966546,412214131,412462593,412698470,412938088,413185093,413432798,413678005,413924768,414172129,414420426,414656600,414896686,415142582,415389010,415628859,415868120,416116708,416365198,416614039,416862815,417109998,417357168,417604173,417851878,418097871,418343623,418592159,418840577,419088962,419337098,419578767,419820556,420067376,420314044,420551504,420788130,421035913,421282941,421527350,421773134,422021124,422269042,422514249,422761012,423009548,423257966,423500616,423744239,423991102,424236773,424476344,424716013,424962514,425208403,425444771,425678134,425922658,426165395,426413238,426660365,426908889,427157469,427404830,427653127,427901512,428149648,428396511,428642182,428883956,429123291,429361689,429597929,429842614,430085916,430303169,430519337,430757853,430994511,431234139,431474017,431715824,431957867,432194041,432434127,432675796,432917585,433157156,433396825,433635223,433871463,434089085,434306086,434543660,434779290,435012048,435242599,435485540,435727270,435974174,436220526,436467683,436714737,436960633,437207061,437453881,437700549,437947050,438192939,438437624,438680925,438918499,439154129,439390665,439626259,439835264,440041767,440278192,440513489,440750295,440986433,441222383,441458027,441694162,441930355,442166633,442402197,442637420,442871807,443106159,443338439,443571197,443801748,444012912,444223539,444459964,444695261,444939606,445183473,445430995,445678354,445926165,446173932,446421417,446668942,446916462,447163892,447411399,447658668,447905341,448151259,448394200,448635930,448873105,449110052,449346858,449582996,449830518,450077877,450322478,450566961,450814766,451062523,451310149,451557751,451805221,452052546,452300255,452547915,452791962,453035502,453282406,453528758,453765968,454003075,454239025,454474669,454722480,454970247,455218052,455465809,455706516,455947195,456194838,456442551,456690249,456937884,457178656,457419425,457666923,457914217,458161374,458408428,458644864,458881252,459117387,459353580,459601065,459848590,460096216,460343818,460591461,460839174,461082417,461325997,461570520,461814988,462062747,462310542,462557796,462805036,463050932,463297360,463534541,463771706,464007984,464243548,464491068,464738498,464985968,465233293,465480991,465728626,465973149,466217617,466461704,466705429,466953063,467200660,467447365,467693658,467940478,468187146,468424323,468661376,468896599,469130986,469378493,469625762,469873471,470121131,470361903,470602672,470850431,471098226,471345860,471593457,471833840,472074165,472321185,472567860,472814361,473060250,473296593,473532777,473767129,473999409,474246082,474492000,474736047,474979587,475227085,475474379,475721633,475968873,476215578,476461871,476708891,476955566,477196562,477435892,477680577,477923878,478160745,478397008,478629766,478860317,479103258,479344988,479591892,479838244,480085401,480332455,480578351,480824779,481071599,481318267,481564768,481810657,482055342,482298643,482536217,482771847,483008383,483243978,483455142,483665769,483902944,484139891,484377101,484614208,484850644,485087032,485324213,485561378,485798555,486035608,486271951,486508135,486745002,486981265,487217801,487453395,487664707,487875963};
bool check(int x)
{
int sum=0;
long long f=1;
for(ri i=x;i;i/=10)
sum+=i%10,f|=(f<<(i%10));
if(sum&1) return 0;
return f&1ll<<(sum/2);
}
long long getans(int x)
{
long long ans=f[x/P];
for(ri i=x/P*P+1;i<=x;i++)
{
ans+=check(i);
}
return ans;
}
int main(){
long long a,b;
scanf("%lld%lld",&a,&b);
printf("%lld",getans(b)-getans(a-1));
}
View Code
1