[XXSY]数位DP专题 刷题笔记

Mistletoes · 2021-08-30 11:28:50 · 个人记录

数位DP专题

不要62

题目：

求区间[l,r]中有多少个数满足：不含4和62

题解：

ll dfs(int pos,bool limit,bool pre){
    if(!pos) return 1;
    if(!limit&&ans[pos][pre]!=-1) return ans[pos][pre];
    int tp=limit?a[pos]:9;
    ll res=0;
    for(int i=0;i<=tp;i++){
        if(i==4) continue;
        if(pre&&i==2) continue;
        res+=dfs(pos-1,limit&&(i==tp),i==6);
    }
    if(!limit) ans[pos][pre]=res;
    return res;
}

F(x)

题目：

对于具有n位数 (A_nA_{n-1}A_{n-2}...A_2A_1)的十进制数x，我们将其权值定义F(x)=\sum_{k=1}^{n}A_k\times 2^{k-1}。现在给出两个数字A和B，请计算0和B之间有多少数字，其权值不超过F(A)。

题解：

int dfs(int len,int val,bool limit){
    if(len==0) return val<=a;//a=F(A)
    if(val>a) return 0;
    if(!limit&&f[len][a-val]) return f[len][a-val];
    int sum=0;
    for(int i=0;i<=(limit?num[len]:9);i++)
        sum+=dfs(len-1,val+i*(1<<len),limit&&i==num[len]);
    if(!limit) f[len][a-val]=sum;
    return sum;
}

Bomb

题目：

给一个数字N，求1~N有多少个数字的序列包含“49”子序列。

题解：

ll dfs(int len, int is, int limit){
    if(len==0) return 1;
    if(dp[len][is]&&!limit) return dp[len][is];
    ll cnt=0;
    int p=limit?num[len]:9;
    for(int i=0;i<=p;i++){
        if(is&&i==9) continue;
        cnt+=dfs(len-1,i==4,i==p&&limit);
    }
    if(!limit) dp[len][is]=cnt;
    return cnt;
}

Round Numbers

题目：

如果一个正整数N的二进制表示中，0的个数大于或等于1的个数，那么N就被称为”round number” 。求在一个给出的闭区间[l,r]中有多少个round numbers。

题解：

把l,r转成二进制，然后跑数位dp

开一个五维数组记忆化：f[d][z][o][q][e]。 其中d,z,o,q,e分别表示：当前搜到第d位，有z个0，o个1，q=0,1 表示前面是否全为0（是的话不计0的个数），e=0,1 表示是否已严格小于给定上限。

int dfs(int d,int z,int o,int q,int e){
    if(!d) return z>=o;
    if(f[d][z][o][q][e]!=-1)
        return f[d][z][o][q][e];
    if(a[d]){
        f[d][z][o][q][e]=dfs(d-1,z,o+1,1,e);
        f[d][z][o][q][e]+=dfs(d-1,z+q,o,q,1);
    }
    else{
        f[d][z][o][q][e]=dfs(d-1,z+q,o,q,e);
        if(e) f[d][z][o][q][e]+=dfs(d-1,z,o+1,1,e);
    }
    return f[d][z][o][q][e];
}

吉哥系列故事——恨7不成妻

题目：

如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——

1. 整数中某一位是7；
2. 整数的每一位加起来的和是7的整数倍；
3. 这个整数是7的整数倍；

现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。

题解：

现有一个n位十进制数\overline{A_nA_{n-1}...A_{pos}XXX...X}（第n位到第pos位上的数已经确定为A_n,A_{n-1},...,A_{pos}，其余位置的数还未确定）

设Y=\overline{A_nA_{n-1}...A_{pos}000...0}，那么(\overline{A_nA_{n-1}...A_{pos}XXX...X})^2=(Y+\overline{XXX...X})^2=Y^2+(\overline{XXX...X})^2+2Y\overline{XXX...X}

那么数位dp时要开三个记忆化数组，分别维护 和7无关的数字的个数、和7无关的数字的和、和7无关的数字的平方和

B_number

题目：

若一个非负整数的十进制形式包含子串“13”，且是13的倍数，则该数为B数。对给定的n，求1~n中有几个B数。

题解：

数位dp裸题

[SCOI2009]windy数

题目：