信息学奥赛一本通 1586：【 例 2】数字游戏

【题目链接】ybt 1586【 例 2】数字游戏【题目考点】1. 数位动规数位动规是用于解决数位相关问题的动态规划方法。题型常为统计给定区间中满足给定条件的数的数量。条件往往与数位相关区间范围很大一般超过10 9 10^9109例统计区间[ L , R ] [L, R][L,R]中含有数字1的整数的数量统计区间[ L , R ] [L, R][L,R]中各数位是不降序列的数的个数。统计区间[ L , R ] [L, R][L,R]中各个数码出现的次数。记count(a,b)表示区间[ a , b ] [a, b][a,b]内符合条件的整数数量。那么可以利用通过前缀和求子段和的思路count(a,b) count(0,b)-count(0,a-1)。因此可以将问题转为求区间[ 0 , n ] [0,n][0,n]内符合条件的整数数量。统计[ L , R ] [L, R][L,R]中含有数字1的整数的数量为[ 0 , R ] [0,R][0,R]中含有数字1的整数数量减去[ 0 , L − 1 ] [0,L-1][0,L−1]中含有数字1的整数数量。数位动规问题大体求解步骤设solve函数传入参数n nn求[ 0 , n ] [0, n][0,n]中满足条件的数的个数设a aa数组将n nn数位分离结果存储在a aa数组中a i a_iai​为a aa的第i ii位(位号常常设为从1开始)a n anan为n nn的位数。动态规划求解问题将结果返回。主函数中调用solve(b)-solve(a-1)求区间[ a , b ] [a, b][a,b]中满足条件的数的个数。数位动规的解题思想类似深搜求全排列需要从高位到低位逐位确定每一位的值。第i ii位可以取哪些值取决于当前“每一位的值是否受限”如果处于受限状态第i ii位可以取到的最大值为a i a_iai​如果不处于受限状态在10进制下第i ii为可以取到的最大值为9。例求0~135中满足条件的数。对135数位分离后a 1 5 , a 2 3 , a 3 1 , a_15, a_23, a_31,a1​5,a2​3,a3​1,。如果已经确定第3位和第二位为13那么第1位最大可以取到的值为a 1 5 a_15a1​5因为如果这一位取大于5的值比如取6得到的数为136得到的整数会超出给定的范围。如果已经确定的第3位为1第2位为2那么第1位可以取0~9中的任意数比如取9得到的数为129得到的整数仍然在范围之内。动规状态的阶段有第1~i ii位相关状态j jj是否受限l i m limlim以及第i 1 i1i1位是否为前导0状态l e a d leadlead。常使用记忆化递归完成动规求解。存在递推解题写法不如记忆化递归更加简洁易懂。【解题思路】本题要求得到不降数也就是低位数位的值要大于等于高位数位的值自然想到动规的阶段中增加“最高位必须大于等于某个数”的要求。状态定义阶段第1~i ii位最高位大于等于j jj每位是否受限l i m limlim决策这一位数填什么策略一个不降整数策略集合第1~i ii位最高位大于等于j jj每位是否受限为l i m limlim的所有整数。统计量数量状态定义d p i , j , l i m dp_{i, j, lim}dpi,j,lim​第1~i ii位最高位大于等于j jj每位是否受限为l i m limlim的整数数量。状态转移方程策略集合第1~i ii位最高位大于等于j jj每位受限为l i m limlim的整数数量。分割策略集合根据第i ii位的取值不同以及当前是否为受限状态进行分割策略集合。考察第i ii位的取值范围下限为j jj如果该数每位受限上限为整数最大范围a aa的第i ii位的值a i a_iai​如果不受限则上限为9。因此取值范围的上限u p upup的值为int up lim ? a[i] : 9;在[ j , u p ] [j, up][j,up]范围内枚举第i ii位的取值v vv如果当前该数每位受限且第i ii位取值v vv为上限a i a_iai​也就是u p upup判断条件写为lim v up。那么第1~i − 1 i-1i−1位数的要求为最高位大于等于v vv且每位受限满足条件的数增加d p i − 1 , v , t r u e dp_{i-1,v,true}dpi−1,v,true​否则当前该数每位不受限或受限但第i ii位取值小于a i a_iai​那么第1~i − 1 i-1i−1位的要求为最高位大于等于v vv每位不受限满足条件的数增加d p i − 1 , v , f a l s e dp_{i-1,v,false}dpi−1,v,false​。状态转移方程为当l i m t r u e limtruelimtrue时u p a i upa_iupai​当l i m f a l s e limfalselimfalse时u p 9 up9up9。d p i , j , l i m ∑ v j u p d p i − 1 , v , l i m ∧ ( v u p ) dp_{i,j,lim} \sum_{vj}^{up}dp_{i-1,v,lim\land (vup)}dpi,j,lim​∑vjup​dpi−1,v,lim∧(vup)​考察当i 1 i1i1时d p 1 , j , l i m dp_{1,j,lim}dp1,j,lim​的值应该为[ j , u p ] [j, up][j,up]区间中数值的的个数u p − j 1 up-j1up−j1如果继续使用状态转移方程只需要让d p 0 , v , l i m ∧ ( v u p ) dp_{0,v,lim\land (vup)}dp0,v,lim∧(vup)​的值都为1 11即可让d p 1 , j , l i m u p − j 1 dp_{1,j,lim}up-j1dp1,j,lim​up−j1。因此可以设状态初值或记忆化搜索的递归出口当i 0 i0i0时d p i , j , l i m 1 dp_{i,j,lim}1dpi,j,lim​1。【题解代码】解法1数位动规#includebits/stdc.husingnamespacestd;constintN15;typedeflonglongLL;intx,y,an,a[N],dp[N][10][2];//dp[i][j][lim]第1~第i位第i位的值j每位受限情况lim不降数的个数。intdfs(inti,intj,boollim){if(i0)return1;if(dp[i][j][lim]!-1)returndp[i][j][lim];intres0,uplim?a[i]:9;for(intvj;vup;v)resdfs(i-1,v,limvup);returndp[i][j][lim]res;}intsolve(intn){an0;do{a[an]n%10;n/10;}while(n0);//对n数位分离memset(dp,-1,sizeof(dp));//dp初值为-1用于记搜。如果某位置值为-1说明该位置的值没有求出过。returndfs(an,0,true);}intmain(){while(cinxy)coutsolve(y)-solve(x-1)\n;return0;}