Time Limit: 2000/1000 MS (
Java/Others) Memory Limit: 128000/64000 KB (Java/Others) SubmitStatistic Next Problem
Problem Description
8是中国人很喜欢的一个数字，但是如果有3的存在就变成了38，就不是很好了。。
你能告诉我，在[L, R] 的正整数区间内，要么包含3 要么包含 8 的不同的整数有多少个么？
Input
第一行一个整数T (T ≤ 10000)，代表数据的组数
对于每组数据给两个整数 L, R (1 ≤ L ≤ R ≤ 1e9)
Output
对于每组数据，给一个整数为答案。
Sample Input
3
1 100
1 3
8 8
Sample Output
34
1
1
Source
buaads
Manager
nanae
解题思路：简单数位DP,dp[i][0]表示既没有3也没有8的，dp[i][1]表示有3但是没有8的，dp[i][2]表示有8但是没有3的，推的时候用flag1表示前面的数出现了3，flag2表示前面的数出现了8，分情况讨论即可
#include
#include
#include
using namespace std; int dp[20][3]; void DP() { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=20;i++) { dp[i][0]=dp[i-1][0]*8; dp[i][1]=dp[i-1][0]+dp[i-1][1]*9; dp[i][2]=dp[i-1][0]+dp[i-1][2]*9; } } int ans(int num[],int n) { int ans=0; bool flag1,flag2; flag1=flag2=false; for(int k=n-1;k>=0;k--) { if(!flag1&&!flag2) { if(num[k]<=3) { ans+=num[k]*(dp[k][1]+dp[k][2]); if(num[k]==3) flag1=true; } else if(num[k]>3&&num[k]<=8) { ans+=dp[k][1]+dp[k][0]; ans+=(num[k]-1)*(dp[k][1]+dp[k][2]); if(num[k]==8) flag2=true; } else { ans+=dp[k][1]+dp[k][0]; ans+=dp[k][2]+dp[k][0]; ans+=(num[k]-2)*(dp[k][1]+dp[k][2]); } } else if(!flag1&&flag2) { if(num[k]<=3) { ans+=num[k]*(dp[k][0]+dp[k][2]); if(num[k]==3) flag1=true; } else if(num[k]>3&&num[k]<=8) ans+=(num[k]-1)*(dp[k][0]+dp[k][2]); else { ans+=dp[k][2]+dp[k][0]; ans+=(num[k]-2)*(dp[k][0]+dp[k][2]); } } else if(flag1&&!flag2) { if(num[k]<=3) ans+=num[k]*(dp[k][0]+dp[k][1]); else if(num[k]>3&&num[k]<=8) { ans+=dp[k][1]+dp[k][0]; ans+=(num[k]-1)*(dp[k][1]+dp[k][0]); if(num[k]==8) flag2=true; } else ans+=(num[k]-1)*(dp[k][0]+dp[k][1]); } } return ans; } int main() { int t,L,R; int num1[20],num2[20]; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&t); DP(); while(t--) { scanf("%d%d",&L,&R); memset(num1,0,sizeof(num1)); memset(num2,0,sizeof(num2)); int i=0,j=0; R++; while(L) num1[i++]=L%10,L/=10; while(R) num2[j++]=R%10,R/=10; printf("%d\n",ans(num2,j)-ans(num1,i)); } return 0; }