题意：题中平衡数的定义： 以一个位置作为平衡轴，然后左右其他数字本身大小作为重量，到平衡轴的距离作为全职，实现左右平衡（即杠杆原理平衡）。然后为区间[x,y]内平衡数的个数。 (0 ≤ x ≤ y ≤ 1018)
思路一：首先一个非0的n位数最多只有1个中心轴，那么我们可以枚举中心轴，算对于每一个中心轴，有多少数字，统计答案，注意0的特殊情况就可以。
然后TLE。。。
加了一个剪纸（可行性剪枝），如果到一位，state为负，就返回，因为中心轴左边都是+，只有右边是-。这里小于0，那么之后就不可能大于0了
然后还是TLE
但是，查了一下题解，这就是标解啊！
想出了标解，理一下做题的思路：首先，感觉这道题如果记录 当前位、平衡轴位置、当前状态，这样感觉并不好转移。而分析题目性质可以发现，一个非0数只能会有一个（一一对应）平衡轴（0除外，最后特殊处理一下就好），那么如果枚举平衡轴的话，只需计算到最后state是否为0就好，相对来说就很好处理。和前面就很好的形成对比
好吧，知道哪里错了。。。因为这里是记录方案总数，但是在很多情况下，方案是为0，但是0的方案也已经搜过了，所以在memset赋值时，必须把dp全置为-1，才能保证！！！！这里是记忆化搜索都要注意的！！！！，然后在判断时，应该判断是否为-1才对！！
不是特别明白为什么加上 //if (state<0) return 0;，就wa？？？？
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll f[24][5005],n,m; int li[24]; ll dfs(int mid,int i,int state,bool limit) { //if (state<0) return 0; if (i==0&&state==0) return 1; if (i==0) return 0; if (!limit && f[i][state]!=-1) return f[i][state]; int up=limit?li[i]:9; ll ans=0; for (int j=0;j<=up;j++) { ans+= dfs(mid,i-1,state+(mid-i)*j,limit&&j==up?true:false); } if (!limit) f[i][state]=ans; return ans; } ll work(ll n) { if (n<0) return 0;//pay attention to the 0 memset(li,0,sizeof(li)); int tot=0; while (n) { li[++tot]=n%10; n=n/10; } ll ans=0; for (int i=1;i<=tot;i++) { memset(f,-1,sizeof(f)); ans+=dfs(i,tot,0,true); } return ans-tot+1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%I64d%I64d",&n,&m); printf("%I64d\n",work(m)-work(n-1)); } return 0; }
