﻿HDU 5898 odd-even number-Ocrosoft

# odd-even number

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
```

Sample Output
```Case #1: 29
Case #2: 36
```

Source

Solution

```#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 LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 150 + 10;
const int MOD = 100000;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
using namespace std;
//or2..or2..or2..or2..//
int dig[20], len;
LL dp[20][2][20][2];//第i位，上一位奇偶，连续位数，前导零

LL dfs(int pos, int pre = 0, int ln = 0, bool inf = 1, bool ze = 1)//pre 1为奇，0为偶
{
if (!pos)//处理完最后一位
{
if (pre)//最后一位是奇数,如果连续位数为偶数,则可行
return (ln & 1) == 0;
//最后一位是偶数,如果连续位数为奇数,则可行
else return ln & 1;
}
//已经搜索过
if (!inf&&dp[pos][pre][ln][ze] != -1)return dp[pos][pre][ln][ze];
int en = inf ? dig[pos] : 9;//如果前面的位数小于dig[pos]，inf就会为0，后面的数字可以任取
LL ans = 0;
for (int i = 0; i <= en;i++)
{
if (i & 1)//奇数
{
if (ze)//有前导零
{
//如果还是放0,还是有前导零
if (!i)ans += dfs(pos - 1, 0, 0, inf&&i == en, 1);
//如果放非0,而且是奇数,连续位数为1,没有前导零
else ans += dfs(pos - 1, 1, 1, inf&&i == en, 0);
}
else if (!pre)//上一位是偶数
{
//连续位数为奇数的情况下满足条件
if (ln & 1)ans += dfs(pos - 1, 1, 1, inf&&i == en, ze);
}
//上一位是奇数
else ans += dfs(pos - 1, 1, ln + 1, inf&&i == en, ze);
}
else//偶数
{
if (ze)//有前导零
{
//如果还是放0,还是有前导零
if (!i)ans += dfs(pos - 1, 0, 0, inf&&i == en, 1);
//如果放非0,而且是偶数,连续位数为1,没有前导零
else ans += dfs(pos - 1, 0, 1, inf&&i == en, 0);
}
//上一位是偶数
else if (!pre)ans += dfs(pos - 1, 0, ln + 1, inf&&i == en, ze);
else
{
//上一位是奇数,连续位数为偶数时满足条件
if (!(ln & 1))ans += dfs(pos - 1, 0, 1, inf&&i == en, ze);
}
}
}
if (!inf)dp[pos][pre][ln][ze] = ans;//记录
return ans;
}
int main()
{
int T, cas = 1;
LL l, r;
cin >> T;
while (T--)
{
memset(dp, -1, sizeof(dp));
scanf("%lld%lld", &l, &r), l--;
for (len = 0; l; l /= 10)dig[++len] = l % 10;
LL tp = dfs(len);
for (len = 0; r; r /= 10)dig[++len] = r % 10;
printf("Case #%d: %lld\n", cas++, dfs(len) - tp);
}
return 0;
}```