Massive Algorithms: HDU 3709

HDU 3709 - Balanced Number

http://acm.hdu.edu.cn/showproblem.php?pid=3709

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

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

Author

GAO, Yuan

http://www.voidcn.com/article/p-buhbhkpl-p.html

题意：问区间[x,y]内，有多少个平衡数。

一个数是平衡数，即存在一个支点pvt，使得 sum(bit[i]*(pvt-i) )=0;

(x,y属于long long)

要枚举中轴，然后数位dp

https://blog.csdn.net/idealism_xxm/article/details/51412771

又是一个状态很难想的数位DP

对于一个非0数x，最多只存在一个支点pivot使力矩为0

所以支点不同时的统计个数不重复（不包括0），可以直接相加

所以可以设dp[i][j][k]表示长度为i时，支点为j，且高位的数的力矩为k时，满足题意的数的个数

http://www.acmsearch.com/article/show/13958

首先要分析出，对于某个非 0 的 number，最多可能有一个 pivot 的位置。

证明：如果有两个这样的位置，将左边位置移动到右边时，左边的 sigma 一定增大，右边的 sigma 最多保证不减，不可能增大，故不可能再次相等。

于是可以枚举这样的位置，然后分类统计求和。

由于 0 对于每个位置都会被统计到，最后要再减去重复的。

Ps：在数位dp 的 dfs 中，对于 0 的看待，是 len 个0 放一起，以后这个细节要注意。

LL dp[20][20][1800];

int digit[20];

LL dfs(int len,int fixloc,int sum,bool fp) // fp== isLimited
{
    if(!len)
        return sum == 0 ? 1 : 0;
    if(sum < 0)
        return 0;
    if(!fp && dp[len][fixloc][sum] != -1)
        return dp[len][fixloc][sum];
    int fpmax = fp ? digit[len] : 9;
    LL ret = 0;
    for(int i=0;i<=fpmax;i++){
        ret += dfs(len-1,fixloc,sum+i*(len-fixloc),fp && i == fpmax);
    }
    if(!fp)
        dp[len][fixloc][sum] = ret;
    return ret;
}

LL f(LL n)
{
    if(n == -1)
        return 0;
    int len = 0;
    while(n){
        digit[++len] = n % 10;
        n /= 10;
    }
    LL ret = 0;
    for(int i=len;i>=1;i--){
        ret += dfs(len,i,0,true);
    }
    return ret - len + 1;
}

https://www.itread01.com/content/1541519229.html

分析：很好這又是常見的數位dp ，不過不同的是我們這次需要列舉是哪個位置是平衡點，一開始我是想說搜尋到最後以為，然後得到這個數的位數，在判斷平衡位置，想到這樣的話，這就說明了我對數位dp 還是不太熟悉的，因為這樣的話dfs() 裡面的sum , emmm是找不到狀態的；

正解：依然是列舉平衡點的位置，這個思路沒有問題，但是這個卻是在so(_) 函式裡面列舉，啊這樣就妙不可言了，這樣的話只要我們在dfs()裡面增加變數 k ,表示是平衡點的位置，那這樣的話我的sum 就是記錄從左到右的貢獻，因為是從左到右的列舉，左邊加，右邊減，所以是不是sum<0 , 就肯定是不行的嘛；哦！還有一個重點，因為0也是平衡數來的，所以我們這樣的列舉平衡點就加了ans-1 次0 的貢獻，這裡巨坑一開始沒有想到，其他程式碼打出來了，答案不對，然後找程式的錯誤，其實這裡是關鍵來的

https://www.imuo.com/a/acb0f8e814e8f93db97199818cfbd047916d5592b13ed82b067c486d5f3db063

typedef long long ll;
int dig[20];
ll dp[20][20][1500];

ll dfs(int pos,int piv,int sum,bool limit)
{
    if(sum<0) return 0; //右侧力矩已经大于左侧力矩，已经不可能平衡，不需要再往低位DFS，直接剪枝
    if(pos==0) return sum==0; //已经精确到某一个数,观察一下两侧力矩是否相等.
    if(!limit && dp[pos][piv][sum]!=-1) return dp[pos][piv][sum]; //如果曾计算过dfs(pos,piv,sum,0)，直接返回dp[pos][piv][sum]

    int up=limit?dig[pos]:9; //确定当前第pos位的枚举上界
    ll ans=0; //定义ans变量，记录累加结果，在函数最后return ans
    for(int i=0;i<=up;i++) //暴力枚举当前第pos位的数
        ans+=dfs(pos-1,piv,sum+i*(pos-piv),limit && i==up);

    if(!limit) dp[pos][piv][sum]=ans; //将dfs(pos,piv,sum,0)记录到dp[pos][piv][sum]
    return ans;
}
ll solve(ll x)
{
    int len=0;
    while(x) //将上界N记录到dig数组中
    {
        dig[++len]=x%10;
        x/=10;
    }
    ll ans=0;
    for(int i=1;i<=len;i++) ans+=dfs(len,i,0,1);
    return ans-len+1;
}

HDU 3709 - Balanced Number

Labels

Popular Posts