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

HDU 2089 不要62

本文由 Ocrosoft 于 2016-08-17 21:04:18 发表

不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34822    Accepted Submission(s): 12629

Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
 

Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。
 

Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
 

Sample Input
1 100
0 0
 

Sample Output
80
 

Author
qianneng
 

Solution
数位DP用来计算一个区间内满足条件的数的个数。

#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 = 7 + 10;
using namespace std;
int dp[10][10];//数字7位
void ini()
{
	ms(dp);
	dp[0][0] = 1;
	for (int i = 1; i <= 7; i++)
	{
		for (int j = 0; j < 10; j++)//枚举第i位
		{
			for (int k = 0; k < 10; k++)//枚举下一位
			{
				if (j != 4 && !(j == 6 && k == 2))//第i位不是4,并且是6的时候下一位不能是2
				{
					dp[i][j] += dp[i - 1][k];
				}
			}
		}
	}
}
int solve(int n)//传入是n,返回时1到n的满足条件的个数
{
	int ret = 0;
	ini();
	int dig[10] = { 0 }, len = 0;
	while (n / 10 != 0 || n % 10 != 0)
	{
		dig[++len] = n % 10;
		n /= 10;
	}
	for (int i = len; i; i--)
	{
		for (int j = 0; j < dig[i]; j++)
		{
			if (j != 4 && !(dig[i + 1] == 6 && j == 2))//这里数字是倒着存的
				ret += dp[i][j];
		}
		if (dig[i] == 4 || (dig[i] == 2 && dig[i + 1] == 6))break;//遇到不满足的就结束
	}
	return ret;
}
int main()
{
	int n, m;
	while (cin >> n >> m&&n + m)//n,m>0
	{
		cout << solve(m + 1) - solve(n) << endl;//不加一当n,m相同的时候就会是0。
	}
	return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 2089 不要62

点赞 (0)or拍砖 (0)

评论 抢沙发

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