HDU 3709 Balanced Number (数位DP)

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

题意:

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

思路:

  一开始以为需要枚举位数,枚举前缀和,枚举后缀和,一旦枚举起来就会MLE。

  其实只需要3维 [第几位][和][轴位置],对于轴的位置是需要枚举的,每个位都是有可能的,比如900和7都是一个平衡数。注意这道题的区间下限可能为0,而0也是平衡数,这在拆十进制的时候len=0的,最好将0特处理。

 #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=; LL f[N][][N], bit[N];
//[第几位][和][轴] LL dfs(int i,int sum,int mid,bool e)
{
if(i==) return sum==;
if(sum< || sum>=) return ;
if(!e && ~f[i][sum][mid]) return f[i][sum][mid]; LL ans=;
int u= e? bit[i]: ;
for(int d=; d<=u; d++)
{
if(sum== && i==mid && d==) continue; //首位是mid,必须不为0
ans+=dfs(i-, sum+(i-mid)*d, mid, e&&d==u); //注意不能为负
}
return e? ans: f[i][sum][mid]=ans;
} LL cal(LL n)
{
if(n<) return ;
int len=;
while(n) //拆数
{
bit[++len]=n%;
n/=;
}
LL ans=; //dfs是没有统计0的,因为len=0是不会执行dfs的
for(int i=; i<=len; i++)
ans+=dfs(len, , i, true);
return ans;
} int main()
{
//freopen("input.txt","r",stdin);
memset(f,-,sizeof(f));
LL L,R;int t;cin>>t;
while( t-- )
{
cin>>L>>R;
cout<<cal(R)-cal(L-)<<endl;
}
return ;
}

AC代码

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

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

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

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

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

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

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

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

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

  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 5898 odd-even number 数位DP

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

  7. 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 ...

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

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

  9. 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 ...

  10. HDU 5179 beautiful number 数位dp

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

随机推荐

  1. 树莓派之web服务器搭建

    树莓派之web服务器搭建 (一)使用ufw创建防火墙 设置目的:可以完全阻止对树莓派的访问也可以用来配置通过防火墙对特点程序的访问.使用防火墙更好的保护树莓派. 准备工作 1.带有5V电源的树莓派 2 ...

  2. 通过IP获得IP所在地的三个接口

    http://ip.qq.com/cgi-bin/searchip?searchip1=180.168.144.211 http://ip.taobao.com/service/getIpInfo.p ...

  3. 如何导入ShareSDK的sample

    由于项目需要,最近需要做10几个平台的分享,如果自己去集成,浪费很多时间,而且还很难成功.最后发现Sharesdk,可以满足项目需求. 首先,需要到他们的官网http://sharesdk.cn/下载 ...

  4. java事件处理2

    Document事件 这个事件有点特别,需要用getDocument()返回到自己所维护的文档,然后就可以添加监视器 (textArea1.getDocument).addDocumentListen ...

  5. IE10-IE11在NET4&period;0下出现&OpenCurlyDoubleQuote;&lowbar;&lowbar;doPostBack未定义”解决方案

    IE10在NET4.0下出现"__doPostBack未定义"的办法 参考文章: http://blogs.msdn.com/b/scott_hanselman/archive/2 ...

  6. 【Objective-C】内存管理

    涉及三大知识点:引用计数器,属性参数,自动释放池 一.引用计数器(程序编译时Xcode可以自动给你的代码添加内存释放代码,如果编写手动释放代码Xcode会报错) 1.关闭ARC(xcode 4.x之后 ...

  7. &lbrack;转帖&rsqb;利用hydra(九头蛇)暴力破解内网windows登录密码

    利用hydra(九头蛇)暴力破解内网windows登录密码 https://blog.csdn.net/weixin_37361758/article/details/77939070 尝试了下 能够 ...

  8. python的var&lowbar;dump,打印对象内容

    from __future__ import print_function from types import NoneType __author__ = "Shamim Hasnath&q ...

  9. C&num;关闭子窗口而不释放子窗口对象的问题解决

    在网上找来一些方式,感觉还都不错,下面给出方式: 在线扫描相机的调试过程中,需要开辟调试界面来进行位置的配置.调试结束后,一种常用的方式是将调试参数保存并在下次启动时加载.另一种简单方式是直接使用该参 ...

  10. AngularJS 无限滚动加载数据控件 ngInfiniteScroll

    在开发中我们可能会遇到滚动鼠标到浏览器底部实现数据的加载,js和jquery实现都不复杂都是既然AngularJS提供现成的我们怎么不用昵. ng-infinite-scroll.js这个组件则可以实 ...