数位专题

ural1009 数位dp

1009. K-based Numbers Time limit: 0.5 second Memory limit: 64 MB Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’

【URAL】1057 Amount of Degrees 数位DP

传送门：【URAL】1057 Amount of Degrees 题目分析：将数转化成能达到的最大的01串，串上从右往左第i位为1表示该数包括B^i。代码如下： #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;typedef long long LL ;#de

【codeforces】55D. Beautiful numbers 数位DP

传送门：【codeforces】55D. Beautiful numbers 题目分析：被每一位整除则用二进制记录已经包括的数字的个数，以及对2520取模后的状态。由于对5整除当且仅当最后一个数为0或5，对2整除当且仅当最后一个数为偶数，且1~9的最小公倍数为2520，不包括2，5后的最小公倍数为252，所以除最后一层对2520取模，其余时候都对252取模即可。由于整除的状态有限，最多只有

【HDU】3709 Balanced Number 数位DP

传送门：【HDU】3709 Balanced Number 题目分析：枚举重心的位置再进行数位DP。代码如下： #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;typedef long long LL ;#pragma comment(linker, "/ST

【HDU】3652 B-number 数位DP

传送门：【HDU】3652 B-number 题目分析：记录数字对13取模后的状态。代码如下： #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i

【BZOJ】1026: [SCOI2009]windy数数位DP

传送门：【BZOJ】1026: [SCOI2009]windy数题目分析：数位DP水题。代码如下： #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,

数位DP | 组合数学 —— POJ 3252

对应POJ题目：点击打开链接 Round Numbers Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 3252 Description The cows, as you know, have no f

【HDU4507】【吉哥系列故事——恨7不成妻】【变形数位dp】

吉哥系列故事——恨7不成妻 Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2260 Accepted Submission(s): 660 Problem Description 单身! 　　依然单

【数位dp】

1. 那个lower_bound 必须都是单调的 2. 数组越界 3. memset(dp,-1,sizeof(dp));写在外面 4. 4 * 2/ 2 *2 可以直接约掉 #include <cstring>#include <stdio.h>#include <algorithm>#include <iostream>#include <cmath>#in

数位dp n内1的个数递推找规律

1061:数字统计查看提交统计提问总时间限制: 1000ms 内存限制: 10000kB 描述给出一个整数n(1<=n<=20000000),要求输出从1到n间所有数字中“1”的出现次数．例如：数字11，1到11间数字“1”的出现次数为4。（1，10，11，11出现4次，因为11有两个1，所以出现4次）输入一个整数n，(1<=n<=20000000)

HOJ13030 数位dp

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=13030 题目意思：给你A B问A -- B之间的二进制表示中1的个数，包括A B本身。规模： 1 ≤ A ≤ B ≤ 1016 数位dp，第一次深入理解数位dp的含义，总的来说，更具题目意思总结规律。我们用dp(x)表示1-x的二进制表示1的个数。那么解就等于dp

【Leetcode 2283 】判断一个数的数字计数是否等于数位的值—— 数组计数

给你一个下标从 0 开始长度为 n 的字符串 num ，它只包含数字。如果对于每个 0 <= i < n 的下标 i ，都满足数位 i 在 num 中出现了 num[i]次，那么请你返回 true ，否则返回 false 。示例 1：输入：num = "1210"输出：true解释：num[0] = '1' 。数字 0 在 num 中出现了一次。num[1] = '2' 。数

LeetCode 3153.所有数对中数位差之和：计数

【LetMeFly】3153.所有数对中数位差之和：计数力扣题目链接：https://leetcode.cn/problems/sum-of-digit-differences-of-all-pairs/ 车尔尼有一个数组 nums ，它只包含正整数，所有正整数的数位长度都相同。两个整数的数位不同指的是两个整数相同位置上不同数字的数目。请车尔尼返回 nums 中所有

3153. 所有数对中数位不同之和（24.8.30）

题目题目你有一个数组 nums ，它只包含正整数，所有正整数的数位长度都相同。两个整数的数位不同指的是两个整数相同位置上不同数字的数目。请返回 nums 中所有整数对里，数位不同之和。示例 1 输入：nums=[13,23,12] 输出：4 解释：计算过程如下: 13 和 23 的数位不同为 1。13 和 12 的数位不同为 1。23 和 12 的数位不同为 2。所以所有

LightOJ 1068 Investigation (数位dp)

http://www.lightoj.com/volume_showproblem.php?problem=1068 求出区间[A,B]内能被K整除且各位数字之和也能被K整除的数的个数。（1 ≤ A ≤ B < 231 and 0 < K < 10000）算是最简单的数位dp了，k在这里是10000，三维数组都开不开。但是想想会发现A,B最多有10位，各位数字之和不会超过90，那么当

简单的数位dp

数位dp的模板 hdu 2089 设dp[len][flag]，flag = 1表示前一位是6,否则前一位不是6. #include <stdio.h>#include <iostream>#include <map>#include <set>#include <list>#include <stack>#include <vector>#include <

hdu5208 Where is Bob 数位dp

维护四个数的上下边界条件，转移使最小值最大即可。数位dp有时只对dp赋一次-1，这时边界条件满足一定条件与后面的数是什么无关，可以直接返回，在此题中条件太苛刻，用处不大，会tle。也可以每次都赋一次-1，这时算出一个状态的值就能赋给dp，再次用到时直接返回。 #include<iostream>#include<cstdio>#include<cmath>#include<al

hdu2089--不要62（数位dp练习2）

不要62 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Description 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，

bzoj1026--SCOL2009--windy数(数位dp练习1)

windy数 Time Limit:1000MS Memory Limit:165888KB 64bit IO Format:%lld & %llu Submit Status Description windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多

lightoj 1032 - Fast Bit Calculations （数位DP）

记忆花搜索：dp[len][num][last] : 现在处理第len位，前面有num个11，并且最后一位为last。 /************************************************ Author: fisty* Created Time: 2015-08-18 20:18:09* File Name : 1032.cpp***************

BZOJ 3530 数数【AC自动机+数位dp】

[Sdoi2014]数数简单数位dp+简单AC自动机反正数位DP是队友写的 AC自动机要记录两个值，一个是是否为一个串的结束，即不合法状态，一个是前缀零的情况。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostr

计算最大数位-第13届蓝桥杯省赛Python真题精选

[导读]：超平老师的Scratch蓝桥杯真题解读系列在推出之后，受到了广大老师和家长的好评，非常感谢各位的认可和厚爱。作为回馈，超平老师计划推出《Python蓝桥杯真题解析100讲》，这是解读系列的第87讲。计算最大数位，本题是2022年4月23日举办的第13届蓝桥杯青少组Python编程省赛真题编程部分第2题，13届一共举办了两次省赛，这是第二次省赛。题目要求对于给定的正整数N，请编程计

数位统计DP——AcWing 338. 计数问题

数位统计DP 定义数位DP（Digital DP）是一种用于解决与数字的数位相关问题的动态规划算法。它将数字的每一位看作一个状态，通过转移状态来计算满足特定条件的数字个数或其他相关统计信息。运用情况统计满足特定条件的数字个数，例如在给定范围内有多少个数字满足某些数位特征。计算数字的某个数位上的特定统计信息，如出现的数字频率等。解决与数字排列、组合相关的问题。注意事项数位DP的

UVa 11361 Investigating Div-Sum Property / 数位DP

先上代码以后再说 #include <cstdio>#include <cstring>const int maxn = 110;int dp[maxn][maxn][maxn];int ok(int x, int k){if(x < 10)return x / k;int a = x;int b = 1;int l = 0;while(a){l++;a /= 10;b *= 10;

hdu 5106 Bits Problem(数位dp)

题目链接：hdu 5106 Bits Problem 题目大意：给定n和r，要求算出[0,r)之间所有n-onebit数的和。解题思路：数位dp，一个ct表示个数，dp表示和，然后就剩下普通的数位dp了。不过貌似正解是o(n)的算法，但是n才 1000，用o(n^2)的复杂度也是够的。 #include <cstdio>#include <cstring>#include <

面试4：c++（数位物联）

1.const 关健字的作用定义常量，防止变量被意外修改，增强程序的可读性和维护性。可以用于指针，声明指向常量的指针或常量指针。 2.static关健字的作用 (1)在函数内，用于修饰局部变量，使其生命周期延长到整个程序运行期间，且只初始化一次。 (2)用于修饰全局变量或函数，限制其作用域为本文件。 3.volatile关健字的作用 volatile关键字的作用：主要用