题目描述
tabris有一个习惯,无聊的时候就会数圈圈,无论数字还是字母。
现在tabris更无聊啦,晚上睡不着觉就开始数羊,从a只数到b只。
顺便还数了a到b之间有多少个圈。
但是tabris笨啊,虽然数羊不会数错,但很可能数错圈的个数。
但是tabris很难接受自己笨这个事实,所以想问问你他一共应该数出多少个圈,这样tabris才好判断他到底笨不笨啊。
输入描述:
输入一个T,表示数据组数
每组测试数据包含两个正整数a,b。
T∈[1,1000]
a,b∈[1,1014]
输出描述:
每组数据输出结果,并换行。
示例1
输入
11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 100
输出
0 0 0 1 0 1 0 2 1 1 111
备注:
数字的圈的个数请根据样例自行理解。
题解
数位$dp$。
$dp[i][j]$表示数字长度有$i$位,且第$i$位为$j$的总和,统计一下就可以了。
#include <bits/stdc++.h> using namespace std; long long dp[16][10]; long long b[20], a[20]; long long c[20], sz; /* 0 1 1 0 2 0 3 0 4 1 5 0 6 1 7 0 8 2 9 1 */ void init() { memset(a, 0, sizeof a); a[0] = 1; a[4] = 1; a[6] = 1; a[8] = 2; a[9] = 1; b[0] = 1; for(int i = 1; i <= 15; i ++) { b[i] = b[i - 1] * 10LL; } for(int i = 0; i <= 9; i ++) { dp[1][i] = a[i]; } for(int i = 2; i <= 15; i ++) { for(int j = 0; j <= 9; j ++) { dp[i][j] = a[j] * b[i - 1]; for(int k = 0; k <= 9; k ++) { dp[i][j] = dp[i][j] + dp[i - 1][k]; } } } } long long get(long long x) { if(x == 0) return 0; long long ans = 0; sz = 0; while(x) { sz ++; c[sz] = x % 10; x = x / 10; } for(int i = 1; i <= sz - 1; i ++) { for(int j = 1; j <= 9; j ++) { ans = ans + dp[i][j]; } } for(int j = 1; j < c[sz]; j ++) { ans = ans + dp[sz][j]; } long long sum = a[c[sz]]; for(int i = sz - 1; i >= 1; i --) { for(int j = 0; j < c[i]; j ++) { ans = ans + dp[i][j]; ans = ans + sum * b[i - 1]; } sum = sum + a[c[i]]; } return ans; } int main() { init(); int T; scanf("%d", &T); while(T --) { long long L, R; scanf("%lld%lld", &L, &R); printf("%lld\n", get(R + 1) - get(L)); } return 0; }