HDUOJ 5898 odd-even number

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5898

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

思路:数位DP显然,然后。。然后我就WA了一下午。。最后玄学AC。我设dp[pos][pre][oddlen][evenlen]为第pos位前一个数字为pre连续奇数的长度和连续偶数的长度的方案数,然后分类讨论下,对于pre是奇数的情况,如果连续奇数长度为奇数则必须放奇数,否则随便放,对于pre是偶数的情况,如果连续偶数长度为偶数则必须放偶数,否则随便放。然后这里有个点就是你随便放的时候,对于第一种情况,如果放偶数,那么你就要把oddlen置为0,对于第二种情况,如果放奇数,那么你就要把evenlen置为0,相当于这里表示的就是到pos位置为止连续的偶数或奇数长度。。有点绕。。如果不置0就会蜜汁WA。。所以最后发现我这状态定义的是有点繁琐了= =只要开三维表示如果当前位是奇数那么连续奇数的长度或者如果当前位是偶数那么连续偶数的长度,应该是可以写的。。哎数位DP功力还不够还要多写写啊。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
ll l,r;
ll dp[25][10][25][25];
int T,digits[25];
ll dfs(int pos,int pre,int oddlen,int evenlen,bool preZero,bool jud){
    if (pos==0){
        if (!(oddlen&1)&&((evenlen&1)||(evenlen==0))) return 1;
        else return 0;
    }
    if (!jud && !preZero && dp[pos][pre][oddlen][evenlen]!=-1) return dp[pos][pre][oddlen][evenlen];
    int limit=jud?digits[pos]:9;
    ll ret=0;
    for (int i=0;i<=limit;i++){
        if (preZero) ret+=dfs(pos-1,i,(i!=0&&(i&1))?oddlen+1:oddlen,(i!=0&&(!(i&1)))?evenlen+1:evenlen,preZero&&i==0,jud&&(i==limit));
        else if (pre&1){
            if (oddlen&1){
                if (i&1) ret+=dfs(pos-1,i,oddlen+1,evenlen,preZero&&i==0,jud&&(i==limit));
            }
            else{
                if (i&1) ret+=dfs(pos-1,i,oddlen+1,evenlen,preZero&&i==0,jud&&(i==limit));
                else ret+=dfs(pos-1,i,0,evenlen+1,preZero&&i==0,jud&&(i==limit));//置零
            }
        }
        else{
            if (!(evenlen&1)){
                if (!(i&1)) ret+=dfs(pos-1,i,oddlen,evenlen+1,preZero&&i==0,jud&&(i==limit));
            }
            else{
                if (i&1) ret+=dfs(pos-1,i,oddlen+1,0,preZero&&i==0,jud&&(i==limit));//置零
                else ret+=dfs(pos-1,i,oddlen,evenlen+1,preZero&&i==0,jud&&(i==limit));
            }
        }
    }
    if (!jud && !preZero) dp[pos][pre][oddlen][evenlen]=ret;
    return ret;
}
ll solve(ll x){
    int cnt=0;
    while (x){
        digits[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,0,0,0,true,true);
}
int main(){
    int cas=1;
    memset(dp,-1,sizeof(dp));
    for (read(T);T--;){
        read(l),read(r);
        printf("Case #%d: %I64d\n",cas++,solve(r)-solve(l-1));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注