数位 DP 入门 (不要 62+windy 数)

\[I\]

平常的做法是设 \(f_{i,j}\) 为 \(0\)~\(j \times 10^{i-1}\) 的合法个数,这里用某种神奇而快速的做法。

简化题意:

• 不要 \(6\ 2\) 连在一起的数字。
• 不要有 \(4\) 的数字。

我们暂且设 :

• \(f_{i,1}\) 为 \(0\)~\(10^i-1\) 的合法个数。
• \(f_{i,2}\) 为 \(0\)~\(10^i-1\) 的不合法个数。
• \(f_{i,3}\) 为 \(0\)~\(10^i-1\) 的开头为 \(2\) 的合法个数。

我们考虑到要求 \(62\) 这种东西,所以要用 \(f_{i,3}\)。
其实这三个数组可以缩成一个,就是 \(f_{i,1}\)。

为了方便我们把 \(f_{i,3}\) 去掉。

考虑到 \(f_{i,3}\) 要求合法,且开头是 \(2\)。所以我们用上一位合法的开头加上一个 \(2\) 就是转移。
\[f_{i,3}=f_{i-1,1}\]

考虑合法的如何转移。因为 \(6\ 2\) 会导致不合法,而现在可以给开头加上一个 \(6\),所以我们只需要减去一个上一位的开头为 \(2\) 的个数。

\[f_{i,1}=-f_{i-2,1}\]

然后考虑到上一次合法的数字转移过来只有开头加上 \(4\) 会 \(GG\),所以加上一个 \(f_{i-1,1} \times 9\)。

\[f_{i,1}=f_{i-1,1} \times 9-f_{i-2,1}\]

然后考虑 \(f_{i,2}\) 的转移。我上一位的不合法数字在开头上面加上什么都是不合法的。且我可以给合法的数字加上一个 \(4\) 使其不合法。再且我可以给那些以 \(2\) 开头的数字加上一个 \(6\) 使其不合法。所以就是:

\[f_{i,2}=f_{i-1,2} \times 10+f_{i-1,1}+f_{i-2,1}\]

预处理时间复杂度 \(O(k)\),\(k\) 为位数。

查询就更简单了~

首先我们要把上一位的不合法减掉:

\[ans-=num_i\times f_{i-1,2}\]

如果我的数字本身出现了不合法,那么我后面的所有数字都是不合法的。\(num_i\times f_{i-1,2}\) 已经减过了,就减 \(num_i \times f_{i-1,1}\)。

\[ans-=num_i \times f_{i-1,1}\]

如果数字本身没有不合法,那么看情况讨论。

• 如果出现 \(4\),那么上一位的所有合法都是废的。

\[ans-=f_{i-1,1}\]

• 如果出现 \(6\),那么上一位所有 \(2\) 开头的都是废的。

\[ans-=f_{i-2,1}\]

• 如果我现在存在了一个 \(6\ 2\),那么这一位所有的 \(2\) 都是废的。

\[ans-=f_{i-1,1}\]

最后统计一下数字本身是否合法。

varfuck:array[-1..15,-1..3] of longint;i,j,x,y:longint;function Slove(ans:longint):longint; varnum:array[-1..15] of longint;i,len,flag:longint;s:string; beginfillchar(num,sizeof(num),0); Delete(s,1,length(s));str(ans,s); len:=length(s); flag:=1;for i:=1 to len do val(s[i],num[len-i+1]);for i:=len downto 1 dobegindec(ans,num[i]*fuck[i-1,2]);if flag=666 then dec(ans,num[i]*fuck[i-1,1]) elsebeginif num[i]>4 then dec(ans,fuck[i-1,1]);if num[i]>6 then dec(ans,fuck[i-2,1]);if (num[i+1]=6)and(num[i]>2) then dec(ans,fuck[i-1,1]);end;if (num[i]=4)or((num[i+1]=6)and(num[i]=2)) then flag:=666;end;exit(ans); end;beginfuck[0,1]:=1;for i:=1 to 9 dobeginfuck[i,1]:=fuck[i-1,1]*9-fuck[i-2,1];fuck[i,2]:=fuck[i-1,2]*10+fuck[i-1,1]+fuck[i-2,1];end;read(x,y);while (x<>0)and(y<>0) dobeginwriteln(Slove(y+1)-Slove(x)); read(x,y);end; end.

\[II\]

同样是递推来做。

我们设 \(f_{i,j}\) 为 \((j-1) \times 10^{i-1}+1\)~\(j \times 10^{i-1}\) 的幸运数字的个数。跟平常一样,是为了压空间,也是为了好转移。

转移就异常的简单了:(且满足 \(x\ y\) 不是 \(6\ 2\),也不是 \(4\))

\[f_{i,x}=\sum\limits^{9}_{x=0} \sum\limits^{9}_{y=0} f_{i-1,y}\]

然后我们在查询的时候直接加上就好了。

来谈谈一直没有说过的查询,其实随便列举一个数字 \(2333\):

• 最高位 : \(0\)~\(1000\),\(1001\)~\(2000\)
• 次高位 : \(0\)~\(100\),\(101\)~\(200\),\(201\)~\(300\)
• 第三高位 : \(0\)~\(10\),\(11\)~\(20\),\(21\)~\(30\)
• 最低位 : \(0\)~\(1\),\(1\)~\(2\),\(2\)~\(3\)

所以大概明白了数位 \(DP\) 的套路。

varfuck:array[-1..15,-1..10] of int64;i,x,y:longint;function Slove(x:longint):int64; varnum:array[-1..15] of longint;i,j,len:longint;s:string; beginfillchar(num,sizeof(num),0);str(x,s); len:=length(s); Slove:=0;for i:=1 to len do val(s[i],num[len-i+1]);for i:=len downto 1 dobeginfor j:=0 to num[i]-1 dobeginif (num[i+1]=6)and(j=2) then continue;inc(Slove,fuck[i,j]);end;if (num[i]=4) then break;if (num[i]=2)and(num[i+1]=6) then break;end; end;beginfor i:=0 to 9 do fuck[1,i]:=1; fuck[1,4]:=0;for i:=2 to 10 do for x:=0 to 9 do for y:=0 to 9 do begin if (x=6)and(y=2) then continue; if (x=4)or(y=4) then continue; inc(fuck[i,x],fuck[i-1,y]); end;read(x,y);while (x<>0)and(y<>0) dobeginwriteln(Slove(y+1)-Slove(x));read(x,y);end; end.

第一道数位 \(DP\)。

由于空间不够,所以我们必须要压缩一下。

所以我们设 \(f_{i,j}\) 为 \(1\)~\(X\) 的 \(windy\)。(其中 \(X\) 满足第一位等于 \(j\),且有 \(i\) 位)

\[f_{i,j}=\sum\limits^{9}_{l=j+2} f_{i-1,l} +\sum\limits^{j-2}_{l=0} f_{i-1,l}\]

for i:=0 to 9 do fuck[1,i]:=1;for i:=2 to 20 do for j:=0 to 9 do begin for k:=j-2 downto 0 do inc(fuck[i,j],fuck[i-1,k]); for k:=j+2 to 9 do inc(fuck[i,j],fuck[i-1,k]); end;

这样子就很好的压缩了空间。

我们把 \(C(l,r)\) 变为 \(C(r+1)-C(l)\)

(\(C(r)-C(l-1)\) 莫名 \(WA\) 了?)

我们考虑求一个数字 \(x\) 的 \(windy\)。我们定义 \(X\) 为 \(x\) 倒立过来的数组,\(len\) 为数组长度。如 \(x=7192\),\(X_i=\{2,9,1,7\},len=4\)。

我们先把 \(0\)~\(999\) 的 \(windy\) 求一下。

\[\sum\limits^{len-1}_{i=1}\sum\limits^{9}_{j=1} f_{i,j}\]

for i:=1 to len-1 do for j:=1 to 9 do inc(Windy,fuck[i,j]);

然后把 \(1000\)~\(6999\) 的求了。

\[\sum\limits^{X_{len}-1}_{i=1} f_{len,i}\]

for i:=1 to num[len]-1 do inc(Windy,fuck[len,i]);

最后的最难搞~要把剩下的求了。

\[\sum\limits^{1}_{i=len-1} \sum\limits^{X_{i}-1}_{j=0} f_{i,j} (abs(j-X_{i+1})>=2)\]

for i:=len-1 downto 1 dobeginfor j:=0 to num[i]-1 do if abs(j-num[i+1])>=2 then inc(Windy,fuck[i,j]);if abs(num[i]-num[i+1])<2 then break;end;

就没了。

转载于:https://www.cnblogs.com/FibonacciHeap/articles/10321802.html

总结

以上是生活随笔为你收集整理的数位 DP 入门 (不要 62+windy 数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。