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

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

平衡数的定义是指,以某位作为支点,此位的左面(数字 * 距离)之和 与右边相等,距离是指某位到支点的距离;

题意:求区间内满足平衡数的数量 ;

分析:很好这又是常见的数位dp , 不过不同的是我们这次需要枚举是哪个位置是平衡点 , 一开始我是想说搜索到最后以为 ,然后得到这个数的位数 ,在判断平衡位置 , 想到这样的话 , 这就说明了我对数位dp 还是不太熟悉的 ,因为这样的话dfs() 里面的sum , emmm是找不到状态的 ;

正解: 依然是枚举平衡点的位置  ,这个思路没有问题 , 但是这个却是在so(_) 函数里面枚举 ,啊这样就妙不可言了, 这样的话只要我们在dfs()里面增加变量 k ,表示是平衡点的位置 , 那这样的话我的sum 就是记录 从左到右的贡献 , 因为是从左到右的枚举 , 左边加, 右边减 , 所以是不是sum<0 , 就肯定是不行的嘛 ;哦!还有一个重点 ,因为0也是平衡数来的 , 所以我们这样的枚举平衡点就加了ans-1 次0 的贡献 ,这里巨坑一开始没有想到,其他代码打出来了 , 答案不对 ,然后找程序的错误 ,其实这里是关键来的

#include<stdio.h>
#include<string.h>
#include<cmath>
using namespace std ;
#define ll long long
ll dp[][][];
ll a[];
ll dfs(int pos , int k , int sum , bool limit)
{
if(pos==-)
return sum==;
if(sum<)
return ;
if(!limit && dp[pos][k][sum]!=-)
return dp[pos][k][sum];
int up=limit?a[pos]:;
ll ans=;
for(int i= ; i<=up ; i++)
{
ans+=dfs(pos-,k,sum+(pos-k)*i,limit&&i==a[pos]);
}
if(!limit)
dp[pos][k][sum]=ans;
return ans;
}
ll so(ll x)
{
int ans=;
ll sum=;
while(x)
{
a[ans++]=x%;
x/=; }
for(ll i= ; i<ans ; i++)
sum+=dfs(ans-,i,,);
return sum-(ans-);
}
int main( )
{ int t;
memset(dp,-,sizeof(dp));
scanf("%d",&t);
while(t--)
{
ll l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",so(r)-so(l-));
}
}

HDU 3709 Balanced Number 求区间内的满足是否平衡的数量 (数位dp)的更多相关文章

  1. hdu 3709 Balanced Number(数位dp)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3709 题意:给定区间[a,b],求区间内平衡数的个数.所谓平衡数即有一位做平衡点,左右两边数字的力矩相 ...

  2. HDU 3709 Balanced Number &lpar;数位DP&rpar;

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

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

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

  4. HDU 3709 Balanced Number (数位DP)

    题意: 找出区间内平衡数的个数,所谓的平衡数,就是以这个数字的某一位为支点,另外两边的数字大小乘以力矩之和相等,即为平衡数. 思路: 一开始以为需要枚举位数,枚举前缀和,枚举后缀和,一旦枚举起来就会M ...

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

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

  6. HDU 3709 Balanced Number

    发现只要Σa[i]*i%Σa[i]==0就可以. #include<iostream> #include<cstdio> #include<cstring> #in ...

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

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

  8. HDU 4417 Super Mario(主席树求区间内的区间查询&plus;离散化)

    Super Mario Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Tota ...

  9. hdu 4630 查询&lbrack;L&comma;R&rsqb;区间内任意两个数的最大公约数

    No Pain No Game Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) ...

随机推荐

  1. 修改Windows&sol;Ubuntu&sol;Mint多系统的默认启动顺序

    打开该配置文件 sudo gedit /etc/default/grub 其中的“GRUB_DEFAULT=0”就是设置的默认启动项了.GRUB启动项是按照启动菜单依次使用数字进行索引了,起始数字为0 ...

  2. Ubuntu14&period;04安装OpenCV2&period;4&period;9

    1.安装依赖 sudo apt-get install build-essential libgtk2.0-dev libjpeg-dev libtiff4-dev libjasper-dev lib ...

  3. iOS7&lpar;iPhone4&rpar;button不能改变button的title

    最近整了个高端的iPhone4测试机,系统是iOS7.1,测出一个问题,两个button,第二个的enable为NO,点击第一个button,第二个的title改变,然而在iPhone4上并不能运行, ...

  4. 每天一点css3聚沙成塔(一):transition

    transition 语法: transition:[ transition-property ] || [ transition-duration ] || [ transition-timing- ...

  5. 《Pointers On C》读书笔记&lpar;第一章 快速上手&rpar;

    1.C语言是一种*格式的程序设计语言,没有规则要求我们必须如何书写语句.然而,如果我们在编写程序时能够遵守一些约定还是非常值得的,它可以使代码更加容易阅读和修改.另外,预处理命令有较为严格的规则. ...

  6. Hadoop&comma;master和slave简单的分布式搭建

    搭建过程中配置免密钥登录为了以后方便使用 [提醒]安装Hadoop中会遇到新建文件夹,配置路径等问题,这个不能生搬硬套,要使用自己配置的路径,灵活使用. Hadoop的部署配置文件在http://bl ...

  7. JavaScript中的trim自定义

    先直接贴代码 String.prototype.trimfy=function (val){ var demo=String(this); if(demo.indexOf(val)>=0){ i ...

  8. 关于socket&period;io的使用

    这段时间学习了socket.io,用它写了小项目,在此总结下它的基本使用方式和一些要点. socket.io是基于Node.js和WebSocket协议的实时通信开源框架,它包括客户端的JavaScr ...

  9. BFPRT算法

    解决的问题:在一个数组中找到最小的k个数 常规解法:1.排序,输出前k个数,时间复杂度O(n*log(n)). 2.利用一个大小为k的大根堆,遍历数组维持大根堆,最后返回大根堆就可以了,时间复杂度O( ...

  10. OpenStack实践系列⑧可视化服务Horizon之Dashboard演示

    OpenStack实践系列⑧可视化服务Horizon之Dashboard演示 七.可视化服务Horizon之Dashboard演示 仪表板依赖于功能核心服务,包括身份,图像服务,计算和网络两种(neu ...