Balanced Number
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 3798 Accepted Submission(s): 1772
to calculate the number of balanced numbers in a given range [x, y].
0 9
7604 24324
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)的更多相关文章
-
hdu 3709 Balanced Number(平衡数)--数位dp
Balanced Number Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) ...
-
HDU 3709 Balanced Number(数位DP)题解
思路: 之前想直接开左右两边的数结果爆内存... 枚举每次pivot的位置,然后数位DP,如果sum<0返回0,因为已经小于零说明已经到了pivot右边,继续dfs只会越来越小,且dp数组会炸 ...
-
HDU 3709 Balanced Number 求区间内的满足是否平衡的数量 (数位dp)
平衡数的定义是指,以某位作为支点,此位的左面(数字 * 距离)之和 与右边相等,距离是指某位到支点的距离; 题意:求区间内满足平衡数的数量 : 分析:很好这又是常见的数位dp , 不过不同的是我们这次 ...
-
HDU - 3709 - Balanced Number(数位DP)
链接: https://vjudge.net/problem/HDU-3709 题意: A balanced number is a non-negative integer that can be ...
-
hdu 5898 odd-even number 数位DP
传送门:hdu 5898 odd-even number 思路:数位DP,套着数位DP的模板搞一发就可以了不过要注意前导0的处理,dp[pos][pre][status][ze] pos:当前处理的位 ...
-
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 ...
-
hdu3709 Balanced Number (数位dp+bfs)
Balanced Number Problem Description A balanced number is a non-negative integer that can be balanced ...
-
HDU3709:Balanced Number(数位DP+记忆化DFS)
Problem Description A balanced number is a non-negative integer that can be balanced if a pivot is p ...
-
HDU 5179 beautiful number 数位dp
题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5179 bc(中文): http://bestcoder.hdu.edu.cn/contes ...
随机推荐
-
Mysql导入导出非常慢解决办法
MySQL导出的SQL语句在导入时有可能会非常非常慢,经历过导入仅45万条记录,竟用了近3个小时.在导出时合理使用几个参数,可以大大加快导入的速度. -e 使用包括几个VALUES列表的多行INSER ...
-
与锤子手机HR的对话——创业没有联合创始人,CTO 等高管会把它当做自己的事业吗?
以下对话,是在被之前的锤子HR磨叽2周约面试折腾的火大的心态下进行…… 这个问题发到知乎,被一群人骂啊……cnblogs都是工程师,估计懂期权参加创业的同学多一些,有空前往知乎声援一下……在这里:ht ...
-
交流从选择coding.net开始
之前提到我们需要coding.net(一个可以帮助你在线存放管理代码的地方,便于项目合作)来进行学习交流,它可以帮我们记录我们入门的点点滴滴,现在就简单介绍一下coding.net的注册及使用. 1. ...
-
MySQL数据库恢复的经历。
蛋疼,定时任务设置错误.把数据给删除了.还有一次是服务器时间不对,也把数据给删除了. 还好,开启了二进制日志,才算把数据找回,但是速度效率也太低. 痛定思变.在把一切交由电脑工作的时候,也要做好一定的 ...
-
Linux下GPIO驱动(一) ----一个简单的LED驱动
/******************************* * *杂项设备驱动:miscdevice *majior=10; * * *****************************/ ...
-
logstash数据处理示例
#test {"time":1504752032399,"date":"2017-09-08 12:00:00","str&quo ...
-
连接db2数据库出现No buffer space available (maximum connections reached?)
Caused by: javax.naming.NamingException: [jcc][t4][2043][11550][3.57.82] 异常 java.net.SocketException ...
-
IE6、IE7、Firefox中margin问题及input解决办法
margin不居中的问题 .div{ margin:10px;/*ff*/ *margin:15px;/*ie7*/ _margin:15px;/*ie6*/ 尺寸会变为正常的两倍,按道理应为5px ...
-
Codeforces Beta Round #4 (Div. 2 Only) A. Watermelon 水题
A. Watermelon 题目连接: http://www.codeforces.com/contest/4/problem/A Description One hot summer day Pet ...
-
scanf是怎么从标准输入读取数据的
scanf是从标准输入读取数据的 假设现在标准输入中的数据是123456 int a; 而我scanf("%d",&a); 会把123456转化为数字然后存入到a中. 如果 ...