题目链接 题意：找到某区间中平衡数的个数。所谓平衡数是指，存在某个位置，值得两边的力矩相等。举个例子。。比如14326，如果把4作为中间。。那么左边=11=1 右边=31+22+62=19。。。 思路：枚举中间的pivot。。。注意如果是个位数也是平衡数（就是认为两边的力矩都是0了。。。），所以每一个位置都可能是平衡位置。。枚举的时候从1到len... 一开始我是分别记录两边的值。。非常浪费空间。。。然而发现其实没必要。。我们只关心左边是否相等。。而不关心左右的值到底是多少。。所以可以把两边的值带符号合并成一个值（pivot左边为+，pivot右边为负）。。。如果最后为0。。说明左右相等。。。 以及。。这个值(设为sum)是递减 …

题目链接 题意：问某区间中，round number 的个数是多少。所谓round number,当且仅当一个数的二进制表示中，‘0’的个数大于等于‘1’的个数。 思路：简单数位dp..和windy数那道题类似，都是不允许前导0.。。所以在dfs中要加一维判断前面是否有非0的数。。。 /* *********************************************** Author :111qqz Created Time :2016年03月17日 星期四 16时17分07秒 File Name :code/poj/3252.cpp …

题目链接 题意：如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍； 现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。 思路;如果是求count的话毫无难度。。。和之前的题目没什么区别。。不多说了。 但是是求平方数。。。一开始我的做法是在dfs中加一个LL 的参数表示当前的和，然后每次到dfs的出口，之前统计count的时候返回的是1，表示找到了满足条件的一个数，那这回就返回平方和。。但是这样做是错的。。。具体为什么错没有想得很明白。。。大概会少算？ 然后参考了如下博客： hdu4507解题报告1 hdu4507解 …

题目链接 题意：给出n,问[1,n]中，满足包含“13”且这个数（不是各位的和）能被13整除的数的个数。 思路：依然是数位dp..不过有一个小tip。。 由于包含13的情况非常难考虑（包含一个“13”，两个“13”.....) 所以要从反面考虑，即不包含13的情况。 但是由于还有另一个条件。 做法是把能被13整除的数考虑成全集U,然后在U中做分划，一部分是含13的，另一部分是不含13的。 这样我们要求两个答案，一个是能被13整除的，另一个是能被13整除并且不含13的，相减即为题目所求。 /* *********************************************** Author :111qqz Created …

题目链接 题意：求一个区间内所有位数字之和能被10整除的数的个数。 思路：数位dp，dfs要一个参数记录从最高位到现在的pos位置的数字之和的结果。 dp[i][j] 表示长度为i，和为j的方案数。 记得开long long ，然而我开了那么多long long 忘了dp 的long long 结果wa到死。。果然大早上不清醒吗== /* *********************************************** Author :111qqz Created Time :2016年03月16日 星期三 08时10分19秒 File Name :code/hdu/4722.cpp …

题目链接 题意：不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ 思路：数位dp 这道题的特点是前面不允许前导0，也就是说，如果第i位前面全是0的话，这个数就变成了i位数，i就变成了最高位，而最高位没有前面的数（**如果这里不考虑不允许前导0这个因素而把前面的一个数认为成是0就错了） **最高位的数可以直接取。 还有记忆化调用以及存储的时候也要注意...只有当位数相同的时候转移才有意义。 具体的方法是dfs中多了一个prehasnonzero的bool变量，就是字面意思，判断当前位置前面的位置是够存在一个非0的值。 /* …

题目链接 题意:问从1到n的所有数中，有多少个数含有数字串“49” 思路：和上一道不要62很像，但是由于是要统计有49的，但是有49的情况实在太多了，正难则反，用减法定理反过来考虑，先统计出不含49的数的个数，这样就和不要62一样了，然后再用总数减。 /* *********************************************** Author :111qqz Created Time :2016年03月15日 星期二 19时32分24秒 File Name :code/hdu/3555.cpp ************************************************ */ …

题目链接 题意：问区间[n,m]中，不含数字4，也不含数字串“62”的所有数的个数。 思路：可以转化成求区间[0,x] 第一次接触数位dp,参考了这几篇博客。 不要62（数位dp）解题报告 解题报告2 解题报告3 比较重要的前提： ¨对于一个小于n的数，肯定是从高位到低位出现某一位<n的那一位。 ¨如 n = 58 n为十进制数。 ¨ x = 49 此时x的十位<n ¨ x = 51 此时x的个位<n ¨有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。 这样之前的位确定了，之后的位就不受n的限制即从00...0~99...9，可以先预处理 以及写成递归形式代码会简洁很 …

http://codeforces.com/problemset/problem/621/E 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。 但是由于b很大（1E9）,所以需要用矩阵加速。 /* *********************************************** …

http://codeforces.com/problemset/problem/148/D 题意：盒子里有w只白老鼠，b只黑老鼠，公主和魔王轮流取（公主先），先取到白老鼠的人获胜。魔王每次取完以后，盒子中的老鼠会因为吓尿了跑掉一只，跑掉的老鼠不算任何人取的。问公主获胜的概率。 思路：概率dp.. dp[i][j]表示有i只白老鼠，j只黑老鼠的时候公主获胜的概率。 转移方程 1. 公主抽到白老鼠（之后龙不必再抽） 胜率为i/(i+j)*1 2. 公主抽到黑老鼠，龙抽到黑老鼠，跳出一只黑老鼠，胜率为j/(i+j) * (j-1)/(i+j-1) * (j-2)/(i+j-2) * f[i][j-3] (j>=3) 3. …