hdu5642题目链接 题意：问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上，则这个字符串为非法。否则为合法。
思路：当时以为是组合数学的题。。。推了半天公式还是还是gg… 现在学了数位dp..果然是数位dp里很简单的一种。。。 dp[i][j][k]表示长度为i,最后一个字符对应的数字为j,最后一个字符出现了k次的方案数。
阅读更多题目链接 题意：找到某区间中平衡数的个数。所谓平衡数是指，存在某个位置，值得两边的力矩相等。举个例子。。比如14326，如果把4作为中间。。那么左边=11=1 右边=31+22+62=19。。。 思路：枚举中间的pivot。。。注意如果是个位数也是平衡数（就是认为两边的力矩都是0了。。。），所以每一个位置都可能是平衡位置。。枚举的时候从1到len… 一开始我是分别记录两边的值。。非常浪费空间。。。然而发现其实没必要。。我们只关心左边是否相等。。而不关心左右的值到底是多少。。所以可以把两边的值带符号合并成一个值（pivot左边为+，pivot右边为负）。。。如果最后为0。。说明左右相等。。。
阅读更多题目链接 题意：求一个区间内所有位数字之和能被10整除的数的个数。 思路：数位dp，dfs要一个参数记录从最高位到现在的pos位置的数字之和的结果。
1 dp[i][j] 表示长度为i，和为j的方案数。 2 记得开long long ，然而我开了那么多long long 忘了dp 的long long 结果wa到死。。果然大早上不清醒吗== 3 4 5 6/* *********************************************** 7Author :111qqz 8Created Time :2016年03月16日 星期三 08时10分19秒 9File Name …
阅读更多题目链接 题意：不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ 思路：数位dp 这道题的特点是前面不允许前导0，也就是说，如果第i位前面全是0的话，这个数就变成了i位数，i就变成了最高位，而最高位没有前面的数（**如果这里不考虑不允许前导0这个因素而把前面的一个数认为成是0就错了） **最高位的数可以直接取。 还有记忆化调用以及存储的时候也要注意…只有当位数相同的时候转移才有意义。 具体的方法是dfs中多了一个prehasnonzero的bool变量，就是字面意思，判断当前位置前面的位置是够存在一个非0的值。
阅读更多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出现的个数。
阅读更多http://codeforces.com/problemset/problem/148/D
题意：盒子里有w只白老鼠，b只黑老鼠，公主和魔王轮流取（公主先），先取到白老鼠的人获胜。魔王每次取完以后，盒子中的老鼠会因为吓尿了跑掉一只，跑掉的老鼠不算任何人取的。问公主获胜的概率。
阅读更多http://codeforces.com/problemset/problem/518/D
题意：有n个人排队上一个电梯。。。在某一秒内，队首的人有p的概率上电梯，1-p的概率不动。每个人只有在队首的位置才可以上电梯（也就是每一秒内，最多只有一个人可以上电梯）。电梯无线长（也就是上了电梯就不会离开了），问在第t秒的时候，电梯上的人的个数的数学期望是多少。
思路：一开始推公式的我还是图样。这题是dp.其实也不难想。dp[i][j]表示第i秒时电梯上有j个人的概率。 当j==n的时候，也就是所以人都上了电梯以后。dp[i+1][j]+=dp[i][j],对于其他时刻 dp[i+1][j+1]+=dp[i][j] …
阅读更多http://codeforces.com/contest/611/problem/B 题意：问a到b（1E18），二进制表示中只有一个0的数有多少个。 思路：
这么大的数。。。不是有循环节就是math problems.UD:20160318讲道理还有可能是数位dp好不好。。。 我们发现可以很容易得算出1到x的二进制表示中只有一个0 的数有多少个。
阅读更多http://codeforces.com/contest/30/problem/C 题意：给出n个target在一个二维平面上。给出每个target的坐标，出现的时间，以及击中的概率。target出现之后就会瞬间消失，枪移动的单位速度为1，射击不需要时间。问能击中的target的最大期望是多少。
阅读更多http://codeforces.com/contest/327/problem/A 题意：给定一段序列，只由0,1组成。要求选一段非空区间，做翻转操作（0变1,1变0），问变完之后1最多能有多少。 思路：最后的1个个数=初始的1的个数+变换区间的0的个数-变换区间的1的个数。初始的是常数。那么我们只要找到某一个区间内，0的个数-1的个数有最大值即可。如果a[i]==0的时候令b[i]=1，否则b[i]=0,那就是经典了最大连续区间和的问题了。dp的思想o(n)可以解决。
阅读更多http://codeforces.com/contest/456/problem/C 题意：给出n(1E5)个数（1E5），每次可以选一个数a[k]并删掉a[k],a[k]-1,a[k]+1得到a[k]分，问最多能得到的分数。 思路：裸dp.f[i]表示选到数i的时候能达到的最大分数。开一个计数数组cnt[x]表示数字x出现的次数。那么显然有f[0]=0,f[1]=cnt[1],f[i(i>=2)] = max(f[i-1]，f[i-2]+f[i]*cnt[i]);答案为f[max(a[i])]，注意要开long long
阅读更多果然dp還是弱項啊啊啊啊．． 不過比最開始的完全無從下手強了不少應該．．．
至少dp狀態表示相對了．．．．轉移方程沒想出來嗚嗚嗚
官方題解：设d(i, j)d(i,j)表示前ii个数，模pp为jj的方案数，则容易得到d(0, 0)=1, d(i, j)=d(i-1, j)+sum_{j=0}^{p-1} d(i-1, (j-a[i]) mod p)d(0,0)=1,d(i,j)=d(i−1,j)+∑j=0p−1d(i−1,(j−a[i]) mod p)，很多人没1a是因为没注意|a_i| le 10^9∣ai∣≤109
阅读更多