HDU3709 Balanced Number

题意

对于一个数，如果能找到一个点作为支点，两边的数位看做砝码，若两边权值相同则为Balanced Number，参考杠杆

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¹⁸).

Output

For each case, print the number of balanced numbers in the range [x, y] in a line.

题解

有一个性质，对于一个非0的数，他的支点有且只有一个，可能比较显然吧

那么我们就可以考虑枚举支点，再按照一般的套路跑就OK了

有个小技巧就是，比较两边的权值时，将左边的数位贡献记为正，右边为负，那么只要最后sum为0即可

为了防止数组越界（sum＜0），可以最初给sum一个比较大的值；也可以sum＜0时return，因为是从左边过来的，一旦＜0就不可能加回去

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll l,r;
int num[20],len;
ll f[20][1800][2];

ll dfs(int s,int sum,int mid,bool lim){
    if(!s) return !sum;
    if(sum<0) return 0;//剪枝 
    if(f[s][sum][lim]!=-1) return f[s][sum][lim];
    int mx= lim ? num[s] : 9 ;
    ll ret=0;
    for(int i=0;i<=mx;i++)
     ret+=dfs(s-1,sum+i*(s-mid),mid,lim&&i==mx);
    return f[s][sum][lim]=ret;
}

ll cx(ll x){
    len=0;
    while(x){
        num[++len]=x%10;
        x/=10;
    }
    ll ans=0;
    for(int i=1;i<=len;i++){
        memset(f,-1,sizeof(f));
        ans+=dfs(len,0,i,true);
    }
    return ans-len+1;
}

void nice(){
    scanf("%lld%lld",&l,&r);
    printf("%lld
",cx(r)-cx(l-1));
}

int main(){
    scanf("%d",&t);
    while(t--) nice();
}