odd-even number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 388 Accepted Submission(s): 212
Problem Description
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^18).
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
1 100
110 220
Sample Output
Case #1: 29
Case #2: 36
Source
题意：一个数字，它每个数位上的奇数都形成偶数长度的段，偶数位都形成奇数长度的段他就是好的。问[L , R]的好数个数。
题解：用dp[i][j]表示第i位数前一位数的状态是j。状态有4种，1-奇数长度为奇，2-奇数长度为偶，3-偶数长度为奇，4-偶数长度为偶
外加一个状态flag=0表示当前这一位之前都是前导零 （注意各个状态之间的转换已经记忆化）
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define ll long long
#define mod 1000000007
#define PI acos(-1.0)
using namespace std;
int t;
ll l,r;
int num[];
ll dp[][];
/*
1 奇奇
2 奇偶
3 偶奇
4 偶偶
*/
ll dfs(int pos,int status,int flag)
{
if(pos<)
{
if(status==||status==)
return ;
else
return ;
}
if(!flag&&dp[pos][status])
return dp[pos][status];
int end=flag ? num[pos] : ;//如果之前都是前导零 则当前这位可以取0~9
ll ans=;
for(int i=;i<=end;i++)
{
if(!status)
{
if(!i)
{
ans=dfs(pos-,,);
}
else if(i&)
{
ans+=dfs(pos-,,flag&&i==end);
}
else
{
ans+=dfs(pos-,,flag&&i==end);
} }
else
{
if(status==){
if(i&){
ans+=dfs(pos-,,flag&&i==end);
}
}
else if(status==){
if(i&){
ans+=dfs(pos-,,flag&&i==end);
}
else{
ans+=dfs(pos-,,flag&&i==end);
}
}
else if(status==){
if(i&){
ans+=dfs(pos-,,flag&&i==end);
}
else
ans+=dfs(pos-,,flag&&i==end);
}
else{
if(!(i&))
{
ans+=dfs(pos-,,flag&&i==end);
}
}
}
}
dp[pos][status]=ans;
return ans;
}
ll slove(ll x)
{
memset(dp,,sizeof(dp));
int len=;
while(x)
{
num[++len]=x%;
x/=;
}
return dfs(len,,);
}
int main()
{
scanf("%d",&t);
for(int i=;i<=t;i++)
{
scanf("%I64d %I64d",&l,&r);
printf("Case #%d: %I64d\n",i,slove(r)-slove(l-));
}
return ;
}