题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5898
题意：很明确，找出区间[l , r]中符合连续奇数为偶数，连续偶数为奇数的个数。
思路：dp[i][j][1]表示i位数j开头符合条件的数，dp[i][j][0]表示i位数j开头（之后）可能符合条件的数。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[22][11][2];
void init()
{
memset(dp,0,sizeof(dp));
for(int i = 0; i <= 9; i++)
{
if(i & 1)
dp[1][i][0] = 1;
else
dp[1][i][1] = 1;
}
for(int i = 2; i <= 19; i++)
{
for(int j = 0; j <= 9; j++)
{
for(int k = 0; k <= 9; k++)
{
if((j & 1) == (k & 1))
{
dp[i][j][1] += dp[i-1][k][0];
dp[i][j][0] += dp[i-1][k][1];
}
else if(j & 1)
dp[i][j][0] += dp[i-1][k][1];
else
dp[i][j][1] += dp[i-1][k][1];
}
}
}
}
ll solve(ll x)
{
int len = 0, a[22], num;//num表示当前连续奇数或偶数的个数
ll ans = 0;
while(x)
{
a[++len] = x % 10;
x /= 10;
}
a[len+1] = 0;
for(int i = len; i >= 1; i--)
{
for(int j = 0; j < a[i]; j++)
{
if(i == len && j)//之后再处理前导0
ans += dp[i][j][1];
else if(i < len)
{
if(j & 1)
{
if((a[i+1] & 1) && (num & 1))
ans += dp[i][j][0];
else if((a[i+1] & 1) && !(num & 1))
ans += dp[i][j][1];
else if(!(a[i+1] & 1) && (num & 1))
ans += dp[i][j][1];
}
else
{
if((a[i+1] & 1) && !(num & 1))
ans += dp[i][j][1];
else if(!(a[i+1] & 1) && (num & 1))
ans += dp[i][j][0];
else if(!(a[i+1] & 1) && !(num & 1))
ans += dp[i][j][1];
}
}
}
if(i == len)
{
num = 1;
continue;
}
if((a[i+1] & 1) != (a[i] & 1))//
{
if((num & 1) == (a[i+1] & 1))//出现不符合题意的情况，没必要再继续判断下去
break;
num = 1;
}
else
num++;
}
for(int i = len - 1; i >= 1; i--)//处理前导0的情况
{
for(int j = 1; j <= 9; j++)
ans += dp[i][j][1];
}
return ans;
}
int main()
{
int T, cas = 1;
scanf("%d",&T);
init();
while(T--)
{
ll l,r;
scanf("%lld %lld",&l,&r);
printf("Case #%d: %lld\n", cas++, solve(r+1) - solve(l));
}
return 0;
} 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089 思路：dp[i][j]表示i位数j开头符合条件的数，由于前导0不受条件影响，不需要单独考虑。 如判断数字1462，第一次处理0000-0999，第二次处理1000-1399，由于出现4显然不符合条件，后面也不需要继续判断了，直接退出循环。 #include<cstdio>
#include<cstring>
using namespace std;
int dp[10][11];
void init()
{
memset(dp,0,sizeof(dp));
for(int i = 0; i <= 9; i++)
{
if(i != 4)
dp[1][i] = 1;
}
for(int i = 2; i <= 7; i++)
{
for(int j = 0; j <= 9; j++)
{
for(int k = 0; k <= 9; k++)
{
if(j == 4 || j == 6 && k == 2)
continue;
dp[i][j] += dp[i-1][k];
}
}
}
}
int solve(int x)
{
int len = 0, a[10], num;
int ans = 0;
while(x)
{
a[++len] = x % 10;
x /= 10;
}
a[len+1] = 0;
for(int i = len; i >= 1; i--)
{
for(int j = 0; j < a[i]; j++)
{
if(j == 4 || j == 2 && a[i+1] == 6)
continue;
ans += dp[i][j];
}
if(a[i] == 4 || a[i+1] == 6 && a[i] == 2)
break;
}
return ans;
}
int main()
{
init();
int l,r;
while(scanf("%d %d",&l,&r) && (l || r))
printf("%d\n", solve(r+1) - solve(l));
return 0;
}