算法竞赛备赛进阶之数位DP训练

数位DP的思想就是对每一位进行DP，计算时记忆化每一位可以有的状态，其作用是减少运算时间，避免重复计算。

数位DP是一种计数用的DP，一般就是要统计一个区间[A,B]内满足一些条件数的个数。

以1e9甚至1e18、1e100的问题为例，因为在统计情况下有很多重复的计算，数位DP实现了相同状态只计算一次，从而大幅减少运算时间。

数位DP：

技巧1：[X, Y] => f(Y) - f(X-1)

技巧2：用树进行排列

1.度的数量

1081

求给定区间[X, Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。

例如。设X=15，Y=20，K=2，B=2，择优且仅有下列三个数满足题意：

17 = 24 + 20

18 = 24 + 21

20 = 24 + 22

输入格式

第一行包含两个整数X和Y，接下来两行包含整数K和B

#include<iostream>
#include<algorithm>
#include<vector>
​
using namespace std;
​
const int N = 35;
​
int K, B;
int f[N][N];
​
void init()
{
    for(int i = 0;i < N; i++)
        for(int j = 0;j <= N; j++)
            if(!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
​
int dp(int n)
{
    if(!n) return 0;
    
    vector<int> nums;
    while(n)
    {
        nums.push_back(n % B);
        n /= B;
    }
    
    int res = 0;
    int last = 0;
    
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        if(x)//求左边的分支
        {
            res += f[i][K - last];
            if(x > 1)
            {
                if(K - last - 1 >= 0) res += f[i][K - last - 1];
                break;
            }
            else 
            {
                last++;
                if(last > K) break;
            }
        }
        if(!i && last == K) res++; // 最右侧分支上的方案
    }
    
    return res;
}
​
int main()
{
    init();
    
    int l, r;
    cin >> l >> r >> K >> B;
    
    cout << dp(r) - dp(r - 1) << endl;
    return 0;
}

2.数字游戏

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈现非下降关系，如123，446

现在大家决定玩一个游戏，指定一个整数闭区间[a, b]，问这个区间内有多少个不降数。

动态规划

  1. 状态表示

    1. 集合：所有最高位是j，且一共有i位的不降数的集合

    2. 属性：数量

  2. 状态计算

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
​
using namespace std;
​
const int N = 40;
​
int f[N][N]; // f[i][j]表示一共有i位，且最高位填j的数的个数
​
void init()
{
    for(int i = 0;i <= 9; i++) f[1][i] = 1;
    
    for(int i = 2;i < N; i++)
        for(int j = 0;j <= 9; j++)
            for(int k = j;k <= 9; k++)
                f[i][j] += f[i - 1][k];
}
​
int dp(int n)
{
    if(!n) return 1;
    
    vector<int> nums;
    while(n)
    {
        nums.push_back(n % 10);
        n /= 10;
    }
    
    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = last;j < x; j++)
            res += f[i + 1][j];
        
        if(last > x)
            break;
        last = x;
        
        if(!i) res++;
    }
    
    return res;
}
​
int main()
{
    void init();
    
    int l, r;
    while(scanf("%d%d", &l, &r))
    {
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;
}

3.Windy数

1083.Windy定义了一种Windy数：不包含前导零且相邻两个数字之差至少为2的正整数被称为Windy数。

Windy想知道，在A和B之间，包括A和B，总共有多少个Windy数？

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
​
using namespace std;
​
const int N = 11;
​
int f[N][10];
​
void init()
{
    for(int i = 0;i <= 9; i++) f[1][i] = 1;
    
    for(int i = 2;i < N; i++)
        for(int j = 0;j <= 9; j++)
            for(int k = 0;k <= 9; k++)
                if(abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}
​
int dp(int n)
{
    if(!n) return 0;
    
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int last = -2;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = 0;j < x; j++)
            if(abs(j - last) >= 2)
                res += f[i + 1][j];
        
        if(abs(x - last) >= 2) last = x;
        else break;
        
        if(!i) res++;
    }
    
    // 特殊枚举有前导零
    for(int i = 1;i < nums.size(); i++)
        for(int j = 1;j <= 9;+)
            res += f[i][j];
    
    return res;
}
​
int main()
{
    init();
    
    int l, r;
    cin >> l >> r;
    
    cout << dp(r) - dp(l - 1) << endl;
    
    return 0;
}

4.数字游戏II

1084.由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和mod N 为0

现在大家又要玩游戏了，指定一个整数闭区间[a, b]，问这个区间内有多少个取模数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
​
using namespace std;
​
const int N = 11, M = 110;
​
int P;
int f[N][10][M];
​
int mod(int x, int y)
{
    return (x % y + y) % y;
}
​
void init()
{
    memset(f, 0, sizeof(f));
    
    for(int i = 0;i <= 9; i++) f[1][i][i % P]++;
    
    for(int i = 2;i < N; i++)
        for(int j = 0;j <= 9; j++)
            for(int k = 0;k < N; k++)
                for(int x = 0;x <= 9; x++)
                    f[i][j][k] += f[i - 1][x][mod(k - j, P)];
}
​
int dp(int n)
{
    if(!n) return 1;
    
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = 0;j < x; j++)
            res += f[i + 1][j][mod(-last, P)];
        
        last += x;
        
        if(!i && last % P == 0) res++;
    }
    
    return res;
}
​
int main()
{
    int l, r;
    while(cin >> l >> r >> P)
    {
        init();
        
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;
}

5.不要62

1085.杭州人称那些傻乎乎黏兮兮的人为62。

杭州交通管理局经常会扩充一些的士车牌照。附近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有4或62的号码。如：62315，73418，88914都属于不吉利号码。但是，61152虽然含有6和2，但不是逐号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照号区号[n, m]，推断出交管局今后又要实际上给多少辆的士车上牌照了。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
​
using namespace std;
​
const int N = 9;
​
int f[N][10];
​
void init()
{
    for(int i = 0;i <= 9; i++)
        if(i != 4)
            f[1][i] = 1;
    
    for(int i = 2;i < N; i++)
        for(int j = 0;j <= 9; j++)
        {
            if(j == 4) continue;
            for(int k = 0;k <= 9; k++)
            {
                if(k == 4 || j == 6 && k == 2)
                    continue;
                f[i][j] += f[i - 1][k];
            }
        }
}
​
int dp(int n)
{
    if(!n) return 1;
    
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = 0;j < x; j++)
        {
            if(j == 4 || last == 6 && j == 2) continue;
            res += f[i + 1][j];
        }
        
        if(x == 4 || last == 6 && x == 2) break;
        last = x;
        
        if(!i) res++;
    }
    
    return res;
}
​
int main()
{
    init();
    
    int l, r;
    while(cin >> l >> r, l || r)
    {
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;
}

6.恨7不成妻

1086.DS级码农吉哥依然单身！ 所以，他生平最恨情人节，不管是214还是77，他都讨厌！

吉哥观察了214和77这两个数，发现： 　　2+1+4=7 　　7+7=72 　　77=711 最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！

什么样的数和7有关呢？

如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；

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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
​
using namespace std;
​
typedef long long LL;
​
const int N = 20, P = 1e9 + 7;
​
struct F
{
    int s0, s1, s2;
}f[N][10][7][7];
​
int power7[N], power9[N];
​
int mod(LL x, int y)
{
    return (x % y + y) % y;
}
​
void init()
{
    for(int i = 0;i <= 9; i++)
    {
        if(i == 7) continue;
        auto &v = f[1][i][i % 7][i % 7];
        v.s0++;
        v.s1 += i;
        v.s2 += i * i;
    }
    
    LL power = 10;
    for(int i = 2;i < N; i++, power *= 10)
        for(int j = 0;j < N; j++)
        {
            if(j == 7) continue;
            for(int a = 0;a < 7; a++)
                for(int b = 0;b < 7; b++)
                    for(int k = 0;k <= 9; k++)
                    {
                        if(k == 7) continue;
                        auto &v1 = f[i][j][a][b], &v2 = f[i - 1][k][mod(a - j * (power % 7), 7)][mod(b - j, 7)];
                        v1.s0 = (v1.s0 + v2.s0) % P;
                        v1.s1 = (v1.s1 + j * (power % P) * v2.s0 + v2.s1) % P; 
                        v1.s2 = (v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0) % P + 2 * j * (power % P) % P * v2.s1 % P + v2.s2) % P;
                    }
        }
    
    power7[0] = power9[0] = 1;
    for(int i = 1;i < N; i++)
    {
        power7[i] = power7[i - 1] * 10 % 7;
        power9[i] = power9[i - 1] * 10 % P;
    }
}
​
F get(int i, int j, int a, int b)
{
    int s0 = 0, s1 = 0, s2 = 0;
    for(int x = 0;x < 7; x++)
        for(int y = 0;y < 7; y++)
        {
            if(x == a || y == b) continue;
            auto v = f[i][j][x][y];
            s0 = (s0 + v.s0) % P;
            s1 = (s1 + v.s1) % P;
            s2 = (s2 + v.s2) % P;
        }
    return {s0, s1, s2};
}
​
int dp(LL n)
{
    if(!n) return 0;
    
    LL backup_n = n % P;
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    LL last_a = 0, last_b = 0;
    for(int i = nums.size() - 1;i >= 0; i--)
    {
        int x = nums[i];
        for(int j = 0;j < x; j++)
        {
            if(j == 7) continue;
            int a = mod(-last_a % 7 * power7[i + 1], 7);
            int b = mod(-last_b, 7);
            
            auto v = get(i + 1, j, a, b);
            res = (res + (last_a % P) * (last_a * P) % P * power9[i + 1] % P * power9[i + 1] % P * v.s0 % P + 2 (last_a % P) % P * power9[i + 1] % P * v.s1 % P + v.s2) % P;
        }
        
        if( x == 7) break;
        last_a = last_a * 10 + x;
        last_b += x;
        
        if(!i && last_a % 7 && last_b % 7) res += (res + backup_n * backup_n) % P;
    }
    
    return res;
}
​
int main()
{
    init();
    
    int T;
    cin >> T;
    while(T--)
    {
        int l, r;
        cin >> l >> r;
        cout << mod(dp(r) - dp(l - 1), P) << endl;
    }
    
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/325511.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

宏集案例 | 楼宇管理新智慧：Panorama SCADA楼宇管理系统应用实例

宏集案例 | 楼宇管理新智慧：Panorama SCADA楼宇管理系统应用实例

来源&#xff1a;宏集科技 工业物联网 宏集案例 | 楼宇管理新智慧&#xff1a;Panorama SCADA楼宇管理系统应用实例 原文链接&#xff1a;https://mp.weixin.qq.com/s/ikPOXHCCNJh5Zlgu7wKADw 欢迎关注虹科&#xff0c;为您提供最新资讯&#xff01; #数据采集与监控 #BMS #…
阅读更多...
【正点原子】STM32电机应用控制学习笔记——8.FOC简介

【正点原子】STM32电机应用控制学习笔记——8.FOC简介

FOC是适用于无刷电机的&#xff0c;而像有刷电机&#xff0c;舵机&#xff0c;步进电机是不适用FOC的。FOC是电机应用控制难度最大的部分了。 一.FOC简介&#xff08;了解&#xff09; 1.介绍 FOC&#xff08;Filed Oriented Control&#xff09;即磁场定向控制&#xff0c;…
阅读更多...
亚马逊鲲鹏系统：全自动多账号下单，打造真实浏览轨迹

亚马逊鲲鹏系统：全自动多账号下单，打造真实浏览轨迹

亚马逊鲲鹏系统是一款卓越的软件&#xff0c;其独特的功能让用户可以轻松设置多个账号同时进行自动下单&#xff0c;极大地提高了购物效率。操作流程简单明了&#xff0c;用户只需事先设置关键词及ASIN进行货比三家&#xff0c;为用户筛选最优的产品。随后&#xff0c;软件将模…
阅读更多...
cesium设置近地天空盒 天空会倾斜

cesium设置近地天空盒 天空会倾斜

上篇文章讲解了如何设置近地天空盒&#xff0c;效果出来了还是发现天空是斜的 https://blog.csdn.net/m0_63701303/article/details/135618244 效果&#xff1a; 这里需要修改Cesium.skyBox的代码&#xff0c;代码如下直接全部复制组件内调用即可 skybox_nearground.js&…
阅读更多...
福州真兰水表有限公司精益六西格玛项目总结发布会：推动质量改进的成功案例展示

福州真兰水表有限公司精益六西格玛项目总结发布会：推动质量改进的成功案例展示

2024年1月3日&#xff0c;福州真兰水表有限公司2023年度DMAIC项目总结发布会如期举行。ZENNER真兰集团中国区总裁杨燕明先生&#xff0c;张驰咨询公司精益六西格玛黑带大师朱成朝老师&#xff0c;福州真兰水表有限公司副总经理杨岚琴女士&#xff0c;以及生产经理&#xff08;倡…
阅读更多...
一些平时很少用，但关键时刻很有用的华为手机功能

一些平时很少用，但关键时刻很有用的华为手机功能

天灾&#xff0c;自古以来就是威不可知亦不可测的东西&#xff0c;但大自然中的很多意外&#xff0c;其实可以做到有迹可循。 地震预警功能 前段时间频繁地震&#xff0c;一个月内先是积石山&#xff0c;而后是日本能登。 这时候&#xff0c;手机上的地震预警功能就是能够帮…
阅读更多...
复旦、交大、清华等公布2023届本科生毕业数据

复旦、交大、清华等公布2023届本科生毕业数据

近日多所高校发布《2022-2023学年本科教学质量报告》&#xff0c;包含各高校本科毕业生就业升学情况&#xff0c;一起来看看吧&#xff5e; 01 清华大学 清华大学推免率超60% 据报告显示&#xff0c;2023年清华大学本科毕业生总数 3609 人&#xff0c;授予学士学位3519 人。应…
阅读更多...
什么样的耳机适合游泳？游泳耳机对人体有危害吗？

什么样的耳机适合游泳？游泳耳机对人体有危害吗？

游泳是一项深受大家喜爱的运动&#xff0c;不仅可以锻炼身体&#xff0c;还能让我们享受到水中的乐趣。然而&#xff0c;对于喜欢在水中听音乐的人来说&#xff0c;选择一款适合游泳的耳机就显得尤为重要了。 游泳耳机是一种专为水上运动设计的防水耳机&#xff0c;可以在游泳、…
阅读更多...
48-DOM

48-DOM

1.DOM基础 Document Object Module，文档对象模型，window对象，document文档，都可以获取和操作 1)文档节点 2)属性节点（标签内的属性href，src） 3)文本节点（标签内的文字） 4)注释节点 5)元素节点（标签） 2.获取元素节点 2.1通过标签名获取 <p>1</p><…
阅读更多...
Apache StringUtils：Java字符串处理工具类

Apache StringUtils：Java字符串处理工具类

简介 在我们的代码中经常需要对字符串判空&#xff0c;截取字符串、转换大小写、分隔字符串、比较字符串、去掉多余空格、拼接字符串、使用正则表达式等等。如果只用 String 类提供的那些方法&#xff0c;我们需要手写大量的额外代码&#xff0c;不然容易出现各种异常。现在有…
阅读更多...
chatgpt实用技巧之二反问式提示

chatgpt实用技巧之二反问式提示

大家好&#xff0c;今天跟大家讲实用gpt的小技巧二、反问式提示 有时候不知道怎么给 GPT 提示词&#xff0c;这时候&#xff0c;就可以反问 GPT 如何更好地给提示词。如图片所示 更详细内容可以看下这篇&#xff1a; 按照 GPT 给出的&#xff1a;故事设定角色故事发展主题结局…
阅读更多...
git提交文本或者word到git教程，git创建仓库时候自带

git提交文本或者word到git教程，git创建仓库时候自带

简易的命令行入门教程: Git 全局设置: git config --global user.name “XX” git config --global user.email “XXXqq.com” 创建 git 仓库: mkdir test cd test git init touch README.md git add README.md git commit -m “first commit” git remote add origin https:…
阅读更多...
Verilog语法——5.测试文件

Verilog语法——5.测试文件

参考资料 【明德扬_verilog零基础入门语法HDL仿真快速掌握-手把手教你写FPGA/ASIC代码设计流程中的应用】 5. 测试文件 5.1 认识测试文件&#xff08;testbench&#xff09; testbench是一种验证的手段。首先&#xff0c;任何设计都是会有输入输出的。 但是在软环境中没有激励…
阅读更多...
50天精通Golang（第18天）

50天精通Golang（第18天）

web开发介绍、iris框架安装、HTTP请求和返回、Iris路由处理 一 Web项目开发介绍及实战项目介绍 1.1 引言 本系列课程我们将学些Golang语言中的Web开发框架Iris的相关知识和用法。通过本系列视频课程&#xff0c;大家能够从零到一经历一个完整项目的开发&#xff0c;并在课程…
阅读更多...
壹基金“安全家园”项目瑞金市城北社区志愿者救援队成立

壹基金“安全家园”项目瑞金市城北社区志愿者救援队成立

项目介绍&#xff1a;阿里巴巴公益&壹基金安全家园项目 -社区志愿者救援队专项行动是一个以社区为本的防灾减灾公益项目。据介绍&#xff0c;该项目通过推动社区建立自己的志愿者救援队伍&#xff0c;为队伍“配物资”“办培训”&#xff0c;并协助他们动员居民参与“家庭—…
阅读更多...
宝宝洗衣机买几公斤？婴儿专用洗衣机测评

宝宝洗衣机买几公斤？婴儿专用洗衣机测评

由于幼龄时期的宝宝的皮肤比较娇嫩&#xff0c;很容易受到伤害。所以小宝宝的衣服一般都是棉质的&#xff0c;很柔软&#xff0c;很亲肤的&#xff0c;为的就是保护宝贝们娇嫩的肌肤。而宝宝们在日常中更换衣物会相对频繁&#xff0c;换的衣物也必须及时清洗晾晒&#xff0c;以…
阅读更多...
1-数组-有效的数独

1-数组-有效的数独

这是数组的第一题&#xff0c;从现在开始开启数组篇章。力扣链接。 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的…
阅读更多...
锐意进取，蓬勃发展｜爱基百客2023全景图

锐意进取，蓬勃发展｜爱基百客2023全景图

岁序更迭&#xff0c;2023年已悄然离去。对我们来说&#xff0c;这是充满挑战与机遇的一年。爱基百客作为一家专注于测序服务的公司&#xff0c;我们在这一年里经历了许多挑战&#xff0c;也取得了令人鼓舞的成绩。前面我们盘点了表观产品和单细胞产品&#xff0c;今天再邀您回…
阅读更多...
.Net 8.0 Web API Controllers 添加到 windows 服务

.Net 8.0 Web API Controllers 添加到 windows 服务

示例源码下载&#xff1a;https://download.csdn.net/download/hefeng_aspnet/88747022 创建 Windows 服务的方法之一是从工作线程服务模板开始。 但是&#xff0c;如果您希望能够让它托管 API 控制器&#xff08;也许是为了查看它正在运行的进程的状态&#xff09;&#xff0…
阅读更多...
企业知识库搭建全流程，中小型企业必看

企业知识库搭建全流程，中小型企业必看

知识库是企业知识管理和信息查询的重要平台&#xff0c;对企业效率提升&#xff0c;业务流程规范和企业文化建设有着重要的影响。那么&#xff0c;如何为企业搭建一个合适&#xff0c;高效&#xff0c;易用的知识库呢&#xff1f;接下来就为中小型企业详解企业知识库搭建全流程…
阅读更多...
最新文章

Copyright @ 2022~2023