题目链接：URAL1057 题意：区间【X，Y】内，有多少个数可以表示成K个不同的B的幂次方之和 如：K=2，B=2，3=2^0+2^1，5=2^2+2^0等 这个题是论文上的题：算法合集之《浅谈数位类统计问题》 其实归到数位DP不是很合适，因为数学推导推完了之后就是一个组合数的问题 详细分析见论文吧，不再赘述，说说我对代码的理解 #include<map> #include<set> #include<math.h> #include<time.h> #include<iostream> #include&...

Beautiful numbers Codeforces55_D HOJ1983 注意两边的提交格式和long long；int64不一样，细节 题意：【X，Y】区间内有多少个数，该数能够整除数位中的每一位 按照数位DP模板先走起 dp【pos】【num】【mod】表示：当前已经算到了第pos位，当前数为num，各个数位的乘积为mod 然后发现，空间没法开起来。 pos开20位，num要用1到1e18 各个数位的乘积mod，肯定会是1，2，3，4，5，6，7，8，9这9个数的最小公倍数的约数 2520共有多少个约数，暴力算一下，就几十个。 所以可以用数组先暴力算出...

题目链接：HDOJ4734 题意：给定整数a，b：先按照题目意思求得F（a），然后求区间【0,b】内有多少个数不超过F（a） 刷了这么久的数位DP，对于这种模型题感觉还是在的 dp【len】【x】：数位为len，不超过j的数的总数量 求F（a）写个函数进行计算就好了 最终的要求是不超过F（a），所以每次用F（a）去减去数位DP枚举的数，如果最终不小于0，说明这个值是可以的 剩下的跟模板就没有区别了 #include<map> #include<set> #include<math.h> #include<time.h>...

题目链接：HDOJ4507 这个题，跟标准模板就有很多的不一样了，主要体现在数学的计算上面 题意：区间【L，R】内，与7数字无关的数的平方和 无关的定义是：该数不含7，不能被7整除，各个数位之和不是7的倍数 分析： 如果是统计符合某种性质的数的个数，那么很简单 不含7，在数位枚举的时候遇到7跳过就好 被7整除和数位之和是7的倍数，都是在数位枚举完了之后，记忆化的时候一个IF判断就好 就是模板 统计数的和的题都没有做过，直接上平方和，怎么做呢？ 很简单：先从和来想 之前有多少个数符合了要求，每个数位上的值是多少，先加起来 平方和呢：（a+b）^2=a^2...

题目链接：POJ3252 题意很简单：【L，R】区间中，各个数的二进制表示形式中0的个数不小于1的个数的数目 本来是可以1A的简单题，超时了无数发，来解释解释细节 看到题目中L，R的大小是2*10^9，在int范围内，超时跟long long可能也有关系 然后就是状态的分析 dp【pos】【x】【y】：当前枚举到了第pos位，0的个数有x个，1的个数有y个，符合题目意义的值有多少个 由于前导0对于题目影响，所以需要一个bool型变量zero来标记当前情况下是不是前面全都是全导0，然后呢，dfs记忆化的模板也出来了 int dfs（int pos，int x，int...

题目链接：CF258B 还是继续我的数位DP专题学习 题意：在【1，M】中选择7个数，定义数字中含有4或者7的叫做运气数，如4447有4个，可以累计 现在要求：选择第一个数的运气值要严格大于其他6个数的运气总和 分析： 第一思路：用DP预处理dp【pos】【x】：当前位为pos，运气值为x的数有多少个 但是发现这样做，有一点不好：怎么去比较严格大于这个事呢 需要这样定义：dp【pos】【x】【y】：要求最后的运气值是y！ 做过这种类似的题啊！当pos==0的时候比较x和y是否相等就好 然后在注意一个前导0的问题，因为0是符合数位DP的，但是不符合题意，所以这个...

题目链接：CF401D 题意：求将n的所有数位重新排列的所有数中，能够被m整除的数的个数 当数位DP专题做的，所以会想到记忆化来保存状态搞 n的所有数位重新排列怎么搞？记录有多少个数字就好，每个数字都得记录，就都得用一个新变量来保存 由于不能有前导0，所以构造出来会是这样： dp【pos】【a0】【a1】【a2】【a3】【a4】【a5】【a6】【a7】【a8】【a9】 代表当前的前pos位，0出现a0次……9出现a9次 然后在dfs记忆化的时候，再来两个变量zero和flag，一个判断是否都是前导0，一个判断当前最高位能填多少 考虑下空间复杂度，肯定不行 那么就得换方...

链接：HDOJ3271 题意：10进制的【A，B】区间内，在转化为BASE进制之后，各个数位的和为M的有多少个数，其中第K个数是多少 思路：转为为BASE进制和转为10进制有什么太大区别吗？ 因为BASE不超过10，所以就是在模板的calc函数里改个值就好了 求数位的和为M就是模板 其中第二问：第K个数是多少有点麻烦 首先呢，第1个数是calc（X-1）这样来计算 最大的那个数是calc（Y） 然后就是经典二分搞定 #include<map> #include<set> #include<math.h> #include&lt...

题目链接：HDOJ3967 题目：把【A，B】区间中的每个数X，分成左右两部分，如果和是K的倍数，那么算一个满足条件的数。求区间内的总数 分成左右两部分意思是说从任意一个数位断开，比如1234，可以分成1+234，也可以是12+34，还可以是123+4 如果有多种分解情况，算多种 然后就跟平衡数的思路一样了 平衡数是枚举支点，这个题就是枚举分隔的位置 如果X这个数有len位，那么枚举len-1个分界点，有一个符合就算一个 记忆化的写法就好，还是需要主要好10的次幂的打表与当前数位的位置要对应好 纠正以前理解数位DP中前导0的理解错误 在记忆化使用的时候可以不需要zer...

题目链接：HDOJ3565 题意：首先定义了一个peak number，是没有前导0的，存在某一个数位，比左右两边的数字都大的数 然后Bi-peak number，是两个peak number的数位相连 分析样例就能够得到这个题的坑点，很友善的题 样例1是只有5个数位，要分成Bi-peak number，至少要6位，abcdef，其中b>a,b>c,e>d,e>f 样例2是想要分解的话，后面那个数有前导0 样例3简单 这个题充分的体现了自己数位DP不熟练 不会根据题目，来灵活的设计DP状态和转移 dp【pos】【state】【pre】是设计...

题目链接：HDOJ3943 题意：在（P，Q】区间内，第K大的满足条件的数是多少 条件是：数位中有X个4，Y个7 分析： 有X个4，Y个7是很简单的数位dp dp【pos】【x】【y】：当前pos位，现在已经有了x个4，y个7 注意可以有个小剪枝，即x不能超过X，y不能超过Y 二分的方法与HDOJ 3271 SNIBB相同 题解在这儿呢：HDOJ3271SNIBB 注意开闭区间 二分的时候，求符合条件的解的时候，用个变量记录每次二分后，符合条件的值 分析见代码 注意2的63次方，需要long long #include<map> #i...

题意：平面上有ABCD四个点，给定坐标，线段AB上的运动速度是P，线段CD上的运动速度是Q，其他平面内的运动速度是R，距离是欧几里得距离，求A从运动到D的最小值 链接：HDOJ3400 思路：计算几何的题，每次枚举，都会涉及到eps 想法很简单，要求A到D的最小值 如果最优解需要从AB线段上过的话，那么需要找到AB上的一个点X，使得AX+XD时间最短 同理，CD上需要找到一个Y，结合点X，AX+XY+YD的函数值最优 由于不清楚单调性，所以求X的时候是需要三分的，在三分之内，需要嵌套一个三分枚举Y，求得在该个X的情况下的最优值，然后比较X1和X2，利用三分原理删除一个区间，...

被逼着写的一个题，以前觉得难度很大的东西，一旦有动力去好好学习，其实真的并没有那么难 ACM代码其实没有多少行，而且原理也就那么几句，怀着一颗向上的心，每天正能量，每天一道a+b，时间长了真的会有很大进步的 因为，时间都看得见 （废话了一波） 题目链接：POJ2823 题意：给定n，k，n个数，求每个连续的以K为区间长度的区间中的最小值和最大值 方法1：线段树！区间内的最大最小值，果断线段树搞 （不明白为啥只能用C++提交，G++会超时） 我对于这个的理解是：C++的很多实现较少，而且编译不稳定所以快（追求效率用C++提交） G++很多东西实现得更好，或者说编译原理不相同...

许久未打的CF比赛，水平不行被自己打成了一场手速赛，20分钟过了A和B之后gg，结果赛后把CDE都能补完了 这种训练难度其实是最好的，感觉自己会的，不一定能1A，不一定能写出来，祝自己省赛顺利 给个A题的链接 A题：数学题，一个n个数字的全排列，所有数字可以任意交换，但是只能交换一次，求最大值n和最小值1的最大的可能距离 要么放到第一个位置，要么放到最后一个位置，枚举即可 int n; int num[maxn]; int main(){ //input; while(scanf("%d",&n)!=EOF){ int ans=0; f...