HDU 5898 odd-even number - dblank

HDU 5898 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

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

题意:给出一个区间[l, r],问其中数位中连续的奇数长度为偶数并且连续的偶数长度为奇数的个数。(1<=L<=R<= 9*10^18)

思路: 数位DP,在dfs的时候我们要记录该位前面一位的奇偶性,还有该连续段的长度,然后dfs的时候搜索到和法的数字,还要考虑全是0的搜索情况。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
const int N = 300+10, inf = 0x3f3f3f3f;
typedef long long ll;
int digit[25], cnt;
ll dp[25][25][2][2];
ll dfs(int pos, int pre, int len, int lim, int zero)
{
    if(pos<=0) return (pre&1)!=(len&1);
    if(!lim && dp[pos][len][pre][zero]!=-1) return dp[pos][len][pre][zero];
    int End = lim ? digit[pos] : 9;
    ll res = 0;
    for(int i = 0; i<=End; i++)
    {
        if(zero)
        {
            if(i == 0)
            res += dfs(pos-1, 0, 0, lim && i == End, 1);
            else res += dfs(pos-1, i&1, 1, lim && i ==End, 0);
        }
        else
        {
            if(i & 1)
            {
                if(pre & 1)
                {
                    res += dfs(pos-1, 1, len+1, lim && i == End, 0);
                }
                else if(len&1)
                {
                    res += dfs(pos-1, 1, 1, lim && i == End, 0);
                }
            }
            else
            {
                if(!(pre & 1))
                {
                    res += dfs(pos-1, 0, len+1, lim && i == End,0);
                }
                else if(!(len & 1))
                {
                    res += dfs(pos-1, 0, 1, lim && i == End, 0);
                }
            }
        }
    }
    if(!lim) dp[pos][len][pre][zero] = res;
    return res;
}
ll solve(ll x)
{
  //  int cnt = 0
  cnt = 0;
  //  if(x == 0)
     //   return 1;
    while(x)
    {
        digit[++cnt] = x%10;
        x/=10;
    }
    return dfs(cnt, 0, 0, 1, 1);
}
int main()
{
    memset(dp, -1, sizeof(dp));
    int t;
    ll n, m;
    cin>>t;
    for(int cas = 1; cas<=t; cas++)
    {
        scanf("%I64d%I64d", &n, &m);
        printf("Case #%d: ",cas);
        printf("%I64d\n",solve(m)-solve(n-1));
    }
    return 0;
}

相关文章

发表新评论