晋中市住房与城乡建设厅网站,培训机构加盟,企业内网搭建要多少钱,陕西网站制作商前言#xff1a;这是蒟蒻第一次写算法系列#xff0c;请诸位大佬原谅文笔与排版。 一、导入 在刷题的时候#xff0c;我们有时会见到这样一类问题#xff1a;在区间$[l,r]$内#xff0c;共有多少个整数满足某种条件。如果$l$和$r$间的差很小#xff0c;我们可以考虑暴力枚… 前言这是蒟蒻第一次写算法系列请诸位大佬原谅文笔与排版。 一、导入 在刷题的时候我们有时会见到这样一类问题在区间$[l,r]$内共有多少个整数满足某种条件。如果$l$和$r$间的差很小我们可以考虑暴力枚举直接判断。然而若$lr10^9$甚至更大呢 这时往往就可以用到一种dp方式数位dp。 二、做法 这里先放一道例题1026: [SCOI2009]windy数。 题意求在区间$[l,r]$内满足相邻数位的差2的整数的个数。 首先我们可以发现$[l,r]$的答案$[1,r]$的答案-$[1,l)$的答案。于是我们可以把问题转化为求$[1,r]$和$[1,l-1]$的答案。因为$lr2*10^9$所以暴力枚举肯定行不通。但是我们可以发现这道题中整数需满足的条件只与相邻数位有关这启示我们也许可以按位dp 我们先来看一张经典的图表示区间$[0,22]$ 这幅图中把正整数按位用树的形式表示那么区间$[0,x]$这里x22就可以拆成多棵满10叉树即图中的蓝圈而且因为每层所用的树个数不会超过10棵0~9总共有$\log_{10}{x}$层则树的个数规模为$O(10\log{x})$。 那么单棵满10叉树的答案怎么求呢我们仔细观察这棵树那么就可以发现每棵满10叉树表示的数是位数相同等于它从下往上数所处的层数最高位相同等于根节点表示的数且该树的答案只与以树根的10个儿子为根的10棵子树的答案有关。并且在整棵树中处在同一层的且子树根节点表示的数相同的树即位数相同最高位相同它们是等价的。于是我们就可以直接设$f[i][j]$表示有i位最高位为j的满足条件的整数的个数然后xjb转移。于是就可以优哉游哉地dp 然后按图统计答案了。 不过这道题还是比较麻烦因为需要排除前导零的影响不过核心思想还是上面的那样然后再分位数统计就好了。 代码时间复杂度$O(10^2\log{r})$ #includecstdio
#includecmath
#includecstdlib
#includecstring
#includectime
#includealgorithm
#includequeue
#includevector
#includemap
#define ll long long
#define ull unsigned long long
#define max(a,b) (ab?a:b)
#define min(a,b) (ab?a:b)
#define lowbit(x) (x -x)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-18
#define maxn 100020
inline ll read(){ll tmp0; char cgetchar(),f1; for(;c0||9c;cgetchar())if(c-)f-1; for(;0cc9;cgetchar())tmp(tmp3)(tmp1)c-0; return tmp*f;}
inline ll power(ll a,ll b){ll ans0; for(;b;b1){if(b1)ansans*a%mod; aa*a%mod;} return ans;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void swap(int a,int b){int tmpa; ab; btmp;}
using namespace std;
int f[20][10];
int l,r;
int dp(int x)
{int num[20],len0;for(;x;x/10)num[len]x%10;for(int i0;i9;i)f[1][i]1;//预处理 for(int i2;ilen;i)for(int j0;j9;j){f[i][j]0;for(int k0;k9;k)if(abs(j-k)2)f[i][j]f[i-1][k];}//处理f数组f[i][j]表示有i位,最高位为j的的windy数个数*/ int ans0;for(int i1;ilen;i)for(int j1;j9;j)ansf[i][j];//统计位数小于len的数一定小于n直接加上 for(int ilen;i;i--){int l(ilen)?1:0,r(i1)?num[i]:num[i]-1;//不含前导零所以最高位不能取0从1开始枚举否则从0开始//除个位以外因当前位若取num[i]可能超出1~n的范围所以只能取到num[i]-1因为询问1~n时包含n所以个位的上限要取num[i]for(int jl;jr;j)if(ilen||abs(j-num[i1])2)ansf[i][j];if(ilenabs(num[i]-num[i1])2)break;//统计下一位时这一位取的是num[i]若会和上一位num[i1]发生冲突则不可能出现windy数直接break掉 }return ans;
}
int main()
{lread(); rread();printf(%d\n,dp(r)-dp(l-1));
} bzoj1026 三、归纳 数位dp的特征数据规模大统计整数个数被统计的数满足的条件往往与数位之间的关系或数位间的运算有关。 基本做法差分先按位dp出所需数据$f[i][S]$-i位数状态为S然后再拆分原区间用dp出的数据统计。 四、其他例题 1、【bzoj1833】[ZJOI2010] count 数字计数 裸的数位dp分别计算每个数字出现的次数做法和上面类似。 代码 #includecstdio
#includecmath
#includecstdlib
#includecstring
#includectime
#includeiostream
#includealgorithm
#includequeue
#includevector
#includemap
#define ll long long
#define ull unsigned long long
#define max(a,b) (ab?a:b)
#define min(a,b) (ab?a:b)
#define lowbit(x) (x -x)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-18
#define maxn 100010
inline ll read(){ll tmp0; char cgetchar(),f1; for(;c0||9c;cgetchar())if(c-)f-1; for(;0cc9;cgetchar())tmp(tmp3)(tmp1)c-0; return tmp*f;}
inline ll power(ll a,ll b){ll ans1; for(;b;b1){if(b1)ansans*a%mod; aa*a%mod;} return ans;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void swap(int a,int b){int tmpa; ab; btmp;}
using namespace std;
ll f[20][10][10],base[20];
ll l,r;
void prework()
{base[0]1;for(int i1;i13;i)base[i]base[i-1]*10;for(int i0;i9;i)f[1][i][i]1;for(int i2;i13;i)for(int j0;j9;j){ll xf[i-1][0][0]f[i-1][0][1]*9;for(int k0;k9;k){f[i][j][k](jk?base[i-1]:0)x;}}
}
ll solve(ll n,int num)
{if(n0)return 0;ll tmpn;//这里n是为了把闭区间转化为开区间因为下面求解时1~n的答案并不包括n。。int a[20],len0;for(;tmp;tmp/10)a[len]tmp%10;for(int i1;ilen;i)for(int j1;j9;j)ansf[i][j][num];for(int ilen;i;i--){for(int j(ilen?1:0);ja[i];j)ansf[i][j][num];n-a[i]*base[i-1];if(a[i]num)ansn;}return ans;
}
int main()
{prework();lread(); rread();for(int i0;i9;i)printf(%lld ,solve(r,i)-solve(l-1,i));printf(%lld\n,solve(r,9)-solve(l-1,9));
} bzoj1833 转载于:https://www.cnblogs.com/quzhizhou/p/9245648.html
