标签：string   总结   前缀和   表示   return   开始   char   问题：   oid   

属于数位\(DP\)入门级别的题目，但我做这类题不多，还是要总结一下这道经典题目

\(Description\)

题面
给定\(a,b\),求\([a,b]\)区间有多少个数满足:任意两个相邻数位之间的差的绝对值\(>=2\)
\(a,b

\(Solution\)

数位\(DP\)的基本思想是一个一个数确定，逼近到边界
数位\(DP\)一般设计状态为\(dp[i][s]\)表示当前考虑到第\(i\)位（从最低位编号），当前位置或附近位置状态为\(s\)的方案数。
有时候需要预处理，有时候直接数位\(dp\)即可

对于这个题，比较显然的是设计状态\(dp[i][j]\)表示当前考虑到第\(i\)位（\(1--(i-1)\)都已经考虑），第\(i\)位为\(j\)的方案数
状态转移比较显然，注意也要处理\(0\)的情况

void pre()
{
    pow[0]=1;
    for(re int i=1;i=2) dp[i][j]+=dp[i-1][k];//把0的情况也处理 
}

统计答案时就照着数位\(DP\)的套路统计，不过这道题要注意前导零，比如例子:\(65536\)

如此统计还有几个问题：
\(1.\)不能直接统计\(00000-59999\)，因为像\(01xxx\)这样的答案会被判断为不合法，但是答案要求不包含前导零，所以这种情况是合法的。所以我们要枚举答案时\(1、2、3、4\)位数的情况，来消除前导\(0\)的影响
\(2.\)注意到每次逼近都是枚举到当前位置的数\(-1\)，因为这样后面的位置可以考虑所有情况，所以最后会枚举到\(65535\)而忽略\(65536\)，把边界设到\(x+1\)即\(65537\)就行了。
\(3.\)注意\(65xxx\)的答案实际上已经不合法了，我们枚举第二高位的时候会排除这种情况，但到了下一位直接默认这一位是\(5\)了，因此就不合法了。所以每次跳到下一位之前要判断这一位和前一位是否合法，不合法直接退出,\(return\)，因为后面美剧的都是\(65xxx\)，都不合法不用考虑了。
更多细节见代码

\(Code\)

#include
#include
#include
#include
#define re register
#define ll long long
using namespace std;
inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch=2) dp[i][j]+=dp[i-1][k];//把0的情况也处理 
}
ll ask(ll x)
{
    ll tmp=x,ans=0,last;
    cnt=0;
    while(tmp) {tmp/=10,cnt++;}
    int now=x/pow[cnt-1];//now表示当前考虑的最高位 
    for(re int i=cnt-1;i>=1;--i) 
     for(re int j=1;j=1,考虑不考虑都会被前缀和相减消除 
    for(re int i=1;i=1;--i)
    {
        now=x/pow[i-1];//提取最高位 
        for(re int j=0;j=2) ans+=dp[i][j];
        if(abs(now-last)

$P2657\ [SCOI2009]\ windy$数

标签：string   总结   前缀和   表示   return   开始   char   问题：   oid   

原文地址：https://www.cnblogs.com/Liuz8848/p/11832044.html