odd-even number
题目链接：
http://acm.split.hdu.edu.cn/showproblem.php?pid=5898
题意：
求区间内满足以下条件的数的个数
①每一位连续的奇数出现偶数次
②每一位连续的偶数出现奇数次
题解：
区间DP水题，记0为出现奇数偶数次，1为出现奇数奇数次
记0为没有出现过偶数，1为出现偶数偶数次，2为出现偶数奇数次。
代码
#include<stdio.h> #include<string.h> #define Type long long const int N=31; Type dp[N][10][2][3][2]; int bit[N]; long long sum; bool change(bool status,int i,int pre,int sum1,int sum2) { if(pre==-1||!sum)return true; if(pre%2!=i%2) { if(i%2)return !(sum2%2); else return !(sum1%2); } else return true; } int Sum1(int i,int pre,int sum1,int sum2) { if(!sum||i%2!=pre%2)return i%2; return i%2?(sum1+1)%2:sum1; } int Sum2(int i,int pre,int sum1,int sum2) { if(!sum&&!i)return 0; if(!sum||i%2!=pre%2)return (i%2)?0:2; if(i%2)return sum2; else { if(!sum2)return 2; else return sum2==2?1:2; } } Type dfs(int pos,int pre,bool limit,bool status,int sum1,int sum2) { sum=pre==-1?0:sum*10+pre; if(pos<1)return (status&&!(sum1%2)&&!(sum2%2))?1:0; if(!limit&&pre!=-1&&dp[pos][pre][sum1][sum2][status]!=-1) return dp[pos][pre][sum1][sum2][status]; int end=limit?bit[pos]:9; Type res=0; for(int i=0;i<=end;++i) res+=dfs(pos-1,i,limit&&(i==end),status&&change(status,i,pre,sum1,sum2),Sum1(i,pre,sum1,sum2),Sum2(i,pre,sum1,sum2)); if(!limit)dp[pos][pre][sum1][sum2][status]=res; if(pre!=-1)sum=(sum-pre)/10; return res; } Type Get_Ans(Type x) { sum=0; int len=0; while(x||!len) { bit[++len]=x%10; x/=10; } return dfs(len,-1,true,true,0,0); } void solve() { Type l,r; int T,w=0; memset(dp,-1,sizeof(dp)); scanf("%d",&T); while(T--) { scanf("%lld%lld",&l,&r); printf("Case #%d: %lld ",++w,Get_Ans(r)-Get_Ans(l-1)); } } int main() { solve(); return 0; }