首页 > 其他分享 >数位dp

数位dp

时间：2024-03-26 20:55:36浏览次数：29  
标签：std return int i64 limit ans dp 数位

233. 数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
class Solution:
    def countDigitOne(self, n: int) -> int:
        s=str(n)
        @cache
        def f(i:int,cnt:int,is_limit:bool)->int:
            if i==len(s):
                return cnt
            ans=0
            up=int(s[i]) if is_limit else 9
            for d in range(up+1):
                ans+=f(i+1,cnt+(d==1),is_limit and d==up)
            return ans
        return f(0,0,True)
2376. 统计特殊整数

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)

        @cache
        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
            if i == len(s):
                return int(is_num)
            ans = 0
            if not is_num:
                ans = f(i+1, mask, False, False)
            up = int(s[i]) if is_limit else 9
            for d in range(1-int(is_num), up+1):
                if mask & (1 << d) == 0:
                    ans += f(i+1, mask | (1 << d), is_limit and d == up, True)
            return ans

        return f(0, 0, True, False)
2719. 统计整数数目

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

  • num1 <= x <= num2
  • min_sum <= digit_sum(x) <= max_sum.

请你返回好整数的数目。答案可能很大，请返回答案对 10**9 + 7 取余后的结果。

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        def calc(n: str) -> int:
            @cache
            def dfs(i: int, s: int, is_limit: bool) -> int:
                if s > max_sum:
                    return 0
                if i == len(n):
                    return s >= min_sum
                ans = 0
                up = int(n[i]) if is_limit else 9
                for d in range(up+1):
                    ans += dfs(i+1, s+d, is_limit and d == up)
                return ans
            return dfs(0, 0, True)

        is_good = min_sum <= sum(map(int, num1)) <= max_sum
        ans = (calc(num2)-calc(num1)+is_good) % (10**9+7)
        return ans
788. 旋转数字

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

class Solution:
    def rotatedDigits(self, n: int) -> int:
        dif = (0, 0, 1, -1, -1, 1, 1, -1, 0, 1)
        s = str(n)

        @cache
        def dfs(i: int, hasDif: bool, is_limit: bool) -> int:
            if i == len(s):
                return hasDif
            ans = 0
            up = int(s[i]) if is_limit else 9
            for d in range(up+1):
                if dif[d] != -1:
                    ans += dfs(i+1, hasDif or dif[d], is_limit and d == up)
            return ans
        return dfs(0, False, True)
902. 最大为 N 的数字组合

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        s = str(n)

        @cache
        def dfs(i: int, is_limit: bool, is_num: bool) -> int:
            if i == len(s):
                return int(is_num)
            ans = 0
            if not is_num:
                ans += dfs(i+1, False, False)
            up = s[i] if is_limit else '9'

            for d in digits:
                if d > up:
                    break
                ans += dfs(i+1, is_limit and d == up, True)
            return ans
        return dfs(0, True, False)
面试题 17.06. 2出现的次数

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

class Solution:
    def numberOf2sInRange(self, n: int) -> int:
        s=str(n)
        @cache
        def dfs(i:int,cnt:int,is_limit:bool)->int:
            if i==len(s):
                return cnt
            ans=0
            up=int(s[i]) if is_limit else 9
            for d in range(up+1):
                ans+=dfs(i+1,cnt+(d==2),is_limit and d==up)
            return ans
        return dfs(0,0,True)
600. 不含连续1的非负整数

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1

class Solution:
    def findIntegers(self, n: int) -> int:
        s = bin(n)[2:]

        @cache
        def dfs(i: int, one: bool, is_limit: bool) -> int:
            if i == len(s):
                return 1
            ans = 0
            up = int(s[i]) if is_limit else 1
            ans += dfs(i+1, False, is_limit and 0 == up)
            if not one and up == 1:
                ans += dfs(i+1, True, is_limit)
            return ans
        return dfs(0, False, True)
E - 数E - 数

求出[1,n) 有多少个数 满足：数位之和是D的倍数，对答案取模\(10^{9}+7\)

using Z = Mint<i64>;
void solve()
{
    int D;
    std::string s;
    std::cin >> D >> s;
    int n = s.size();
    const i64 NIL = -1;
    std::vector dp(n, std::vector<std::vector<i64>>(D, std::vector<i64>(2, NIL)));

    auto dfs = [&](auto self, int i, int r, bool is_limit) -> Z
    {
        if (i == n)
        {
            return r == 0;
        }
        if (dp[i][r][is_limit] != NIL)
        {
            return dp[i][r][is_limit];
        }
        Z ans = 0;
        int up = is_limit ? int(s[i] - '0') : 9;
        for (int d = 0; d <= up; d++)
        {
            ans += self(self, i + 1, (r + d) % D, is_limit and d == up);
        }
        return dp[i][r][is_limit] = ans.v;
    };
    int cnt = 0;
    for (auto i : s)
    {
        cnt += i - '0';
    }
    bool n_ok = cnt % D == 0;
    std::cout << dfs(dfs, 0, 0, true) - n_ok - 1 << '\n';
}
D - 禁止された数字

给定范围[A,B],\(1\le A < B\le 10^{18}\),求出范围内有多少个数满足：数位中至少有一个4，或有一个6

using i64 = long long;

i64 calc(i64 num)
{
    std::string s = std::to_string(num);
    int n = s.size();
    const i64 NIL = -1;
    std::vector dp(n, std::vector<std::vector<i64>>(2, std::vector<i64>(2, NIL)));

    auto dfs = [&](auto self, int i, bool forbid, bool is_limit) -> i64
    {
        if (i == n)
        {
            return forbid;
        }
        auto &res = dp[i][forbid][is_limit];
        if (res != NIL)
        {
            return res;
        }
        i64 ans = 0;
        int up = is_limit ? s[i] - '0' : 9;
        for (int d = 0; d <= up; d++)
        {
            ans += self(self, i + 1, forbid or d == 4 or d == 9, is_limit and d == up);
        }
        return res = ans;
    };
    return dfs(dfs, 0, false, true);
}

void solve()
{
    i64 a, b;
    std::cin >> a >> b;
    std::cout << calc(b) - calc(a - 1) << '\n';
}
D - 1

求出[1,n] 的整数，其数的10进制中的1的个数之和

using i64 = long long;
i64 calc(i64 num)
{
    std::string s = std::to_string(num);
    int n = s.size();
    const i64 NIL = -1;
    std::vector dp(n, std::vector<std::vector<i64>>(n, std::vector<i64>(2, NIL)));
    auto dfs = [&](auto self, int i, i64 cnt, bool is_limit) -> i64
    {
        if (i == n)
        {
            return cnt;
        }
        auto &ans = dp[i][cnt][is_limit];
        if (ans != NIL)
        {
            return ans;
        }
        i64 res = 0;
        int up = is_limit ? s[i] - '0' : 9;
        for (int d = 0; d <= up; d++)
        {
            res += self(self, i + 1, cnt + (d == 1), is_limit and d == up);
        }
        return ans = res;
    };
    return dfs(dfs, 0, 0, true);
}
void solve()
{
    int n;
    std::cin >> n;
    std::cout << calc(n) << '\n';
}
E - Digit Sum Divisible

求出[1,n]的符合条件的整数x,x满足x%(x的数位和)==0,

using i64 = long long;

i64 calc(i64 num)
{
    std::string s = std::to_string(num);
    int n = s.size();
    i64 ans = 0, D;
    const i64 NIL = -1;
    std::vector<std::vector<std::vector<std::vector<i64>>>> dp;

    auto dfs = [&](auto self, int i, int sd, int r, bool is_limit) -> i64
    {
        if (i == n)
        {
            return sd == D and r == 0;
        }
        auto &ndp = dp[i][sd][r][is_limit];
        if (ndp != NIL)
        {
            return ndp;
        }
        i64 res = 0;
        int up = is_limit ? s[i] - '0' : 9;
        for (int d = 0; d <= up; d++)
        {
            if (sd + d > D)
            {
                continue;
            }
            res += self(self, i + 1, sd + d, (10 * r + d) % D, is_limit and d == up);
        }
        return ndp = res;
    };

    for (D = 1; D <= 14 * 9; D++)
    {
        dp.assign(n, std::vector(D + 1, std::vector(D, std::vector(2, NIL))));
        ans += dfs(dfs, 0, 0, 0, true);
    }
    return ans;
}

void solve()
{
    i64 n;
    std::cin >> n;
    std::cout << calc(n) << '\n';
}
Problem - C - Codeforces

求出区间[L,R]中有多少个数满足：其数位中有至多3个非0数位

using i64 = long long;
i64 calc(i64 num)
{
    std::string s = std::to_string(num);
    int n = s.size();
    const i64 NIL = -1;
    std::vector dp(n, std::vector(n, std::vector(2, std::vector(2, NIL))));
    auto dfs = [&](auto self, int i, int cnt, bool is_limit, bool is_num) -> i64
    {
        if (i == n)
        {
            return is_num and cnt <= 3;
        }
        auto &ndp = dp[i][cnt][is_limit][is_num];
        if (ndp != NIL)
        {
            return ndp;
        }
        i64 ans = 0;
        int up = is_limit ? s[i] - '0' : 9;
        if (not is_num)
        {
            ans = self(self, i + 1, cnt, false, false);
        }
        for (int d = 0; d <= up; d++)
        {
            if ((not is_num and d != 0) or is_num)
            {
                ans += self(self, i + 1, cnt + (d != 0), is_limit and d == up, true);
            }
        }
        return ndp = ans;
    };
    return dfs(dfs, 0, 0, true, false);
}
void solve()
{
    i64 L, R;
    std::cin >> L >> R;
    std::cout << calc(R) - calc(L - 1) << '\n';
}
No.741 AscNumber(Easy)

求出[1,\(10^{n}\)]有多少个数字满足：其数位不递减
对\(10^{9}+7\)取模

using Z = Mint<i64>;
void solve()
{
    int n;
    std::cin >> n;
    std::string s = "1" + std::string(n, '0');
    n = n + 1;
    const i64 NIL = -1;
    std::vector dp(n, std::vector(10, NIL));
    auto dfs = [&](auto self, int i, int cur, bool is_limit, bool is_asc) -> Z
    {
        if (i == n)
        {
            return is_asc;
        }
        auto &ndp = dp[i][cur];
        if (ndp != NIL)
        {
            return ndp;
        }
        Z ans = 0;
        int up = is_limit ? s[i] - '0' : 9;
        for (int d = 0; d <= up; d++)
        {
            if (d >= cur)
            {
                ans += self(self, i + 1, d, is_limit and d == up, true);
            }
        }
        return ndp = ans.v;
    };
    std::cout << dfs(dfs, 0, 0, true, true) << '\n';
}
D. Beautiful numbers

给定范围[L,R],
当且仅当正整数可以被其非零位数整除时，它才是美丽的.计算给定范围内美丽数字的数量。

多组重复贡献时，贴上限,is_limit==true的位不进行记忆化

#include <bits/stdc++.h>
#include <bits/extc++.h>
using i64 = long long;
const int N = 20;
const int M = 2520;
const i64 NIL = -1;
int id[M + 1];
void init()
{
    for (int i = 1, j = 1; i <= M; i++)
    {
        if (M % i == 0)
        {
            id[i] = j++;
        }
    }
}
std::vector<std::vector<std::vector<std::vector<i64>>>> dp;
i64 calc(i64 num)
{
    std::string s = std::to_string(num);
    std::reverse(s.begin(), s.end());
    int n = s.size();

    auto dfs = [&](auto self, int i, int cur, int r, bool is_limit) -> i64
    {
        if (i == -1)
        {
            return r % cur == 0;
        }
        auto &ndp = dp[i][id[cur]][r][is_limit];
        if (not is_limit and ndp != NIL)
        {
            return ndp;
        }
        i64 res = 0;
        int up = is_limit ? s[i] - '0' : 9;
        for (int d = 0; d <= up; d++)
        {
            int ncur = d ? cur / std::gcd(cur, d) * d : cur;
            int nr = (r * 10 + d) % M;
            res += self(self, i - 1, ncur, nr, is_limit and d == up);
        }
        if (not is_limit)
        {
            ndp = res;
        }
        return res;
    };
    return dfs(dfs, n - 1, 1, 0, true);
}
void solve()
{
    i64 L, R;
    std::cin >> L >> R;
    std::cout << calc(R) - calc(L - 1) << '\n';
    // std::cout << calc(R) << ' ' << calc(L - 1) << '\n';
}
int main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);

    init();
    dp = std::vector(N, std::vector(60, std::vector(M, std::vector(2, NIL))));

    int t;
    std::cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签：std,return,int,i64,limit,ans,dp,数位
From： https://www.cnblogs.com/FeiShi/p/18097557

相关文章

  • 高维前缀和/SOS DP 学习笔记
    JOISC2023D2T2Council注意到，钦定一个人为主席后，对于此时得票数大于\(\lfloor\frac{n}{2}\rfloor\)的议案，不管怎么选副主席，均能通过；对于此时得票数小于\(\lfloor\frac{n}{2}\rfloor\)的议案，不管怎么选副主席，均不能通过。所以需要考虑的只有此时得票数恰好等于\(\lfloo......
  • 动态规划——线性dp
    数字三角形//从上到下#include<iostream>#include<algorithm>usingnamespacestd;constintN=510,INF=1e9;intn;inta[N][N];intf[N][N];intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)for(int......
  • 使用dpkg在ubuntu上安装软件包遇到依赖包的问题
    问题在ubuntu上使用apt-get安装软件包，系统会自动安装依赖的软件包，但是使用dpkg在ubuntu上安装软件包时不会，有时会遇到下面的错误：pengdl@pengdl-HP:~/Soft$sudodpkg-ivirtualbox-7.0_7.0.14-161095~Ubuntu~focal_amd64.deb[sudo]passwordforpengdl:Selectingpreviously......
  • 换根DP学习笔记
    啊啊啊啊啊啊啊啊啊啊啊啊画图累死我了额，这不菜根快乐DP（根）吗换根DP，即换根树形DP平常树形DP指定一个根，但万一邪恶出题人让你求多个点为根的情况呢？你们可能会想：多跑几遍不就好了！不可以的，直接TLE。这有个树，B是A之后的树根（拎上去）：B成为树根后：画风突然转变但是！其实有些没变！......
  • 【DP】01背包问题与完全背包问题
    一、01背包问题有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包......
  • NCV7718CDPR2G半桥驱动器规格书PDF数据手册引脚图图片价格参数概概述
    产品概述：NCV7718是一款六角半桥驱动器，具有专为汽车和工业运动控制应用设计的保护功能。NCV7718具有独立的控制和诊断功能。该器件可在正向、反向、制动和高阻抗状态下运行。驱动器通过16位SPI接口进行控制，并且菊花链兼容规格书参数：引脚图：......
  • AT_DP
    攻略先设计一个一定保证正确性的状态，可以完全朴素甚至可以n维考虑保证正确性的情况下：合并同类状态，消除无用状态，消除无用转移。对递推式进行分类，只与当前点有关的直接处理，只与以前相关的点预处理，既与当前有关又与现在有关考虑斜率优化（有单调性用单调队列，否则二分或李超）......
  • ARM64: ARDP
    1指令语法ardp<Xd>,<lable>2指令语义1获取程序计数器PC寄存器的值；2将PC寄存器值的低12位全部取0;3将lable的值乘以4096，也就是将label左移12位；4将第2步的PC值与第3步的label值相加；5将第4步所得结果写入寄存器Xd。从上面步骤可以看出，得到的结果低12位为0，所以得到......
  • TCP/UDP/IP协议 自述
    TCP包协议格式SYN—为1表示这是连接请求或是连接接受请求，用于创建连接和使顺序号同步ACK—为1表示确认号字段有效TCP协议三次握手流程主要就是SYN和ACK字段。服务器开始属于监听状态。1、客户端发送连接请求。SYN置为1.序列号为12342、服务器收到请求。ACK置为1，确......
  • Offer必备算法15_简单多问题dp_八道力扣题（打家劫舍+买卖股票）
    目录①力扣LCR089.打家劫舍解析代码②力扣213.打家劫舍II解析代码③力扣740.删除并获得点数解析代码④力扣LCR091.粉刷房子解析代码⑤力扣309.买卖股票的最佳时机含冷冻期状态机分析解析代码⑥力扣714.买卖股票的最佳时机含手续费状态机分析解析代码⑦......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99