HDU 3709 Balanced Number (数位DP)

时间:2022-09-23 09:30:22

Balanced Number

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 3798    Accepted Submission(s): 1772

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

题意:找出区间内平衡数的个数,所谓的平衡数,就是以这个数字的某一位为支点,另外两边的数字大小乘以力矩之和相等,即为平衡数

思路:首先这是一个数位DP题,解此题用枚举的算法,枚举出所有可能的状况进行dfs,最后相加,就是结果了。

AC代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; int bit[];
__int64 dp[][][]; __int64 dfs(int pos,int o,int l,int limit)
{
//根据题意,要改符合答案的条件,所以当l==0时返回1
if (pos==-)
return l==;
//注意这里,l<0一定要写,因为有一种情况是在pivot的左边<0之后又在左边==0了,这种情况是不符合的,所以这一步不能少
if (l<)
return ;
__int64 &aa=dp[pos][o][l];
if (!limit&&aa!=-)
return aa;
__int64 ans=;
int end=limit?bit[pos]:;
for (int i=;i<=end;i++)
{
int next=l;
next+=(pos-o)*i;
ans+=dfs(pos-,o,next,limit&&i==end);
}
if (!limit)
aa=ans;
return ans;
} __int64 sol(__int64 n)
{
int len=;
while(n)
{
bit[len++]=n%;
n/=;
}
__int64 ans=;
for (int i=;i<len;i++)
{
ans+=dfs(len-,i,,);
}
return ans-(len-);
} int main()
{
int o;
cin>>o;
while(o--)
{
memset(dp,-,sizeof(dp));
__int64 x,y;
cin>>x>>y;
cout<<sol(y)-sol(x-)<<endl;
}
return ;
}

HDU 3709 Balanced Number (数位DP)的更多相关文章

  1. hdu 3709 Balanced Number&lpar;平衡数)--数位dp

    Balanced Number Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) ...

  2. HDU 3709 Balanced Number(数位DP)题解

    思路: 之前想直接开左右两边的数结果爆内存... 枚举每次pivot的位置,然后数位DP,如果sum<0返回0,因为已经小于零说明已经到了pivot右边,继续dfs只会越来越小,且dp数组会炸 ...

  3. HDU 3709 Balanced Number 求区间内的满足是否平衡的数量 (数位dp)

    平衡数的定义是指,以某位作为支点,此位的左面(数字 * 距离)之和 与右边相等,距离是指某位到支点的距离; 题意:求区间内满足平衡数的数量 : 分析:很好这又是常见的数位dp , 不过不同的是我们这次 ...

  4. HDU - 3709 - Balanced Number(数位DP&rpar;

    链接: https://vjudge.net/problem/HDU-3709 题意: A balanced number is a non-negative integer that can be ...

  5. hdu 5898 odd-even number 数位DP

    传送门:hdu 5898 odd-even number 思路:数位DP,套着数位DP的模板搞一发就可以了不过要注意前导0的处理,dp[pos][pre][status][ze] pos:当前处理的位 ...

  6. HDU 5787 K-wolf Number 数位DP

    K-wolf Number Problem Description   Alice thinks an integer x is a K-wolf number, if every K adjacen ...

  7. hdu3709 Balanced Number &lpar;数位dp&plus;bfs&rpar;

    Balanced Number Problem Description A balanced number is a non-negative integer that can be balanced ...

  8. HDU3709:Balanced Number&lpar;数位DP&plus;记忆化DFS&rpar;

    Problem Description A balanced number is a non-negative integer that can be balanced if a pivot is p ...

  9. HDU 5179 beautiful number 数位dp

    题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5179 bc(中文): http://bestcoder.hdu.edu.cn/contes ...

随机推荐

  1. Mysql导入导出非常慢解决办法

    MySQL导出的SQL语句在导入时有可能会非常非常慢,经历过导入仅45万条记录,竟用了近3个小时.在导出时合理使用几个参数,可以大大加快导入的速度. -e 使用包括几个VALUES列表的多行INSER ...

  2. 与锤子手机HR的对话——创业没有联合创始人,CTO 等高管会把它当做自己的事业吗?

    以下对话,是在被之前的锤子HR磨叽2周约面试折腾的火大的心态下进行…… 这个问题发到知乎,被一群人骂啊……cnblogs都是工程师,估计懂期权参加创业的同学多一些,有空前往知乎声援一下……在这里:ht ...

  3. 交流从选择coding&period;net开始

    之前提到我们需要coding.net(一个可以帮助你在线存放管理代码的地方,便于项目合作)来进行学习交流,它可以帮我们记录我们入门的点点滴滴,现在就简单介绍一下coding.net的注册及使用. 1. ...

  4. MySQL数据库恢复的经历。

    蛋疼,定时任务设置错误.把数据给删除了.还有一次是服务器时间不对,也把数据给删除了. 还好,开启了二进制日志,才算把数据找回,但是速度效率也太低. 痛定思变.在把一切交由电脑工作的时候,也要做好一定的 ...

  5. Linux下GPIO驱动(一) ----一个简单的LED驱动

    /******************************* * *杂项设备驱动:miscdevice *majior=10; * * *****************************/ ...

  6. logstash数据处理示例

    #test {"time":1504752032399,"date":"2017-09-08 12:00:00","str&quo ...

  7. 连接db2数据库出现No buffer space available &lpar;maximum connections reached&quest;&rpar;

    Caused by: javax.naming.NamingException: [jcc][t4][2043][11550][3.57.82] 异常 java.net.SocketException ...

  8. IE6、IE7、Firefox中margin问题及input解决办法

    margin不居中的问题 .div{ margin:10px;/*ff*/ *margin:15px;/*ie7*/ _margin:15px;/*ie6*/  尺寸会变为正常的两倍,按道理应为5px ...

  9. Codeforces Beta Round &num;4 &lpar;Div&period; 2 Only&rpar; A&period; Watermelon 水题

    A. Watermelon 题目连接: http://www.codeforces.com/contest/4/problem/A Description One hot summer day Pet ...

  10. scanf是怎么从标准输入读取数据的

    scanf是从标准输入读取数据的 假设现在标准输入中的数据是123456 int a; 而我scanf("%d",&a); 会把123456转化为数字然后存入到a中. 如果 ...