数位dp WOJ 1515 不要62

时间:2021-07-22 17:11:33   收藏:0   阅读:2

描述

For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*1018

给出一个区间[l, r],问其中数位中连续的奇数长度为偶数并且连续的偶数长度为奇数的个数。

Input

First line a t,then t cases.every line contains two integers L and R.

Output

Print the output for each case on one line in the format as shown below.

Sample Input

2
1 100
110 220

Sample Output

Case #1: 29
Case #2: 36

题解

数位dp,先转为十进制,再每位比较是否合法

代码

#include<bits/stdc++.h>
using namespace std;
int f[20][2][2];
vector<int> F;
#define pb push_back 
inline vector<int> trans(int x)
{
	vector<int> s;
	s.pb(0);
	while(x)
	{
		s.pb(x%10);
		x/=10;
	}
	return s;
}
inline int calc(int x)
{
	F=trans(x);
	F.resize(20);
	memset(f,0,sizeof(f));
	f[19][1][0]=1;
	for(int i=19;i;i--)
		for(int a=0;a<2;a++)
			for(int b=0;b<2;b++)
				for(int k=0;k<=9;k++)
				{
					if(a&&k>F[i]) break;
					if(k==4) continue;
					if(b&&k==2) continue;
					f[i-1][a&&(k==F[i])][k==6]+=f[i][a][b];
				}
	return f[0][0][0]+f[0][0][1]+f[0][1][0]+f[0][1][1];
}
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	cout<<calc(b)-calc(a-1);
}

原文:https://www.cnblogs.com/Socratize/p/15044002.html

评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!