DP

题目链接 题意：将一个10进制数x按照2进制展开后得到的值设为f(x)…现在给出a,b（10^9）问【0，b】中满足f[x]<=f[a]的数的个数。 思路：先算出f[a]，然后我们发现f(x)最大也就10*2^10=10240，数组可以存下，搞之。和上一道题类似，我们不关心两个f函数的值具体是多少，只关心它们的相对大小情况，所以还是可以合并成一个变量。然而我用两个变量为什么错了，不懂==

hdu5642题目链接 题意：问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上，则这个字符串为非法。否则为合法。

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

题目链接 题意：问某区间中，round number 的个数是多少。所谓round number，当且仅当一个数的二进制表示中，‘0’的个数大于等于‘1’的个数。 思路：简单数位dp..和windy数那道题类似，都是不允许前导0.。。所以在dfs中要加一维判断前面是否有非0的数。。。

题目链接 题意：如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；

题目链接 题意：给出n，问[1,n]中，满足包含“13”且这个数（不是各位的和）能被13整除的数的个数。 思路：依然是数位dp..不过有一个小tip。。

题目链接 题意：求一个区间内所有位数字之和能被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 :code/hdu/4722.cpp 10************************************************ */ 11 12#include <cstdio> 13#include <cstring> 14#include <iostream> 15#include <algorithm> 16#include <vector> 17#include <queue> 18#include <set> 19#include <map> 20#include <string> 21#include <cmath> 22#include <cstdlib> 23#include <ctime> 24#define fst first 25#define sec second 26#define lson l,m,rt<<1 27#define rson m+1,r,rt<<1|1 28#define ms(a,x) memset(a,x,sizeof(a)) 29typedef long long LL; 30#define pi pair < int ,int > 31#define MP make_pair 32 33using namespace std; 34const double eps = 1E-8; 35const int dx4[4]={1,0,0,-1}; 36const int dy4[4]={0,-1,1,0}; 37const int inf = 0x3f3f3f3f; 38LL l,r; 39int digit[30]; 40LL dp[30][15]; //dp 数组忘记开long long ,wa到死。。。。。。。。。日了哈士奇。 41LL dfs ( int pos,int sum,bool limit) 42{ 43 if (pos==0) 44 { 45 if (sum==0) return 1; 46 else return 0; 47 } 48 if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum]; 49 50 int mx = limit?digit[pos]:9; 51 52 LL res = 0 ; 53 for ( int i = 0 ; i <= mx; i ++) 54 { 55 res+=dfs(pos-1,(sum+i),limit&&i==mx); 56 } 57 58 if (!limit) dp[pos][sum] = res; 59 60 return res; 61 62} 63LL solve ( LL n) 64{ 65// if (n==0) return 1; 66 // if (n<=9) return 0; 67 if (n<0) return 0; 68 ms(digit,0); 69 int len = 0 ; 70 while (n) 71 { 72 digit[++len] = n % 10; 73 n /= 10; 74 } 75 76 return dfs(len,0,true); 77} 78int main() 79{ 80 #ifndef ONLINE_JUDGE 81 freopen("code/in.txt","r",stdin); 82 #endif 83// ios::sync_with_stdio(false); 84 int T; 85 cin>>T; 86 ms(dp,-1); 87 int cas = 0 ; 88 while (T--) 89 { 90 scanf("%lld %lld",&l,&r); 91 LL ans = solve (r)-solve(l-1); 92 93 printf("Case #%d: %lld\n",++cas,ans); 94 } 95 96 #ifndef ONLINE_JUDGE 97 fclose(stdin); 98 #endif 99 return 0; 100}

题目链接 题意：不含前导零且相邻两个数字之差至少为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一样了，然后再用总数减。

题目链接 题意：问区间[n,m]中，不含数字4，也不含数字串“62”的所有数的个数。

http://codeforces.com/problemset/problem/621/E # 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。

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]p,dp[i+1][j]+=dp[i][j](1-p). 初始化dp[0][0]=1，即0时刻电梯上有0个人的概率为1. # 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月02日 星期二 15时57分06秒 4File Name :code/cf/518D.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E3+7; 34int n,t; 35double p; 36double dp[N][N]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 ms(dp,0); 43 dp[0][0] = 1; 44 cin>>n>>p>>t; 45 for ( int i = 0 ; i <= t ; i++) 46 { 47 for ( int j = 0 ; j <= n ; j++) 48 { 49 if (j==n) 50 { 51 dp[i+1][j]+=dp[i][j]; 52 } 53 else 54 { 55 dp[i+1][j+1]+=dp[i][j]*p; 56 dp[i+1][j]+=dp[i][j]*(1-p); 57 } 58 } 59 } 60 double ans = 0 ; 61 for ( int j = 1 ; j <= n ; j++) 62 ans +=j*dp[t][j]; 63 64 printf("%.12f\n",ans); 65 66 #ifndef ONLINE_JUDGE 67 fclose(stdin); 68 #endif 69 return 0; 70}

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

M - Bounty hunter **Time Limit:**5000MS **Memory Limit:**65536KB 64bit IO Format:%lld & %llu Submit Status Description Bounty hunter is a hero who always moves along cities to earn money by his power. One day he decides to N cities one by one

果然dp還是弱項啊啊啊啊．． 不過比最開始的完全無從下手強了不少應該．．．