HDU-3709 Balanced Number(数位DP)

超、凢脫俗 2022-06-09 00:27 146阅读 0赞

Balanced Number

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。所以该数是平衡数。现在给你一个区间，问该区间内有多少个平衡数。

思路：这是一道数位DP题，我们可以枚举对称点，然后状态存对称点左边的值减对称点右边的值，如果最后为0说明该数符合要求。详情见代码注释。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 105;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    typedef long long LL;
    int a[20];
    LL dp[20][3600][20];//依次存储位数，对称点左边的值减对称点右边的值，对称点位置
    LL dfs(int pos, int sum/*对称点左右值的差*/, int k/*对称点的位置*/, bool lead/*前导零*/, bool limit/*数位上界变量*/)
    {
    	//递归边界，既然是按位枚举，最低位是1，那么pos==0说明这个数我枚举完了    
    	if (pos == 0) return sum == 0;
    	if (sum < 0)return 0;
    	if (!limit && !lead && dp[pos][sum][k] != -1) return dp[pos][sum][k];
    	int up = limit ? a[pos] : 9;//根据limit判断枚举的上界up   
    	LL ans = 0;
    	//开始计数    
    	for (int i = 0; i <= up; i++)//枚举，然后把不同情况的个数加到ans就可以了    
    		ans += dfs(pos - 1, sum + (pos - k)*i/*在对称点左边就加，右边就减*/, k, lead && i == 0, limit && i == a[pos]);
    	//计算完，记录状态    
    	if (!limit && !lead) dp[pos][sum][k] = ans;
    	/*这里对应上面的记忆化，在一定条件下时记录，保证一致性*/
    	return ans;
    }
    LL solve(LL x)
    {
    	LL sol = 0;
    	int pos = 1;
    	while (x)//把数位都分解出来    
    	{
    		a[pos++] = x % 10;
    		x /= 10;
    	}
    	for (int i = 1; i < pos; i++)//枚举对称点的位置
    		sol += dfs(pos - 1/*从最高位开始枚举*/,0/*对称点左右值的差*/,i/*对称点的位置*/, true, true);
    	return sol - (pos - 2);//要减去000，00这样子的情况。
    }
    int main()
    {
    	LL l, r;
    	int T;
    	scanf("%d", &T);
    	memset(dp, -1, sizeof dp);
    	while (T--)
    	{
    		scanf("%lld%lld", &l, &r);
    		printf("%lld\n", solve(r) - solve(l - 1));
    	}
    }