头像

Shadow


访客:10529

离线:4个月前


活动打卡代码 AcWing 1084. 数字游戏 II

Shadow
6个月前

(๑╹ヮ╹๑)ノ Studying makes me happy

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int f[N][10][110],l,r,p;

int mod(int x,int y) {
    return (x%y+y)%y;
}

void init() {
    memset(f,0,sizeof(f));
    for(register int i=0; i<=9; i++) f[1][i][i%p] = 1;

    for(register int i=2; i<N; i++)
        for(register int j=0; j<=9; j++)
            for(register int k=0; k<p; k++)
                for(register int x=0; x<=9; x++)
                    f[i][j][k] += f[i-1][x][mod(k-j,p)];
}
int dp(int n) {
    if (!n) return 1;
    int a[N],cnt=0,ans=0,last=0;//last记录前面各位数字之和 
    while(n) a[cnt++] = n%10, n/=10;
    for(register int i=cnt-1; i>=0; i--) {
        int x = a[i];
        for(register int j=0; j<x; j++)//左边的分支 
            ans += f[i+1][j][mod(-last,p)];
        last += x;
        if(!i && last%p==0) ans++;//顺利地到了最后 
    }
    return ans;
}
int main() {
    while(scanf("%d%d%d",&l,&r,&p)!=EOF) {
        init();
        printf("%d\n",dp(r)-dp(l-1));
    } 
    return 0;
}


活动打卡代码 AcWing 1082. 数字游戏

Shadow
6个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 35;
int f[N][N],l,r;
void init() {
    for(register int i=0; i<=9; i++) f[1][i] = 1;

    for(register int i=2; i<N; i++)
        for(register int j=0; j<=9; j++)
            for(register int k=j; k<=9; k++)
                f[i][j] += f[i-1][k];
}
int dp(int n) {
    if (!n) return 1;
    int a[N],cnt=0,ans=0,last=0;//last记录上一位是几
    while(n) a[cnt++] = n%10, n/=10;
    for(register int i=cnt-1; i>=0; i--) {
        int x = a[i];
        for(register int j=last; j<x; j++)//因为需要保证这一位比上一位大
            ans += f[i+1][j];
        if(x<last) break;
        last = x;
        if(!i) ans++;//顺利地到了最后 
    }
    return ans;
}
int main() {
    init();
    while(scanf("%d%d",&l,&r)!=EOF)
        printf("%d\n",dp(r)-dp(l-1));
    return 0;
}
/*
集合:所有最高位是j,且有i位的方案数
属性:计数
*/


活动打卡代码 AcWing 1083. Windy数

Shadow
6个月前
#include<bits/stdc++.h>
using namespace std;
int a,b;
int d[2005]= {202174,338305,476808,615022,753274,891526,1029740,1168243,1304374,1459689,1459689,1459689,1459689,1597903,1736155,1874407,2012621,2151124,2287255,2442570,
              2597885,2597885,2597885,2597885,2736137,2874389,3012603,3151106,3287237,3442552,3597867,3733998,3733998,3733998,3733998,3872250,4010464,4148967,4285098,4440413,
              4595728,4731859,4870362,4870362,4870362,4870362,5008576,5147079,5283210,5438525,5593840,5729971,5868474,6006688,6006688,6006688,6006688,6145191,6281322,6436637,
              6591952,6728083,6866586,7004800,7143052,7143052,7143052,7143052,7279183,7434498,7589813,7725944,7864447,8002661,8140913,8279165,8279165,8279165,8279165,8434480,
              8589795,8725926,8864429,9002643,9140895,9279147,9417361,9417361,9417361,9417361,9572676,9708807,9847310,9985524,10123776,10262028,10400242,10538745,10538745,10538745,
              10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,
              10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10538745,10694060,10830191,10830191,10830191,10830191,10968443,11106657,11245160,11381291,11536606,
              11691921,11828052,11966555,11966555,11966555,11966555,12104769,12243272,12379403,12534718,12690033,12826164,12964667,13102881,13102881,13102881,13102881,13241384,13377515,13532830,
              13688145,13824276,13962779,14100993,14239245,14239245,14239245,14239245,14375376,14530691,14686006,14822137,14960640,15098854,15237106,15375358,15375358,15375358,15375358,15530673,
              15685988,15822119,15960622,16098836,16237088,16375340,16513554,16513554,16513554,16513554,16668869,16805000,16943503,17081717,17219969,17358221,17496435,17634938,17634938,17634938,
              17634938,17634938,17773441,17911655,18049907,18188159,18326373,18464876,18601007,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,
              18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,18756322,
              18911637,19047768,19186271,19186271,19186271,19186271,19324485,19462988,19599119,19754434,19909749,20045880,20184383,20322597,20322597,20322597,20322597,20461100,20597231,20752546,
              20907861,21043992,21182495,21320709,21458961,21458961,21458961,21458961,21595092,21750407,21905722,22041853,22180356,22318570,22456822,22595074,22595074,22595074,22595074,22750389,
              22905704,23041835,23180338,23318552,23456804,23595056,23733270,23733270,23733270,23733270,23888585,24024716,24163219,24301433,24439685,24577937,24716151,24854654,24854654,24854654,
              24854654,24854654,24993157,25131371,25269623,25407875,25546089,25684592,25820723,25976038,25976038,25976038,25976038,26114252,26252504,26390756,26528970,26667473,26803604,26958919,
              26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,
              26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,26958919,27114234,27250365,27388868,27527082,27527082,27527082,27527082,27665585,27801716,27957031,
              28112346,28248477,28386980,28525194,28663446,28663446,28663446,28663446,28799577,28954892,29110207,29246338,29384841,29523055,29661307,29799559,29799559,29799559,29799559,29954874,
              30110189,30246320,30384823,30523037,30661289,30799541,30937755,30937755,30937755,30937755,31093070,31229201,31367704,31505918,31644170,31782422,31920636,32059139,32059139,32059139,
              32059139,32059139,32197642,32335856,32474108,32612360,32750574,32889077,33025208,33180523,33180523,33180523,33180523,33318737,33456989,33595241,33733455,33871958,34008089,34163404,
              34318719,34318719,34318719,34318719,34456971,34595223,34733437,34871940,35008071,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,
              35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,35163386,
              35318701,35454832,35593335,35731549,35869801,35869801,35869801,35869801,36005932,36161247,36316562,36452693,36591196,36729410,36867662,37005914,37005914,37005914,37005914,37161229,
              37316544,37452675,37591178,37729392,37867644,38005896,38144110,38144110,38144110,38144110,38299425,38435556,38574059,38712273,38850525,38988777,39126991,39265494,39265494,39265494,
              39265494,39265494,39403997,39542211,39680463,39818715,39956929,40095432,40231563,40386878,40386878,40386878,40386878,40525092,40663344,40801596,40939810,41078313,41214444,41369759,
              41525074,41525074,41525074,41525074,41663326,41801578,41939792,42078295,42214426,42369741,42525056,42661187,42661187,42661187,42661187,42799439,42937653,43076156,43212287,43367602,
              43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,
              43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43367602,43522917,43659048,43797551,43935765,44074017,44212269,44212269,44212269,44212269,44367584,
              44522899,44659030,44797533,44935747,45073999,45212251,45350465,45350465,45350465,45350465,45505780,45641911,45780414,45918628,46056880,46195132,46333346,46471849,46471849,46471849,
              46471849,46471849,46610352,46748566,46886818,47025070,47163284,47301787,47437918,47593233,47593233,47593233,47593233,47731447,47869699,48007951,48146165,48284668,48420799,48576114,
              48731429,48731429,48731429,48731429,48869681,49007933,49146147,49284650,49420781,49576096,49731411,49867542,49867542,49867542,49867542,50005794,50144008,50282511,50418642,50573957,
              50729272,50865403,51003906,51003906,51003906,51003906,51142120,51280623,51416754,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,
              51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,51572069,
              51727384,51863515,52002018,52140232,52278484,52416736,52554950,52554950,52554950,52554950,52710265,52846396,52984899,53123113,53261365,53399617,53537831,53676334,53676334,53676334,
              53676334,53676334,53814837,53953051,54091303,54229555,54367769,54506272,54642403,54797718,54797718,54797718,54797718,54935932,55074184,55212436,55350650,55489153,55625284,55780599,
              55935914,55935914,55935914,55935914,56074166,56212418,56350632,56489135,56625266,56780581,56935896,57072027,57072027,57072027,57072027,57210279,57348493,57486996,57623127,57778442,
              57933757,58069888,58208391,58208391,58208391,58208391,58346605,58485108,58621239,58776554,58931869,59068000,59206503,59344717,59344717,59344717,59344717,59483220,59619351,59774666,
              59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,
              59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59774666,59929981,60066112,60204615,60342829,60481081,60619333,60757547,60896050,60896050,60896050,
              60896050,60896050,61034553,61172767,61311019,61449271,61587485,61725988,61862119,62017434,62017434,62017434,62017434,62155648,62293900,62432152,62570366,62708869,62845000,63000315,
              63155630,63155630,63155630,63155630,63293882,63432134,63570348,63708851,63844982,64000297,64155612,64291743,64291743,64291743,64291743,64429995,64568209,64706712,64842843,64998158,
              65153473,65289604,65428107,65428107,65428107,65428107,65566321,65704824,65840955,65996270,66151585,66287716,66426219,66564433,66564433,66564433,66564433,66702936,66839067,66994382,
              67149697,67285828,67424331,67562545,67700797,67700797,67700797,67700797,67836928,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,
              67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,67992243,
              67992243,67992243,68130746,68268960,68407212,68545464,68683678,68822181,68958312,69113627,69113627,69113627,69113627,69251841,69390093,69528345,69666559,69805062,69941193,70096508,
              70251823,70251823,70251823,70251823,70390075,70528327,70666541,70805044,70941175,71096490,71251805,71387936,71387936,71387936,71387936,71526188,71664402,71802905,71939036,72094351,
              72249666,72385797,72524300,72524300,72524300,72524300,72662514,72801017,72937148,73092463,73247778,73383909,73522412,73660626,73660626,73660626,73660626,73799129,73935260,74090575,
              74245890,74382021,74520524,74658738,74796990,74796990,74796990,74796990,74933121,75088436,75243751,75379882,75518385,75656599,75794851,75933103,75933103,75933103,75933103,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,
              76088418,76088418,76226921,76365135,76503387,76641639,76779853,76918356,77054487,77209802,77209802,77209802,77209802,77348016,77486268,77624520,77762734,77901237,78037368,78192683,
              78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,
              78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78192683,78347998,78484129,78622632,78760846,78760846,78760846,78760846,78899349,79035480,79190795,
              79346110,79482241,79620744,79758958,79897210,79897210,79897210,79897210,80033341,80188656,80343971,80480102,80618605,80756819,80895071,81033323,81033323,81033323,81033323,81188638,
              81343953,81480084,81618587,81756801,81895053,82033305,82171519,82171519,82171519,82171519,82326834,82462965,82601468,82739682,82877934,83016186,83154400,83292903,83292903,83292903,
              83292903,83292903,83431406,83569620,83707872,83846124,83984338,84122841,84258972,84414287,84414287,84414287,84414287,84552501,84690753,84829005,84967219,85105722,85241853,85397168,
              85552483,85552483,85552483,85552483,85690735,85828987,85967201,86105704,86241835,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,
              86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,86397150,
              86552465,86688596,86827099,86965313,87103565,87103565,87103565,87103565,87239696,87395011,87550326,87686457,87824960,87963174,88101426,88239678,88239678,88239678,88239678,88394993,
              88550308,88686439,88824942,88963156,89101408,89239660,89377874,89377874,89377874,89377874,89533189,89669320,89807823,89946037,90084289,90222541,90360755,90499258,90499258,90499258,
              90499258,90499258,90637761,90775975,90914227,91052479,91190693,91329196,91465327,91620642,91620642,91620642,91620642,91758856,91897108,92035360,92173574,92312077,92448208,92603523,
              92758838,92758838,92758838,92758838,92897090,93035342,93173556,93312059,93448190,93603505,93758820,93894951,93894951,93894951,93894951,94033203,94171417,94309920,94446051,94601366,
              94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,
              94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94601366,94756681,94892812,95031315,95169529,95307781,95446033,95446033,95446033,95446033,95601348,
              95756663,95892794,96031297,96169511,96307763,96446015,96584229,96584229,96584229,96584229,96739544,96875675,97014178,97152392,97290644,97428896,97567110,97705613,97705613,97705613,
              97705613,97705613,97844116,97982330,98120582,98258834,98397048,98535551,98671682,98826997,98826997,98826997,98826997,98965211,99103463,99241715,99379929,99518432,99654563,99809878,
              99965193,99965193,99965193,99965193,100103445,100241697,100379911,100518414,100654545,100809860,100965175,101101306,101101306,101101306,101101306,101239558,101377772,101516275,101652406,101807721,
              101963036,102099167,102237670,102237670,102237670,102237670,102375884,102514387,102650518,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,
              102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,102805833,
              102961148,103097279,103235782,103373996,103512248,103650500,103788714,103788714,103788714,103788714,103944029,104080160,104218663,104356877,104495129,104633381,104771595,104910098,104910098,104910098,
              104910098,104910098,105048601,105186815,105325067,105463319,105601533,105740036,105876167,106031482,106031482,106031482,106031482,106169696,106307948,106446200,106584414,106722917,106859048,107014363,
              107169678,107169678,107169678,107169678,107307930,107446182,107584396,107722899,107859030,108014345,108169660,108305791,108305791,108305791,108305791,108444043,108582257,108720760,108856891,109012206,
              109167521,109303652,109442155,109442155,109442155,109442155,109580369,109718872,109855003,110010318,110165633,110301764,110440267,110578481,110578481,110578481,110578481,110716984,110853115,111008430,
              111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,
              111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111008430,111163745,111299876,111438379,111576593,111714845,111853097,111991311,112129814,112129814,112129814,
              112129814,112129814,112268317,112406531,112544783,112683035,112821249,112959752,113095883,113251198,113251198,113251198,113251198,113389412,113527664,113665916,113804130,113942633,114078764,114234079,
              114389394,114389394,114389394,114389394,114527646,114665898,114804112,114942615,115078746,115234061,115389376,115525507,115525507,115525507,115525507,115663759,115801973,115940476,116076607,116231922,
              116387237,116523368,116661871,116661871,116661871,116661871,116800085,116938588,117074719,117230034,117385349,117521480,117659983,117798197,117798197,117798197,117798197,117936700,118072831,118228146,
              118383461,118519592,118658095,118796309,118934561,118934561,118934561,118934561,119070692,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,
              119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,119226007,
              119226007,119226007,119364510,119502724,119640976,119779228,119917442,120055945,120192076,120347391,120347391,120347391,120347391,120485605,120623857,120762109,120900323,121038826,121174957,121330272,
              121485587,121485587,121485587,121485587,121623839,121762091,121900305,122038808,122174939,122330254,122485569,122621700,122621700,122621700,122621700,122759952,122898166,123036669,123172800,123328115,
              123483430,123619561,123758064,123758064,123758064,123758064,123896278,124034781,124170912,124326227,124481542,124617673,124756176,124894390,124894390,124894390,124894390,125032893,125169024,125324339,
              125479654,125615785,125754288,125892502,126030754,126030754,126030754,126030754,126166885,126322200,126477515,126613646,126752149,126890363,127028615,127166867,127166867,127166867,127166867,127322182,
              127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182,127322182
             };
bool check(int x) {
    int w=x%10;
    x/=10;
    while(x) {
        if(abs(w-(x%10))<2) return false;
        w=x%10;
        x/=10;
    }
    return true;
}
int sol(int x,int y) {
    int a=x/1000000,b=y/1000000,cnt=0,sum1=0,sum2=0,xia=a*1000000,shang=b*1000000;
    if(a==b) {
        for(int i=x; i<=y; ++i) if(check(i)) ++cnt;
        return cnt;
    }//若在同一块中则暴力
    for(int i=xia+1; i<=x-1; ++i) if(check(i)) ++sum1;
    if(x>=1000000) sum1=sum1+d[a-1];//下标要减一
    for(int i=shang+1; i<=y; ++i) if(check(i)) ++sum2;
    sum2=sum2+d[b-1];
    return sum2-sum1;//前缀和
}

int main() {
    scanf("%d%d",&a,&b);
    printf("%d\n",sol(a,b));
    return 0;
}


活动打卡代码 AcWing 1081. 度的数量

Shadow
6个月前
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 35;
int fac[N][N],l,r,K,B;

void init() {
    for(register int i=0; i<N; i++)
        for(register int j=0; j<=i; j++)
            if(j==0) fac[i][j] = 1;
            else fac[i][j] = fac[i-1][j] + fac[i-1][j-1];//递推预处理组合数
}

int dp(int n) {
    if(n==0) return 0;//先判断边界

    int ans = 0;
    int last = 0;//存储往下走右边的分支的时候的一些前缀信息
    //在这道题里存的是前面有多少个一
    int cnt = 0;
    int a[N];
    while(n) a[cnt++] = n%B, n/=B;

    for(register int i=cnt-1; i>=0; i--) {
        int x = a[i];
        //每一位中都分两种情况
        if(x) {//求左边的分支
            ans += fac[i][K-last];//当前这一位是0
            if(x>1) {//才能枚举左边的分支,就是可以填1
                if(K-last-1) ans += fac[i][K-last-1];
                break;
            } else {
                last++;//进入了右边的分支,并且右边的这个a[n-1]正好==1
                if(last>K) break;
            }
        }//至此,所有左边的分支就已经算完了
        if(!i && last==K) ans++;//加上最右侧分支上的方案  
    }
    return ans;
}

int main() {
    init();
    scanf("%d%d%d%d",&l,&r,&K,&B);
    printf("%d\n",dp(r)-dp(l-1));
    return 0;
}
/*
数位dp
技巧1:[x,y] => f(y)-f(x-1)
技巧2:从数的形式来考虑
*/


活动打卡代码 AcWing 1077. 皇宫看守

Shadow
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1555;
int n,f[N][3],w[N];
int first[N],idx;
bool has_fa[N];

struct edge {
    int end,nxt;
} bian[N<<1];

void addedge(int s,int e) {
    idx++;
    bian[idx].end = e;
    bian[idx].nxt = first[s];
    first[s] = idx;
}

void dfs(int s) {
    f[s][1] = 1e9;
    f[s][2] = w[s];
    for(register int i=first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        dfs(e);
        f[s][0] += min(f[e][1],f[e][2]);
        f[s][2] += min(f[e][0],min(f[e][1],f[e][2]));
    }
    //f[e][1]比较麻烦,因为它是被子节点看着,所以要枚举是被哪一个子节点看到 
    for(register int i=first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        f[s][1] = min(f[s][1] , f[s][0]+f[e][2]-min(f[e][1],f[e][2])); 
    }
}

int main() {
    scanf("%d",&n);
    for(register int i=1; i<=n; i++) {
        int s,e,cost,cnt;
        scanf("%d%d%d",&s,&cost,&cnt);
        w[s] = cost;
        while(cnt--) {
            scanf("%d",&e);
            addedge(s,e);
            has_fa[e] = true;
        }
    }
    int rt = 1;
    while(has_fa[rt]) rt++;
    dfs(rt);
    printf("%d\n", min(f[rt][2], f[rt][1]));
    return 0;
}
/*
这道题与上一道题不同的是
对于每一个点,要么这个点上放一个士兵
要么它的父亲和儿子节点上放一个士兵
听上去好像没什么不一样的
从另一个方面来描述
就是一个点上的士兵,可以看守它自己、父节点、和子节点三个点这么一圈
(但是上一个题看了父亲就看不了儿子,反之亦然)

还是可以用状态机
f[i][0]表示i这个点可以被它的父节点看到最小花费
f[i][1]表示i这个点可以被它的子节点看到
f[i][2]表示i这个点它自身上有个士兵
*/


活动打卡代码 AcWing 323. 战略游戏

Shadow
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1555;
int n,f[N][2];
int first[N],idx;
bool has_fa[N];

struct edge {
    int end,nxt;
} bian[N<<1];

void addedge(int s,int e) {
    idx++;
    bian[idx].end = e;
    bian[idx].nxt = first[s];
    first[s] = idx;
}

void dfs(int s) {
    f[s][0] = 0;
    f[s][1] = 1;
    for(register int i=first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        dfs(e);
        f[s][0] += f[e][1];//父节点如果不选的话子节点一定不能选 
        f[s][1] += min(f[e][0],f[e][1]);//父节点如果选了的话子节点可选可不选 
    }
}

void init() {
    memset(first,0,sizeof(first));
    memset(has_fa,0,sizeof(has_fa));
    idx = 0;
}

int main() {
    while(scanf("%d",&n)!=EOF) {
        init();
        for(register int i=1; i<=n; i++) {
            int s,cnt,e;
            scanf("%d:(%d)", &s, &cnt);
            while(cnt--) {
                scanf("%d",&e);
                addedge(s,e);
                has_fa[e] = true;
            }
        }
        int rt = 0;
        while(has_fa[rt]) rt++;
        dfs(rt);
        printf("%d\n", min(f[rt][0], f[rt][1]));
    }
    return 0;
}
/*
最大独立集问题

怎么还出来状态机了
f[i][0/1]
f[i][0]表示所有以i为根的子树,并且不选择第i点的最大权值
f[i][1]表示所有以i为根的子树,并且选择i点的最大权值

没有上司的舞会:每条边最多选一个点
这道题:每条边至少选一个点
*/

//最大独立集 = 总点数 - 最小覆盖


活动打卡代码 AcWing 1074. 二叉苹果树

Shadow
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = N * 2;
int n,m,f[N][N];
int first[N],cnt;

struct edge {
    int end,nxt,len;
} bian[N<<1];

void addedge(int s,int e,int w) {
    cnt++;
    bian[cnt].end = e;
    bian[cnt].len = w;
    bian[cnt].nxt = first[s];
    first[s] = cnt;
}

void dfs(int s,int fa) {
    for(register int i=first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        if(e==fa) continue;
        dfs(e,s);
        for(register int j=m; j>=0; j--)
            for(register int k=0; k<j; k++)
                f[s][j] = max(f[s][j],f[s][j-k]+f[e][k]+bian[i].len);
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for(register int i=1; i<=n-1; i++) {
        int s,e,w; 
        scanf("%d%d%d",&s,&e,&w);
        addedge(s,e,w);
        addedge(e,s,w);
    }
    dfs(1,-1);
    printf("%d\n",f[1][m]);
    return 0;
}
/*
有依赖的背包问题的简化版
我们把每个节点看成是一个物品
然后我们要保留这个节点就必须要保留它的父节点

可以保留的树枝数量就可以看成是背包容量 
点连向父亲的边的权值可以看做是点的价值,
每个点的体积是1(也是把边的代价落下来)

f[i][j]表示以i为根节点的子树中选j个边的最大价值
还是树上背包的做法:树形dp + 分组背包 
*/ 


活动打卡代码 AcWing 1075. 数字转换

Shadow
6个月前
#include <bits/stdc++.h> 
using namespace std;
const int N = 50010;
int n,ans,sum[N];
int first[N], cnt;
bool vis[N];

struct edge{
    int end,nxt;
}bian[N<<1];

void addedge(int s,int e){
    cnt++;
    bian[cnt].end = e;
    bian[cnt].nxt = first[s];
    first[s] = cnt;
} 

int dfs(int s) {
    vis[s] = true;
    int dist = 0;
    int d1 = 0, d2 = 0;
    for(register int i=first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        if(!vis[e]) {
            int d = dfs(e);
            dist = max(dist, d);
            if(d >= d1) d2 = d1, d1 = d;
            else if(d > d2) d2 = d;
        }
    }
    ans = max(ans, d1+d2);
    return dist+1;  //?
}

int main() {
    scanf("%d",&n);
    for(register int i=1; i<=n; i++)//线性筛的思想:这个数它是哪些数的约数 
        for(register int j=2; j<=n/i; j++)
            sum[i*j] += i;

    for(register int i=2; i<=n; i++)
        if(sum[i]<i) addedge(sum[i],i);//这次是连单向边 

    for(register int i=1; i<=n; i++)
        if(!vis[i]) dfs(i);

    printf("%d\n",ans);
    return 0;
}
/*
树的直径的应用
问题转化:
一个数和它的约数之和是一一对应的 
如果数x和它的约数之和y可以互相转化,则可以看成在x和y之间加一条边
并且只有在x>y时才能加这条边
所以,对于每一个数x最多只会向它的约数之和连一条边
可以看出,相当于y是x的父节点(因为树上每个点只会有一个父节点) 

注意:也不一定是树,有可能是森林 
*/


活动打卡代码 AcWing 1073. 树的中心

Shadow
6个月前

树的中心

即到最远点距离最近的点

#include<cstdio>
#include<iostream>
#define re register
#define maxn 100010
using namespace std;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
int ans=INF,n,first[N],cnt; 
int d1[N],d2[N];//往下走的 最长路径和次长路径 
int c1[N],c2[N];
int up[N];//往上走的最长路径 
struct edge {
    int end,len,nxt;
} bian[N<<1];

void addedge(int u,int v,int w) {
    cnt++;
    bian[cnt].end = v;
    bian[cnt].len = w;
    bian[cnt].nxt = first[u];
    first[u] = cnt;
}
int dfs1(int s,int fa) {//向下dfs,用子节点更新父节点 
    d1[s] = d2[s] = -INF;//处理负权边 
    for(register int i = first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        if(e==fa) continue;
        int d = dfs1(e,s) + bian[i].len;
        if(d>=d1[s]) {
            d2[s] = d1[s];
            d1[s] = d;
            c1[s] = e;
        } else if(d>d2[s]) d2[s] = d;
    }
    if(d1[s]==-INF) d1[s] = d2[s] = 0;//处理负权边 
    return d1[s];
}
void dfs2(int s,int fa) { //向上dfs,用父节点更新子节点 
    for(register int i=first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        if(e==fa) continue;
        if(c1[s]!=e) up[e] = max(d1[s],up[s]) + bian[i].len;//不是从它更新来的
        else up[e] = max(d2[s],up[s])+bian[i].len;
        dfs2(e,s);
    }
}
int main() {
    scanf("%d",&n);
    for(register int i=1; i<=n-1; i++) {
        int s,e,w; 
        scanf("%d%d%d",&s,&e,&w);
        addedge(s,e,w),addedge(e,s,w);
    }
    dfs1(1,-1);
    dfs2(1,-1);

    for(register int i=1; i<=n; ++i) 
        if(max(up[i],d1[i])<ans) ans=max(up[i],d1[i]);

    printf("%d\n",ans);
    return 0;
}
/*
每一个点往下和往上走分别存一个次大值和最大值
如果从父节点往下走不经过该节点的话我们就返回最大值
如果经过的话就只能返回次大值 
*/ 


活动打卡代码 AcWing 1072. 树的最长路径

Shadow
6个月前

树的最长路径即树的直径

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,cnt,first[N],ans;
struct edge{
    int end,nxt,len;
}bian[N<<1];

void addedge(int s,int e,int w){
    cnt++;
    bian[cnt].end = e;
    bian[cnt].len = w;
    bian[cnt].nxt = first[s];
    first[s] = cnt;
} 

int dfs(int s,int fa) {
    int dist = 0;//表示从当前点往下走的最大长度
    int d1=0, d2=0; //这个点子树上的最长距离和次长距离 
    for(register int i=first[s]; i; i=bian[i].nxt) {
        int e = bian[i].end;
        if(e==fa) continue;
        int d = dfs(e,s) + bian[i].len;
        dist = max(dist,d);

        if(d>=d1) d2 = d1, d1 = d;//如果当前这个值大于之前的最大值,那么最大值更新成现在的距离,次大值更新成上一个最大值 
        else if(d>d2) d2 = d;//如果当前这个点大于之前的次大值(但是不大于最大值)那么就把现在的值更新成次大值 
    }
    ans = max(ans,d1+d2);
    return dist;
}

int main(){
    scanf("%d",&n);
    for(register int i=1; i<=n-1; i++) {
        int s,e,w;
        scanf("%d%d%d",&s,&e,&w);
        addedge(s,e,w),addedge(e,s,w);
    }

    dfs(1,-1);
    printf("%d\n",ans); 
    return 0;
}