数位统计DP
数位统计DP是一种有关数字的限制问题,一般问题形式类似于给定若干限制条件,求满足条件的第K小的数是多少,或者是询问区间\([L,R]\)内有多少满足要求的数字,对于这种类型的题,我们一般是先使用动态规划进行预处理,再运用类似与倍增优化DP的拼凑思想拼出最后的答案,亦或者是试填法
在这类题中,我们动态规划的状态设计一般是第一维是第\(i\)位数字,也就是阶段,后面几个维度一般是题目给的限制条件诞生的维度。
在做题过程中,这类型的题数据范围一般较大,但我们动态规划的算法复杂度大约为\(O(\log^k N)\),至于拼凑与试填法的复杂度也是对数级别。这里的题很多与数学问题有所交叉,可以留意一下
做题套路
- 第K大,遇到这种问题的一般步骤是:动态规划预处理,再使用试填法,这个过程从高位考虑到低位,考虑当前位有多少种选择,填了当前位置之后有多少种方案(排名),类似于平衡树求排名,我们从小到大枚举每一位的可能性,当我们可以填i的时候,如果填i之后的方案数不够K,那么i就不可以填,此时还要令K-=填i的方案数,注意一定得减,当找到的第一个方案数大于k的,这个方案就是我们应该选择的方案。这个的原理我们可以把整个所有的可能性看成一颗搜索树,每一个节点上都存着它有多少个叶子节点(对应方案数),我们要在这棵搜索树里找到从树根到排名为K的叶子节点的路径就是我们的答案,就与平衡树,权值线段树类似
- 求区间\([L,R]\),这里因为是关于数的统计问题,是无后效性的,于是我们可以将其转换为前缀和运算,同样的,先进行动态规划预处理,用某些标志性的点进行拼凑出答案,当然我们也可以使用试填法的思想,只不过这个变成了统计方案而已
注意事项
- 时刻注意前导零的处理
- 强调不重不漏性
- 注意到动态规划的维度等等不要冗余
实战
例题1:装饰围栏
题目描述:
有 \(N\) 块长方形的木板,长度分别为 \(1,2,…,N\),宽度都是\(1\)。
现在要用这 \(N\) 块木板组成一个宽度为 \(N\) 的围栏,满足在围栏中,每块木板两侧的木板要么都比它高,要么都比它低。
也就是说,围栏中的木板是高低交错的。
我们称“两侧比它低的木板”处于高位,“两侧比它高的木板”处于低位。
显然,有很多种构建围栏的方案。
每个方案可以写作一个长度为 \(N\) 的序列,序列中的各元素是木板的长度。
把这些序列按照字典序排序,如下图所示,就是 \(N=4\) 时,所有满足条件的围栏按照木板长度的字典序排序后的结果。
现在给定整数 C,求排名为 C 的围栏中,各木板的长度从左到右依次是多少。
\(1≤N≤20,\)
\(0<C<2^{63}\)
分析
很明显,N很小,C很大,这是一个第K大问题,我们按照套路来处理
- 设计动态规划:由于N很小,我们设计一个与N相关的状态,又因为这个涉及到高低排名,于是:设\(f[i,j,k]\)表示用\(i\)块木板,其中最左边木板的排名为\(j\),身处\(k\)位(0低1高)的方案数,注意这里我们采用了类似排名的描述,而不是像长度为j这样的绝对性描述,这是因为在\(1\sim N\)中,排名为j和长度为j是等价的,且运用排名会使得我们状态转移非常轻松
- 进行动态规划预处理:有状态转移方程:
- 进行拼凑,具体步骤为:
(1). 假设我们已经填好了\(i-1\)块木板,记上一块木板的长度为\(last\),位于\(k\)位,现在我们来考虑第\(i\)块木板
(2). 将\(k\)改为\(k\oplus 1\)即可得到当前木板的状态,然后我们从小到大枚举当前木板的实际长度和相对排名,尝试着使用这一个方案进行下一步
(3).设我们枚举的实际长度为\(len\),相对排名为\(j\),若\(f[n-i+1,j,k]<C\),令\(C=C-f[n-i+1,j,k]\),继续尝试更大的\(j\),否则这个\(j\)就是我们第\(i\)位的答案,进行下一位的枚举,直到最后就得出了答案,当然,最初的计算我们就直接判断\(k=0/1\)谁可以就可以了
#define int long long
int t,f[25][25][2],n,m,vis[25];
void init(){
f[1][1][0]=f[1][1][1]=1;
for(int i=2;i<=20;i++)
for(int j=1;j<=i;j++){
for(int k=1;k<j;k++)f[i][j][1]+=f[i-1][k][0];
for(int k=j;k<i;k++)f[i][j][0]+=f[i-1][k][1];
}
}//DP预处理
signed main(){
init();
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
memset(vis,0,sizeof vis);
int last,k;
for(int j=1;j<=n;j++){
if(f[n][j][1]>=m){
last=j;
k=1;
break;
}
else m-=f[n][j][1];
if(f[n][j][0]>=m){
last=j;
k=0;
break;
}
else m-=f[n][j][0];
}//枚举第一位的情况
vis[last]=1;
printf("%lld",last);
for(int i=2;i<=n;i++){
k^=1;
int j=0;
for(int len=1;len<=n;len++){
if(vis[len])continue;
j++;
if(k==0&&len<last||k==1&&len>last){
if(f[n-i+1][j][k]>=m){
last=len;break;
}
else m-=f[n-i+1][j][k];
}
}
vis[last]=1;
printf(" %lld",last);
}
puts("");
}
return 0;
}
例题2:圆形数字
题目描述:
定义圆形数字如下:
把一个十进制数转换为一个无符号二进制数,若该二进制数中 0 的个数大于或等于 1 的个数,则它就是一个圆形数字。
现在给定两个正整数 a 和 b,请问在区间 [a,b] 内有多少个圆形数字。
分析
下面简称圆数
对于这道题,由于其与二进制有关,且要命的是这个二进制数不能含有前导零,且统计与0有关,这就逼迫我们不得不不记录前导零
那么对于这道题DP的状态就很明显了,设\(f[i,j]\)表示有\(i\)位的数里有\(j\)位是0(不含前导零)的数的数量
不难发现,这个数很容易抽象成:给定\(i\)个数,需要从中选出\(j\)个强制变成0,并且不能选择第一个数(为开头的1),很明显这就是一个组合数:\(f[i,j]=C_{i-1}^j\),值得说的是,我们之所以以0来作为状态而不是1,是因为0相对于1更方便统计,因为组合数可以直接算,这里就不说了,当然也可以借\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)这个性质计算
那么我们下面讨论如何求\([1,a]\)中圆数的数量
考虑将a也拆成二进制,假设有\(tot\)位(\(1\sim tot\)),那么对于二进制表示下位数不足\(tot\)的部分就非常容易统计了
这部分的贡献一共是
很快可以算出来,然后我们考虑第\(tot\)位该怎么算
我们设\(a\)被二进制分解为\(a_{tot}a_{tot-1}…a_1\)(从高到低)
下面我们按从高到低的顺序进行拼凑
详细地说,我们设当前已经拼到了第\(i\)位,第\(tot\sim i+1\)一共有\(b\)个0,当前累计的答案为\(ans\),那么我们就可以分类讨论了
- \(a_i=1\),此时如果我们拼的数这一位取0,那么这个数后面无论再怎么取都一定不会超过\(a\)了,于是我们就可以把取0这一部分的答案累加上,写成公式是:
- \(a_i=0\),令\(b=b+1\)
一路统计下来我们就可以得到答案
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[55],cnt,tot,c[55][55],n,m,a,b;
#define f(i,j) c[i-1][j]
int solve(int a){
if(a==0)return 0;
tot=0;
while(a){
num[++tot]=a&1;
a>>=1;
}
int ans=0;
for(int i=1;i<tot;i++){
int k=(i+1)/2;
for(int j=k;j<=i;j++){
ans+=f(i,j);
}
}
int b=0;
for(int i=tot-1;i>0;--i){
if(num[i]==1){
for(int p=(tot+1)/2-b-1;p<=i;p++)ans+=f(i,p);//加上这一位填0的收益
}
else b++;
}
if(b>=(tot+1)/2)ans++;
return ans;
}
int main(){
for(int i=0;i<=30;i++)c[i][0]=1;
for(int i=1;i<=30;i++){
for(int j=1;j<=i;j++){
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
}
scanf("%d%d",&a,&b);
printf("%d\n",-(solve(a-1)-solve(b)));
}
例题3:计数问题
这个题直接来一个数学做法
具体看我做题时的手稿:
至少我认为这还是比较好懂的,我们只需要把问题转换为前缀和来做就可以了,顺带的,\(1\sim9\)可以像我手稿上的直接做,但是0的时候注意前导零,具体看代码
int cnt(int n,int num) {
int ans=0,i=1,qd0=0;//前导零
while(i<=n){
int l=n/i,r=n%i;
ans+=(l+9-num)/10*i;
if(l%10==num)ans+=r+1;
if(!num)qd0+=i;
i*=10;
}
if(!num)qd0-=1;
return ans-qd0;
}
int main(){
int a,b;
while(~scanf("%d%d",&a,&b)&&a&&b) {
if(a>b)a^=b,b^=a,a^=b;//装逼必备,把式子展开你就懂了
for(int i=0;i<=9;++i)
printf("%d ",cnt(b,i)-cnt(a-1,i));
puts("");
}
return 0;
}
标签:last,木板,int,tot,ans,数位,我们,DP,入门
From: https://www.cnblogs.com/oierpyt/p/16940022.html