A balanced number is a non-negative integer that can be balanced if a pivot is placed at some digit. More specifically, imagine each digit as a box with weight indicated by the digit. When a pivot is placed at some digit of the number, the distance from a digit to the pivot is the offset between it and the pivot. Then the torques of left part and right part can be calculated. It is balanced if they are the same. A balanced number must be balanced with the pivot at some of its digits. For example, 4139 is a balanced number with pivot fixed at 3. The torqueses are 4*2 + 1*1 = 9 and 9*1 = 9, for left part and right part, respectively. It's your job
to calculate the number of balanced numbers in a given range [x, y].
Input The input contains multiple test cases. The first line is the total number of cases T (0 < T ≤ 30). For each case, there are two integers separated by a space in a line, x and y. (0 ≤ x ≤ y ≤ 10 18).
Output For each case, print the number of balanced numbers in the range [x, y] in a line.
Sample Input 2 0 9 7604 24324
Sample Output 10 897
问有多少个数字是“平衡”的，平衡就是取个参考点，左边的数字*距离=右边的数字*距离，4139以3为参考点就是4*2+1*1==9*1
一个数字的参考点唯一。
枚举参考点是第几位，然后对于每一个参考点的位数k，分别跑数位dp，记一下参考点位置，左边的力矩，有没有前导零。在参考点右边的时候直接在力矩上面减即可。
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdlib>
5 #include<algorithm>
6 #include<cmath>
7 #include<queue>
8 #include<deque>
9 #include<set>
10 #include<map>
11 #include<ctime>
12 #define int long long
13 #define LL long long
14 #define inf 0x7ffffff
15 #define pa pair<int,int>
16 #define mkp(a,b) make_pair(a,b)
17 #define pi 3.1415926535897932384626433832795028841971
18 using namespace std;
19 inline LL read()
20 {
21 LL x=0,f=1;char ch=getchar();
22 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
23 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
24 return x*f;
25 }
26 LL n,len,l,r;
27 LL f[50][20][3000][2];
28 int d[110];
29 int zhan[50],top;
30 inline LL dfs(int now,int p,int M,int lead,int fp)
31 {
32 if (now==1)return !M;
33 if (!fp&&f[now][p][M][lead]!=-1)return f[now][p][M][lead];
34 LL ans=0,mx=fp?d[now-1]:9;
35 for (int i=0;i<=mx;i++)
36 {
37 int delta=i*(now-1-p);
38 if (M+delta<0)break;
39 if (now-1==p&&i==0&&lead&&now-1!=1)continue;
40 ans+=dfs(now-1,p,M+delta,lead&&i==0&&now-1!=1,fp&&i==mx);
41 }
42 if (!fp)f[now][p][M][lead]=ans;
43 return ans;
44 }
45 inline LL calc(LL x)
46 {
47 if (x==-1)return 0;
48 if (x==0)return 1;
49 LL xxx=x;
50 len=0;
51 while (xxx)
52 {
53 d[++len]=xxx%10;
54 xxx/=10;
55 }
56 LL sum=0;
57 for (int i=1;i<=len;i++)
58 {
59 for (int j=0;j<=d[len];j++)
60 if (!(j==0&&i==len)||len==1)
61 {
62 sum+=dfs(len,i,j*(len-i),j==0&&len!=1,j==d[len]);
63 }
64 }
65 return sum;
66 }
67 main()
68 {
69 int T=read(),cnt=0;
70 memset(f,-1,sizeof(f));
71 while (T--)
72 {
73 l=read();
74 r=read();
75 if (r<l)swap(l,r);
76 printf("%lld\n",calc(r)-calc(l-1));
77 }
78 } hdu 3709
转载于:https://www.cnblogs.com/zhber/p/7284103.html