描述

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*10¹⁸

给出一个区间[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);
}

数位dp WOJ 1515 不要62