首页 > 代码库 > 2016 ACM/ICPC Asia Regional Shenyang Online 1007/HDU 5898 数位dp
2016 ACM/ICPC Asia Regional Shenyang Online 1007/HDU 5898 数位dp
odd-even number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 388 Accepted Submission(s): 212
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
Source
2016 ACM/ICPC Asia Regional Shenyang Online
题意：一个数字，它每个数位上的奇数都形成偶数长度的段，偶数位都形成奇数长度的段他就是好的。问[L , R]的好数个数。
题解：用dp[i][j]表示第i位数前一位数的状态是j。状态有4种，1-奇数长度为奇，2-奇数长度为偶，3-偶数长度为奇，4-偶数长度为偶
外加一个状态flag=0表示当前这一位之前都是前导零 （注意各个状态之间的转换已经记忆化）
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 //#include<bits/stdc++.h> 8 #include<iostream> 9 #include<cstring> 10 #include<cmath> 11 #include<cstdio> 12 #define ll long long 13 #define mod 1000000007 14 #define PI acos(-1.0) 15 using namespace std; 16 int t; 17 ll l,r; 18 int num[25]; 19 ll dp[25][5]; 20 /* 21 1 奇奇 22 2 奇偶 23 3 偶奇 24 4 偶偶 25 */ 26 ll dfs(int pos,int status,int flag) 27 { 28 if(pos<1) 29 { 30 if(status==2||status==3) 31 return 1; 32 else 33 return 0; 34 } 35 if(!flag&&dp[pos][status]) 36 return dp[pos][status]; 37 int end=flag ? num[pos] : 9;//如果之前都是前导零 则当前这位可以取0~9 38 ll ans=0; 39 for(int i=0;i<=end;i++) 40 { 41 if(!status) 42 { 43 if(!i) 44 { 45 ans=dfs(pos-1,0,0); 46 } 47 else if(i&1) 48 { 49 ans+=dfs(pos-1,1,flag&&i==end); 50 } 51 else 52 { 53 ans+=dfs(pos-1,3,flag&&i==end); 54 } 55 56 } 57 else 58 { 59 if(status==1){ 60 if(i&1){ 61 ans+=dfs(pos-1,2,flag&&i==end); 62 } 63 } 64 else if(status==2){ 65 if(i&1){ 66 ans+=dfs(pos-1,1,flag&&i==end); 67 } 68 else{ 69 ans+=dfs(pos-1,3,flag&&i==end); 70 } 71 } 72 else if(status==3){ 73 if(i&1){ 74 ans+=dfs(pos-1,1,flag&&i==end); 75 } 76 else 77 ans+=dfs(pos-1,4,flag&&i==end); 78 } 79 else{ 80 if(!(i&1)) 81 { 82 ans+=dfs(pos-1,3,flag&&i==end); 83 } 84 } 85 } 86 } 87 dp[pos][status]=ans; 88 return ans; 89 } 90 ll slove(ll x) 91 { 92 memset(dp,0,sizeof(dp)); 93 int len=0; 94 while(x) 95 { 96 num[++len]=x%10; 97 x/=10; 98 } 99 return dfs(len,0,1);100 }101 int main()102 {103 scanf("%d",&t);104 for(int i=1;i<=t;i++)105 {106 scanf("%I64d %I64d",&l,&r);107 printf("Case #%d: %I64d\n",i,slove(r)-slove(l-1));108 }109 return 0;110 }
2016 ACM/ICPC Asia Regional Shenyang Online 1007/HDU 5898 数位dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。