求区间[l,r]内有多少个数的满足： 选一个位为中点，是的左边的数到该位的距离等于右边的位到该位的距离。
比如4139 选择3位中点， 那么左边的距离是 4 * 2 + 1 * 1 ， 右边的距离是9 * 1
想了半天，想到了枚举哪一位作为中点， 然后进行数位dp， 但是样例错了， 忽然想到会重复啊，就百度了一下
原来只有0在枚举中点时会重复，其他的数有且只有一个中点是的左边的距离等于右边的距离
所以只要最后ans-len+1即可
1 #include <functional> 2 #include <algorithm> 3 #include <iostream> 4 #include <string.h> 5 #include <stdio.h> 6 #include <math.h> 7 #include <string> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <set> 12 #include <map> 13 #pragma warning(disable:4996) 14 using namespace std; 15 typedef long long LL; 16 const int INF = 0x7fffffff; 17 const int mod = 2520; 18 LL dp[22][22][4000]; 19 int num[22]; 20 21 LL dfs(int cur, int mid, int diff, bool flag) 22 { 23 if (cur == 0) return diff == 2000; 24 if (!flag && dp[cur][mid][diff] != -1) 25 return dp[cur][mid][diff]; 26 LL ret = 0; 27 int end = flag ? num[cur] : 9; 28 for (int i = 0; i <= end; ++i) 29 { 30 int newDiff = diff; 31 if (cur > mid) 32 newDiff += (cur - mid) * i; 33 else if (cur < mid) 34 newDiff -= (mid - cur) * i; 35 ret += dfs(cur - 1, mid, newDiff, i == end && flag); 36 } 37 if (!flag) 38 dp[cur][mid][diff] = ret; 39 return ret; 40 } 41 LL calc(LL n) 42 { 43 int len = 0; 44 while (n) 45 { 46 num[++len] = n % 10; 47 n /= 10; 48 } 49 LL ret = 0; 50 51 for (int i = 1; i <= len; ++i) 52 ret += dfs(len, i, 2000,true); 53 //0每次枚举中点时都被计算进去了，所以要剪掉 54 return ret - len + 1; 55 56 } 57 int main() 58 { 59 memset(dp, -1, sizeof(dp)); 60 int t; 61 LL l, r; 62 scanf("%d", &t); 63 while (t--) 64 { 65 scanf("%I64d%I64d", &l, &r); 66 if (l == 0) 67 printf("%I64d ", calc(r)); 68 else 69 printf("%I64d ", calc(r) - calc(l - 1)); 70 } 71 return 0; 72 }