企业官网建设流程全解析

网站的内容策略,wordpress电商建站,仿牌网站专用vps,山东天狐做网站cms文章目录数位DP引入概述练习题数位DP 引入 数位动态规划#xff08;数位DP#xff09;主要用于解决 “在区间 [l,r][l, r][l,r] 这个范围内#xff0c;满足某种约束的数字的数量、总和、平方” 这一类问题 针对这类问题#xff0c;有两类写法#xff0c;一种是记忆化搜…文章目录数位DP引入概述练习题数位DP引入数位动态规划数位DP主要用于解决 “在区间[ l , r ] [l, r][l,r]这个范围内满足某种约束的数字的数量、总和、平方” 这一类问题针对这类问题有两类写法一种是记忆化搜索写法一种是迭代写法。力推记忆化搜索写法原因如下记搜写法容易举一反三、易编码预处理后的迭代写法往往边界条件很多状态转移方程容易写错或漏项其边界容易漏判误判且不同题目时迭代写法的DP过程变化较大而记搜的dfs框架则非常套路容易举一反三。数位dp有个通用的套路就是先采用前缀和思想将求解 “[l, r]这个区间内的满足约束的数的数量” 转化为 “[1, r]满足约束的数量 - 区间[1, l - 1]满足约束的数量 ”所以我们最终要求解的问题通常转化为[ 1 , x ] [1, x][1,x]中满足约束的数量或者[ 0 , x ] [0, x][0,x]中的满足约束的数量 左边界取决于题目然后将数字x xx拆分为一个个数位数位如个位、十位、百位等单个数码比如十进制此处就是指0 ~ 9在数x xx中所占据的一个位置在代码中表现为a [ 1 ⋯ l e n ] a[1 \cdots len]a[1⋯len]将数x xx分解为R RR进制一般为十进制或者二进制用数组存储a [ i ] a[i]a[i]表示x xx在R i − 1 R^{i-1}Ri−1处的系数即x xx这个数的长度为l e n lenlen最高位上的数字为a [ l e n ] a[len]a[len]最低位上的数字为a [ 1 ] a[1]a[1]比如十进制数字4321转化为a aa数组后a 4 4 , a 3 3 , a 2 2 , a 1 1 a_4 4, a_3 3, a_2 2, a_1 1a4​4,a3​3,a2​2,a1​1typedeflonglongLL;LLsolve(LL x){intlen0;while(x0){a[len]x%10;x/10;}returndfs(...);//记忆化搜索}接下来考虑填数高位往低位填即l e n → 1 len \to 1len→1借助一道经典的题目来感受下dp的大致过程例题0洛谷 P4999 烦人的数学作业求解区间[ L , R ] [L, R][L,R]中所有数的数位和之和数位和一个数的所有数位上的数字加起来的和比如313的数位和为3 1 3 7 31373137共1 ≤ T ≤ 20 1 \le T \le 201≤T≤20组数据其中1 ≤ L ≤ R ≤ 10 18 1 \le L \le R \le 10^{18}1≤L≤R≤1018既然叫做记搜也就是就是层层深入每一层搜索填写一个数记忆化搜索函数d f s dfsdfs中我们用形参p o s pospos来表示当前需要填写的位置p o s posposint型变量表示当前枚举的位置一般从高到低话说回来我们需要计算的是[ 0 , x ] [0, x][0,x]的所有数的数位和之和虽然区间范围的左边界最小为1但是我们发现0对答案没有贡献所以我们把范围看成[ 0 , x ] [0, x][0,x]也无妨我们需记录一个变量l i m i t limitlimit表示当前数位是否可以任意填写故在记忆化搜索函数d f s dfsdfs的常设定的形参加上l i m i t limitlimitl i m i t limitlimitbool型变量表示枚举的第p o s pospos位是否受到限制为 true 表示取的数不能大于a [ p o s ] a[pos]a[pos]而只有在[ p o s 1 , l e n ] [pos 1, len][pos1,len]的位置上填写的数都等于a [ i ] a[i]a[i]时该值才为 true否则表示当前位没有限制可以取到[ 0 , R − 1 ] [0, R - 1][0,R−1]因为R RR进制的数中数位最多能取到的就是R − 1 R - 1R−1dfs函数的形参还需要添加sumint型变量表示当前l e n → ( p o s 1 ) len \to (pos 1)len→(pos1)的数位和这种普通的dfs搜索其过程就像是一棵 “满多叉树” 时间复杂度最坏为O ( 10 l e n ) O(10^{len})O(10len)其中len最大值为 191e18有 19 位这显然不能接受而动态规划就是减少冗余的重复计算也就是我们将这棵 “满多叉树” 中相同的子树部分给删除掉从而来优化时空复杂度设状态f [ p o s ] [ s u m ] f[pos][sum]f[pos][sum]表示位置[ p o s 1 , l e n ] [pos 1, len][pos1,len]都已填写完毕且这些数位之和为sum的情况下数位[ 1 , p o s ] [1, pos][1,pos]任意填写即limit为falsef [ p o s ] [ s u m ] f[pos][sum]f[pos][sum]为满足约束的所有数的数位和之和故我们可以大致写出记忆化搜索的代码了其中f ff数组初始化均为− 1 -1−1而∼ f [ p o s ] [ n u m ] \sim f[pos][num]∼f[pos][num]是按位取反操作当值等于− 1 -1−1时返回0 00也就是判断值是否为− 1 -1−1LLdfs(intpos,boollimit,intsum){if(!pos)//递归边界returnsum;if(!limit~f[pos][sum])//没限制并且dp值已搜索过returnf[pos][sum];intuplimit?a[pos]:9;LL res0;for(inti0;iup;i)res(resdfs(pos-1,limitiup,sumi))%md;if(!limit)//记搜可复用f[pos][sum]res;returnres;}然后再solve中调用dfs函数LLsolve(LL x){intlen0;while(x0){a[len]x%10;x/10;}returndfs(len,true,0);//初始状态可以理解为len之前全部卡前导0的上}两个问题问题1怎么证明这个记忆化搜索的优化了原先的时间复杂度问题2为什么状态需要设置为不受l i m i t limitlimit限制的前提下完整代码参考#includebits/stdc.husingnamespacestd;typedeflonglongLL;constexprintN20,md1e97;inta[N];LL f[N][9*185];// f[pos][sum]在[pos 1, len]中的数位和为sum[1, pos]的数位任意填。满足这样约束的数的总和// 总共最多 19 * (9 * 18)个状态LLdfs(intpos,boollimit,intsum){if(!pos)//递归边界returnsum;if(!limit~f[pos][sum])//没限制并且dp值已搜索过returnf[pos][sum];intuplimit?a[pos]:9;LL res0;for(inti0;iup;i)res(resdfs(pos-1,limitiup,sumi))%md;if(!limit)//记搜可复用f[pos][sum]res;returnres;}LLsolve(LL x){intlen0;while(x0){a[len]x%10;x/10;}returndfs(len,true,0);//初始状态可以理解为len之前全部卡前导0的上}intT;intmain(){cin.tie(0)-sync_with_stdio(false);memset(f,-1,sizeoff);//可复用的多组样例都可使用cinT;while(T--){LL l,r;cinlr;LL ans(solve(r)-solve(l-1)md)%md;if(ans0)ansmd;coutans\n;}}概述在上述例题0中我们已经知道了数位dp的过程我们往往把约束设置为形参和动态规划的状态以下为记忆化搜索函数d f s dfsdfs的常设定的形参p o s posposint型变量表示当前枚举的位置一般从高到低l i m i t limitlimitbool型变量表示枚举的第p o s pospos位是否受到限制为true表示取的数不能大于a [ p o s ] a[pos]a[pos]而只有在[ p o s 1 , l e n ] [pos1, len][pos1,len]的位置上填写的数都等于a [ i ] a[i]a[i]时该值才为true否则表示当前位没有限制可以取到[ 0 , R − 1 ] [0, R-1][0,R−1]因为R RR进制的数中数位最多能取到的就是R − 1 R-1R−1l a s t lastlastint型变量表示上一位第p o s 1 pos1pos1位填写的值往往用于约束了相邻数位之间的关系的题目l e a d 0 lead0lead0bool型变量表示是否有前导零即在l e n → ( p o s 1 ) len \to (pos1)len→(pos1)这些位置是不是都是前导零基于常识我们往往默认一个数没有前导零也就是最高位不能为0即不会写为000123而是写为123只有没有前导零的时候才能计算0的贡献。那么前导零何时跟答案有关统计0的出现次数相邻数字的差值以最高位为起点确定的奇偶位s u m sumsumint型变量表示当前l e n → ( p o s 1 ) len \to (pos1)len→(pos1)的数位和r rrint型变量表示整个数前缀取模某个数m mm的余数该参数一般会用在约束中出现了能被m mm整除当然也可以拓展为数位和取模的结果s t ststint型变量用于状态压缩对一个集合的数在数位上的出现次数的奇偶性有要求时其二进制形式就可以表示每个数出现的奇偶性练习题通过例题来应用中掌握非常套路化的数位dp过程P2602 [ZJOI2010] 数字计数#includebits/stdc.husingnamespacestd;typedeflonglongLL;constexprintN20;inta[N];intdigit;//当前需要统计的数字// f[pos][cnt][0/1]当最高位已经填了没有前导0时在[pos 1, len]中digit填了cnt个[1, pos]任意填digit出现的次数// 第三维0表示digit0,第三维为1表示digit!1// 当limitfalse时容易知道填1-9的数量是相同的LL f[N][N][2],ans[10];LLdfs(intpos,boollimit,boollead0,intcnt){if(!pos)// 递归边界returncnt;autonowf[pos][cnt][digit!0];if(!limit!lead0~now)// 没限制并且dp值已搜索过returnnow;intuplimit?a[pos]:9;LL res0;for(inti0;iup;i){//填0的时候需注意是否为前导//前导零不算入0的个数if(lead0digit0i0){resdfs(pos-1,limitiup,lead0i0,0);}else{if(idigit)resdfs(pos-1,limitiup,lead0i0,cnt1);elseresdfs(pos-1,limitiup,lead0i0,cnt);}}if(!limit!lead0)//无限制并且没有前导0nowres;returnres;}voidsolve(LL x,intf){intlen0;while(x0){a[len]x%10;x/10;}for(inti0;i9;i){digiti;ans[i]f*dfs(len,1,1,0);}}intmain(){memset(f,-1,sizeoff);LL l,r;cinlr;solve(r,1);//加上[1, r]solve(l-1,-1);//扣除掉[1, l-1]for(inti0;i9;i)coutans[i] ;}