题意：

You are given four integers A , B , C , D , there are many different (a,b,c,d) satisfy a+c>b+d && a+d≥b+c && 0≤a≤A && 0≤b≤B && 0≤c≤C && 0≤d≤D ?

做法：

可以将四个数都拆成2进制，用记忆化搜索来统计。记w1=a+c-b-d,w2=a+d-b-c,如果搜的过程中w1大于2其实可以把它变成2，对答案不影响，如果w1小于2则直接剪枝。w2也同理。

（比赛的时候完全没想到数位dp，看了huanzhizun的博客才会做）I good vegetable！a ！

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=64,mo=1e9+7;
ll A,B,C,D;
int a[N],b[N],c[N],d[N];
int f[N][2][2][2][2][5][5];
void add(int &x,int y)
{
	x=(x+y)%mo;
}
void cg(ll x,int *a)
{
	for (int i=0;i<N;i++) a[i]=0;
	int cnt=0;
	while(x) a[++cnt]=x%2,x/=2;
}
int dfs(int pos,bool u1,bool u2,bool u3,bool u4,int w1,int w2)
{
	if (pos==0) return w1>0&&w2>=0;
	int ret=f[pos][u1][u2][u3][u4][w1+2][w2+2];
	if (ret!=-1) return ret;
	ret=0;

	int d1=1,d2=1,d3=1,d4=1;
	if (u1) d1=a[pos];
	if (u2) d2=b[pos];
	if (u3) d3=c[pos];
	if (u4) d4=d[pos];

	for (int i1=0;i1<=d1;i1++)
	for (int i2=0;i2<=d2;i2++)
	for (int i3=0;i3<=d3;i3++)
	for (int i4=0;i4<=d4;i4++)
	{
		int ww1=w1*2+i1+i3-i2-i4;
		int ww2=w2*2+i1+i4-i2-i3;
		if (ww1>2) ww1=2;
		if (ww2>2) ww2=2;
		if (ww1<-2) continue;
		if (ww2<-2) continue;

		bool uu1=u1,uu2=u2,uu3=u3,uu4=u4;
		if (i1<a[pos]) uu1=0;
		if (i2<b[pos]) uu2=0;
		if (i3<c[pos]) uu3=0;
		if (i4<d[pos]) uu4=0;

		add(ret,dfs(pos-1,uu1,uu2,uu3,uu4,ww1,ww2));
	}
	return f[pos][u1][u2][u3][u4][w1+2][w2+2]=ret;
}
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
		cg(A,a); cg(B,b); cg(C,c); cg(D,d);
		memset(f,-1,sizeof(f));
		printf("%d\n",dfs(63,1,1,1,1,0,0));
	}
}

题意：

你有编号为L到R的钞票，钞票的价值就是它的编号的各个位数字之和（比如编号218的价值就是11）。现在有很多人排着队，你要从编号为L的钞票开始一直给同一个人，给完编号x的钞票再给编号x+1的钞票，直到他手上的价值>=k，换下一个人继续给。问最多能给多少个人使他们手上的价值都>=k。

做法：

先考虑按位暴搜，dfs到n+1的时候其实相当于枚举了一个x（L<=x<=R）。这时候需要知道这个x前面已经累加了多少价值，然后把这个x和之前累加起来的价值合并一下。最后退出递归的时候其实就已经把所有的x从L到R都枚举了一遍，并且返回了合并的结果。

最后记忆化一下复杂度就完美了。

讲不清啊，还是看代码吧

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
char sl[30],sr[30];
int n,k;
struct P
{
	ll num,left;
	P()
	{
		num=left=-1;
	}
	P(ll x,ll y)
	{
		num=x; left=y;
	}
	void operator +=(const P &t)
	{
		num+=t.num;
		left+=t.left;
		num+=left/k;
		left%=k;
	}
}f[20][2][2][170][1005];
P dfs(int pos,bool dn,bool up,int dg,int lft) //dg表示枚举到这一位的数字和，lft表示当前还不足k的积累的价值
{
	if (pos>n)
	{
		if ((lft+dg>=k)) return P(1,0);  // 加上它满k了，多余的就没用了
		return P(0,lft+dg);   //加上它不满k，继续积累
	}
	P ret=f[pos][dn][up][dg][lft];
	if (ret.num!=-1) return ret;
	ret=P(0,lft);
	for (int i=0;i<=9;i++)
	{
		if (dn&&i<sl[pos]-'0') continue;
		if (up&&i>sr[pos]-'0') continue;
		bool ddn=dn; if (i>sl[pos]-'0') ddn=0;
		bool uup=up; if (i<sr[pos]-'0') uup=0;
		int ddg=dg+i;
		P tmp=dfs(pos+1,ddn,uup,ddg,ret.left);  //把ret的剩余部分传递到后面那些数
		ret.left=0;  //ret的剩余部分已经传递了，就要清零
		ret+=tmp;
	}
	return f[pos][dn][up][dg][lft]=ret;
}
int main()
{
	scanf("%s%s%lld",sl+1,sr+1,&k);
	n=strlen(sr+1);
	int m=strlen(sl+1);
	for (int i=m;i>=1;i--) sl[i+(n-m)]=sl[i];
	for (int i=1;i<=n-m;i++) sl[i]='0';   //把数字弄成相同长度，前面补零
	printf("%lld\n",dfs(1,1,1,0,0).num);
}
//http://paste.ubuntu.com/18608740/    原始版本

题意：问1到n（1<=n<=10^8）所有的数，总共有多少个0出现。

做法：

很明显的数位dp

数位dp的题目我发现都可以用暴搜+记忆话过掉，而且写起来超级方便。赛场上第一个AC这道题。

暴搜是这么写的

#include<cstdio>
#include<cstring>
using namespace std;
char s[100];
int a[100];
int n;
long long get(int pos,bool up,bool zr,int now)
{
	if (pos>n) return now;
	long long ret=0;
	for (int i=0;i<=9;i++)
	{
		if (up&&i>a[pos]) continue;
		bool uup=up;
		if (i<a[pos]) uup=0;
		bool zzr=zr;
		if (i!=0) zzr=0;
		int nnow=now;
		if (i==0&&!zr) nnow++;
		ret+=get(pos+1,uup,zzr,nnow);
	}
	return ret;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		for (int i=1;i<=n;i++) a[i]=s[i]-'0';
		printf("%lld\n",get(1,1,1,0));
	}
}

加个记忆化复杂度就变成了f数组的复杂度

#include<cstdio>
#include<cstring>
using namespace std;
char s[100];
int a[100];
int n;
long long f[100][2][2][100];
long long get(int pos,bool up,bool zr,int now)
{
	if (pos>n) return now;
	long long ret=f[pos][up][zr][now];
	if (ret!=-1) return ret;
	ret=0;
	for (int i=0;i<=9;i++)
	{
		if (up&&i>a[pos]) continue;
		bool uup=up;
		if (i<a[pos]) uup=0;
		bool zzr=zr;
		if (i!=0) zzr=0;
		int nnow=now;
		if (i==0&&!zr) nnow++;
		ret+=get(pos+1,uup,zzr,nnow);
	}
	return f[pos][up][zr][now]=ret;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		for (int i=1;i<=n;i++) a[i]=s[i]-'0';
		memset(f,-1,sizeof(f));
		printf("%lld\n",get(1,1,1,0));
	}
}

数位dp的套路就是这样，暴搜加记忆化，超级简单。