计数问题专题
数位统计DP——AcWing 338. 计数问题
数位统计DP 定义 数位DP（Digital DP）是一种用于解决与数字的数位相关问题的动态规划算法。它将数字的每一位看作一个状态，通过转移状态来计算满足特定条件的数字个数或其他相关统计信息。 运用情况 统计满足特定条件的数字个数，例如在给定范围内有多少个数字满足某些数位特征。计算数字的某个数位上的特定统计信息，如出现的数字频率等。解决与数字排列、组合相关的问题。 注意事项 数位DP的
UVA 11645 - Bits(数论+计数问题)
题目链接：11645 - Bits 题意：给定一个数字n，要求0-n的二进制形式下，连续11的个数。 思路：和 UVA 11038 这题类似，枚举中间，然后处理两边的情况。 不过本题最大的答案会超过longlong，要用高精度，不过借鉴http://www.cnblogs.com/TO-Asia/p/3214706.html这个人的方法，直接用两个数字来保存一个数字，这样能保
UVA 11038 - How Many O's?（计数问题）
题目链接：11038 - How Many O's? 题意：求[a.b]之间，0出现的次数。 思路：一开始一直往数位DP上去想，结果发现挺复杂的。。 把问题先转化为求0 - num的个数，在用到b的个数减去到a的个数 其实只要利用计数的乘法和加法原理，把数字对应的每一位的分成左右两边，利用乘法原理求总数，在用加法原理把所有的总数加起来就是总情况数。那么讨论一下分成两边
【数论】计数问题的几种基本方法
一、计数原理 加法原理：n个方法，每个方法有Pi种方案，那么一共方案数为P1 + P2 + P3... + Pn 乘法原理：一件事情有n个步骤，每个步骤需要pi种方案，那么一共有P1 * P2 * P3 * ... * Pn种方案。 容斥原理：集合A,B,C。|A U B U C| = |A| + |B| + |C| - |AB| - |AC| - |BC| + |ABC|。依次类推。 基
UVA 10253 - Series-Parallel Networks（数论+计数问题+递推）
题目链接：10253 - Series-Parallel Networks 白书的例题。 这题也是需要把问题进行转化，一个并联可以分为几个串联，然后串联可以分成边。 如此一来，最后叶子结点种数会是n，问题转化为去分配叶子结点，使得总和为n。 书上有两种方法，一种直接去递归，利用组合数学的方式去计算答案。 一种是推出递推式： 设dp[i][j]为一共j个
UVA 12508 - Triangles in the Grid(计数问题)
12508 - Triangles in the Grid 题目链接 题意：给定一个n∗m格子的矩阵，然后给定A，B，问能找到几个面积在A到B之间的三角形。 思路：枚举每一个子矩阵，然后求[0,A]的个数减去[0,B]的个数就是答案，然后对于每个子矩阵个数很好求为(n−r+1)∗(m−c+1)。关键在于怎么求每个子矩阵的符合个数。 想了好久，参考别人题解才想出来，分3种情况讨论：
计数问题--抽屉原理（鸽笼原理）
定理：（鸽笼原理）若有 n 只鸽子住进 m（n>m） 个鸽笼，则存在一个鸽笼至少住进[(n-1)/m]+1只鸽子,[x]表示小于等于x的最大整数。 注意：1.鸽笼原理只提供了存在性证明。 2.使用鸽笼原理，必须能够正确识别鸽子（对象）和鸽笼（某类要求的特征），并能够计算出鸽子数和鸽笼数。 例： 某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在
leetcode——用位运算来做2的幂次方和比特位计数问题
231.给定一个整数，编写一个函数来判断它是否是 2 的幂次方。 示例 1: 输入: 1 输出: true 解释: 20 = 1 示例 2: 输入: 16 输出: true 解释: 24 = 16 示例 3: 输入: 218 输出: false 思路： 可以用mod去摸运算来做，也可以用 l o g 2 log_{2} log2得到int数 但是最快捷的方法还是用位运算，因为不管是2
树与图的一些计数问题（图论学习总结部分内容）
文章目录 前言七、树与图的一些计数问题（偏数学）容斥原理知识点例题 e g 1 : eg1: eg1: 完全子图染色问题 e g 2 : eg2: eg2: D A G DAG DAG计数 生成树计数知识点例题 环计数问题练习题 前言 由于图论学习总结内容过多，全放在一篇博客过于冗长现进行拆分，本文是树与图的一些计数问题部分，其他部分地址见：图论学习总结(For XCPC
C++ 动态规划 数位统计DP 计数问题
给定两个整数 a 和 b ，求 a 和 b 之间的所有数字中 0∼9 的出现次数。 例如，a=1024，b=1032 ，则 a 和 b 之间共有 9 个数如下： 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等… 输入格式 输入包含多组测试数据。 每组测试数据占一
AcWing.338. 计数问题
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。 例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下： 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等… 输入格式 输入包含多组测试数据。 每组测试数据占一行，包含两个
![【洛谷千题详解】P1980 [NOIP2013 普及组] 计数问题](https://img-blog.csdnimg.cn/direct/11f9972df6d64c5d90a100ed57686124.png)
【洛谷千题详解】P1980 [NOIP2013 普及组] 计数问题
#include<bits/stdc++.h>using namespace std;int main(){int n,x,ans=0;cin>>n>>x;for(int i=1;i<=n;i++){int number=i;while(number){int a=number%10;number/=10;if(a==x) ans++;}}cout<<ans<<endl;return 0
信息学奥林匹克竞赛-计数问题
试计算在区间 1 到 n 的所有整数中，数字 x（0 ≤ x ≤ 9）共出现了多少次？例如，在 1 到 11 中，即在 1、2、3、4、5、6、7、8、9、10、11 中，数字 1 出现了 4 次。 输入格式： 输入文件名为 count.in。 输入共 1 行，包含 2 个整数 n、x，之间用一个空格隔开。 输出格式： 输出文件名为 count.out。 输出共 1 行，包含一个
计数问题（数位DP）
题目大意：给定一个区间，求该区间内0 ~ 9出现的次数，多次询问，以0 0结束询问 测试用例： 输入： 1 10 44 497 346 542 1199 1748 1496 1403 1004 503 1714 190 1317 854 1976 494 1001 1960 0 0 输出： 1 2 1 1 1 1 1 1 1 1 85 185 185 185 190 96 96 96 95
计数问题（数位DP）
题目大意：给定一个区间，求该区间内0 ~ 9出现的次数，多次询问，以0 0结束询问 测试用例： 输入： 1 10 44 497 346 542 1199 1748 1496 1403 1004 503 1714 190 1317 854 1976 494 1001 1960 0 0 输出： 1 2 1 1 1 1 1 1 1 1 85 185 185 185 190 96 96 96 95
POJ - 2282 - The Counting Problem - （计数问题）
题目链接：http://poj.org/problem?id=2282 题目死磕过的，感觉被磕的鼻青脸肿。。。 和题目 POJ - 3286 - How many 0's? - （统计0的个数）的思想一样，明白那道题这道题就差不多了，只是这里不单单统计0的个数。所以对于当前统计位上的值如果不为0，那么它的前面高位的组合可以为0,。 代码： #include<iostream>#in
动态规划专题复习（一）计数问题
文章目录 动态规划专题复习（一）计数问题一，计数问题1.斐波那契数列暴力递归解记忆化搜索动态规划 2.凑零钱暴力递归记忆化搜索动态规划 3.爬台阶暴力递归记忆化搜索动态规划 4.不同路径一暴力递归记忆化搜索动态规划 5.不同路径二动态规划 6.不同的二叉搜索树一暴力递归记忆化搜素动态规划 动态规划专题复习（一）计数问题 最近在复习算法，为明年的春招做准备，欢迎互关呀，共同