记录编号	44414	评测结果	AAAAAAAAAA
题目名称	1174.[顾研NOIP] 幸运之数	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	1.798 s
提交时间	2012-10-18 18:25:17	内存使用	3.15 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <set>
using namespace std;

const int sq10[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

set<int> ok[2];
set<int>::iterator iter,itere;
int num[11],nnum[11];
bool use;

void combine(int n)
{
	int i,now=0;
	for (i=n;i>=0;i--)
		now=now*10+nnum[i];
	if (now>=sq10[n])
		ok[!use].insert(now);
}

void dfs(int now,int deep,int maxdeep)
{
	nnum[deep]=now;
	if (deep==maxdeep)
	{
		combine(maxdeep);
		return;
	}
	int temp;
	if (num[deep])
	{
		temp=now+num[deep];
		if (temp<=9)
			dfs(temp,deep+1,maxdeep);
		temp=now-num[deep];
		if (temp>=0)
			dfs(temp,deep+1,maxdeep);
	}
	else
		dfs(now,deep+1,maxdeep);	
}

int main(void)
{
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	int i,j,a,b,len,temp,total=0;
	cin>>a>>b;
	ok[use].insert(7);
	for (i=1;i<=8;i++)
	{
		ok[!use]=ok[use];
		itere=ok[use].end();
		for (iter=ok[use].begin();iter!=itere;iter++)
		{
			temp=(*iter);
			memset(num,0,sizeof(num));
			len=0;
			while (temp)
			{
				num[len++]=temp%10;
				temp/=10;
			}
			for (j=0;j<=9;j++)
				dfs(j,0,i);
		}
		use=!use;
	}
	itere=ok[use].end();
	for (iter=ok[use].begin();iter!=itere;iter++)
	{
		temp=(*iter);
		if (temp<a)
			continue;
		if (temp>b)
			break;
		total++;
	}
	cout<<total<<endl;
	return(0);
}