浙江财经大学
信工学院ACM集训队

ACDream 1064 完美数

本文由 Ocrosoft 于 2016-08-18 11:45:56 发表

完美数

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

8是中国人很喜欢的一个数字,但是如果有3的存在就变成了38,就不是很好了。。

你能告诉我,在[L, R] 的正整数区间内,要么包含3 要么包含 8 的不同的整数有多少个么?

Input

第一行一个整数T (T ≤ 10000),代表数据的组数

对于每组数据给两个整数 L, R (1 ≤ L ≤ R ≤ 1e9)

Output

对于每组数据,给一个整数为答案。

Sample Input

3
1 100
1 3
8 8

Sample Output

34
1
1

Solution

看了好久…看一个题解还WA了5次…还是周巨巨靠谱。
自己在看的时候写了很多注释,看注释就好了。(注释看不到的,是因为屏幕不够宽…可以复制到编辑器里看…)

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 1000 + 10;
using namespace std;
int dp[15][3];//一维表示数字位数,二维表示1.没有3,8;2.有3;3.有8;
void ini()
{
	ms(dp);
	dp[0][0] = 1, dp[1][0] = 8, dp[1][1] = 1, dp[1][2] = 1;//dp[0][0]实际情况是不存在的,solve中数字要从num[1]开始放
	for (int i = 2; i <= 10; i++)
	{
		dp[i][0] = dp[i - 1][0] * 8;//10个数,除掉3、8,剩余8个
		dp[i][1] = dp[i - 1][0] + dp[i - 1][1] * 9;//这一位是3,那么dp[i-1][1]没有3、8的都满足了;同时之前有3的,这一位可以是任意数字
		dp[i][2] = dp[i - 1][0] + dp[i - 1][2] * 9;//这一位是8,那么dp[i-1][1]没有3、8的都满足了;同时之前有8的,这一位可以是任意数字
	}
}
int solve(int n)//传入是n,返回是[1,n)的满足条件的个数
{
	int ret = 0;
	int num[15] = { 0 }, len = 0;
	while (n)
	{
		num[++len] = n % 10;
		n /= 10;
	}
	bool f1 = 0, f2 = 0;//表示出现过3、出现过8
	for (int i = len; i; i--)
	{
		if (!f1 && !f2)//3、8都没有出现过(指的是这个数字,下面的出现指的是dp数组中)
		{
			if (num[i] <= 3)//放 [0,2]
				ret += (dp[i - 1][1] + dp[i - 1][2])*num[i];//3、8都没有出现过,这一位又不能放3、8,前面的数位需要有3或者8
			else if (num[i] <= 8)//放 [0,7]
				ret += dp[i - 1][1] * num[i] +//如果前面有3,那么这一位放[0,7]都可以
				dp[i - 1][0] + //如果前面没有3、8,这一位要放3,省略了*1
				dp[i - 1][2] * (num[i] - 1);//如果前面有8,这一位可以放[0,7]除掉3
			else if (num[i] == 9)//放 [0,8]
				ret += dp[i - 1][0] + dp[i - 1][0] + //如果前面没有3、8,这一位可以放3、8
				(dp[i - 1][1] + dp[i - 1][2])*(num[i] - 1);//如果前面有3,这位放3;有8,放8;
		}
		//else if (f1 && !f2)ret += (dp[i - 1][0] + dp[i - 1][2])*(num[i] <= 8 ? num[i] : num[i] - 1);
		//else if (!f1 && f2)ret += (dp[i - 1][0] + dp[i - 1][1])*(num[i] <= 3 ? num[i] : num[i] - 1);
		//下面两个else if可以简写成以上两行
		else if (f1 && !f2)//如果出现过3
		{
			if (num[i] <= 8)//放[0,7]
				ret += (dp[i - 1][0] + dp[i - 1][2])*num[i];//(数字)前面已经出现过3,而且放的数不会是8,只要前面没有出现8,都可以放。
			else
				ret += (dp[i - 1][0] + dp[i - 1][2])*(num[i] - 1);//同上,除去8
		}
		else if (!f1 && f2)//如果出现过8
		{
			if (num[i] <= 3)//放[0,2]
				ret += (dp[i - 1][0] + dp[i - 1][1])*num[i];//(数字)前面已经出现过8,而且放的数不会是3,只要前面没有出现3,都可以放。
			else
				ret += (dp[i - 1][0] + dp[i - 1][1])*(num[i] - 1);//同上,除去3
		}
		//上面两个else if可以合并成下面一个else
		/*
		else
		{
			int id = f1 ? 2 : 1, lim = f1 ? 8 : 3;//如果出现过3或者8
			if (num[i] <= lim)
				ret += (dp[i - 1][0] + dp[i - 1][id])*num[i];
			else
				ret += (dp[i - 1][0] + dp[i - 1][id])*(num[i] - 1);
		}
		*/
		if (num[i] == 3)f1 = 1;
		if (num[i] == 8)f2 = 1;
		if (f1&&f2)break;
	}
	return ret;
}
int main()
{
	ini();
	int T;
	cin >> T;
	while (T--)
	{
		int n, m;
		cin >> n >> m;//n,m>0
		cout << solve(m + 1) - solve(n) << endl;//不加一当n,m相同的时候就会是0。
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » ACDream 1064 完美数

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址