首页 > 代码库 > codefroces451D - Count Good Substrings 数位DP
codefroces451D - Count Good Substrings 数位DP
题意:给你n,m 问你n-m中有多少个数首位等于末位。
解题思路:数位DP,从0-n有多少个,这样分开计算,首先把每一位所有可能都枚举出来,然后在一位一位的比对DP
解题代码:
1 // File Name: 204a.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月25日 星期五 09时16分57秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 using namespace std;26 LL sum[20];27 LL temp[20];28 LL count(LL n)29 {30 int len = 0;31 LL k = n;32 while(k)33 {34 len ++ ; 35 k/= 10 ; 36 }37 // printf("%d\n",len);38 if(len == 1)39 return n+1;40 LL ans = sum[len-1];41 int t = len ; 42 int a[20];43 while(n)44 {45 a[t] = n %10 ; 46 n = n/10 ;47 t--;48 }49 for(int i =1 ;i <= len-1;i ++)50 {51 int be; 52 be = i == 1?1:0;53 for(;be < a[i];be++)54 {55 ans += temp[len-i-1]; 56 }57 }58 if(a[len] >= a[1])59 ans ++ ; 60 return ans; 61 }62 int main(){63 LL n ,m;64 temp[0] =1 ;65 temp[1] = 10 ; 66 for(int i =1 ;i <= 17 ;i ++)67 temp[i] = temp[i-1]*10;68 sum[0] = 1; 69 sum[1] = 10; 70 for(int i = 2 ;i <= 19 ;i ++)71 {72 sum[i] = sum[i-1];73 for(int j = 1;j <= 9 ;j ++)74 sum[i] += temp[i-2]; 75 }76 // printf("%I64d\n",count(1));77 scanf("%I64d %I64d",&n,&m);78 printf("%I64d",count(m)-count(n-1)); 79 return 0;80 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。