首页 > 代码库 > HDU 3709 Balanced Number

HDU 3709 Balanced Number

2024-08-03 20:43:34   217人阅读

Problem Description
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 ≤ 1018).
 

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


题意：给你2个数n,m   要你求出在n,m区间内以某个数为中心，2边的力矩相等的数的个数，比如：4139，以3为中心  那么左边=4*2+1*1=9   
右边=9*1=9
思路：还是数位DP啊，我们发现 位数、以哪个数为中点、力矩
妈的，现在想起了分手的女友，追梦人的悲哀吧   性格不合适~  我也是醉了！  泪奔..............
AC代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;

ll f[20][20][2000];
int bits[20];

ll dfs(int pos,int mid,int tor,bool flag)
{
    if(pos==-1)return tor==0;
    if(tor<0)return 0;  //引用bin神的剪枝！
    ll ans=0;
    if(!flag&&f[pos][mid][tor]!=-1)
        return f[pos][mid][tor];
    int u=flag?bits[pos]:9;
    for(int i=0;i<=u;i++)
    {
        ans+=dfs(pos-1,mid,tor+i*(pos-mid),flag&&i==u);
    }
    return flag?ans:f[pos][mid][tor]=ans;
}

ll solve(ll n)
{
    int len=0;
    while(n)
    {
        bits[len++]=n%10;
        n/=10;
    }
    ll ans=0;
    for(int i=0;i<len;i++)  //枚举中心
        ans+=dfs(len-1,i,0,true);
    return ans-(len-1);     //坑的个半死，错的我要哭了，刚好今天又这么失落！
    //排除全是0的情况，看了别人的才知道
}

int main()
{
    ll n,m;
    int t;
    memset(f,-1,sizeof(f));
    while(cin>>t)
    {
        while(t--)
        {
            cin>>n>>m;
            cout<<solve(m)-solve(n-1)<<endl;
        }
    }
    return 0;
}


HDU 3709 Balanced Number


联系
我们