dp之数位dp---(度的数量)
创始人
2024-05-30 08:23:18
0

题目:

在这里插入图片描述

思路:
首先对题目意思进行分析:恰好等于 K 个互不相等的 B 的整数次幂之和,这句话的意思是说对于某一个B进制数x说,x只有k位上只有1,其他位为0。然后让你求区间[X,Y]的满足条件的数字有多少,这里我们可以用区间[1,Y]-[1,X-1]来更加容易的得到答案。

那么我们怎么获得前n个数的满足条件的数呢,首先将B进制数x中的 每一位用a表示为anan-1an-2an-3…a0,然后从第一位an开始,把它分为两部分0-an-1和an,所有的决策都可以由第一部分和第二部分的和组成(图片画横线的部分)。

当我们选第一部分0-an-1的时候,那么第an-1位以及以后的数字我们可以任意选取,(不会超过x),但是因为题目要求只能选0或者1那么先取0的话就是n个数(因为最后一个数的下标为a0)中选出k-last(当前已经选了多少个1)个1的结果,如果取1的话那么就是n个数中选出k-last个1的结果,这部分结果可以用组合数来求得(根据组合数公式C(a,b)=C(a-1,b)+C(a-1,b-1)来获得),但是取1有个前提条件,那么就是an必须大于1(因为如果an等于1的话,那么他是会分到第二部分的)。

这样第一部分就选完了,那么对于第二部分an的时候,如果an不为1,那么根据题意不能选择除了0或者1之外的任意数字,那么直接break退出即可;否则如果为1,那么last就要++(接下来需要的1少一个),然后继续往下走每次计算左边的决策,然后走到最后一位的时候a0如果选0,那么就可以根据判断条件[last=k]是否成立,如果成立结果res++即可;如果选1,那么也会last++,然后因为走到了最后一位,后面没有可以再进行的决策,那么还是根据[last=k]是否成立来使res++。
在这里插入图片描述
大体思路就是这样子的,具体细节可以看看代码:

/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃  	    ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/#include
#include 
#include 
#include 
#include 
#include 
#include
#include
#include
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long 
using namespace std;const int N=1000000+100;
int x,y,k,b;
int s[40][40];//因为如果是二进制位可能会有30位多开了点void cal()//用于计算组合数 
{for(int i =0;i<=40;i++)for(int j =0;j<=i;j++)if(j==0)s[i][j]=1;//i个数中不选也有一种方案else s[i][j]=s[i-1][j]+s[i-1][j-1];
}int dp(int n)
{if(n==0)return 0;//特判,0的时候没有任何一种方案vectorcnt;//用来存储进制转换后的数while(n)cnt.push_back(n%b),n/=b;int res=0;//结果int last=0;//到当前情况已经选了多少个1for(int i =cnt.size()-1;i>=0;i--)//从最高位开始运算{int x=cnt[i];if(x)//如果x大于等于1{res+=s[i][k-last];//i个数中选k-last个1if(x>1){if(k-last-1>=0) res+=s[i][k-last-1];//选1的情况就少了一个1可以选择,//到此左半部分计算完毕break;//因为x大于1的时候右半部分不能得到1,直接退出即可}else{//x为1 的情况last++;//已经选了的1增加if(last>k)break;//如果已经选了1的数量大于k那么也可以直接退出}}if(i==0&&k==last)res++;//走到了a0的情况判断一下是否可以构成一种方案} return res;
}int main()
{cal();cin>>x>>y>>k>>b;cout<

看y总的大概思路就是把这些数按树形结构分成两部分考虑,每一部分的答案根据上一部分获得,反正自己也不是很会,只能尽量写了那么清楚了qwq

上一篇:MyBatis开发详解

下一篇:FJWC2019 Day2 题解

相关内容

热门资讯

微软安卓系统叫什么,Windo... 你知道吗?在科技界,微软这个巨头最近可是搞了个大动作,竟然把目光投向了安卓系统!没错,就是那个我们日...
安卓系统没有最近任务,揭秘无最... 你是不是也遇到了这个问题?安卓系统里怎么就没有“最近任务”这个功能呢?别急,让我来给你详细说说这个事...
安卓系统怎么拒聊天,安卓系统聊... 你是不是也和我一样,有时候手机里聊天软件的消息太多,让人头都大了?别急,今天就来教你怎么在安卓系统里...
下载工资软件安卓系统,高效便捷... 你有没有想过,每个月的工资一到手,是不是就感觉整个人都轻松了呢?但是,你知道怎么轻松地管理你的工资吗...
下载灰灰影音安卓系统,畅享高清... 你有没有想过,一部手机,一部电脑,就能让你随时随地享受高清电影、热门剧集的乐趣?没错,这就是我们今天...
安卓系统是不是中国,中国智慧与... 你有没有想过,那个陪伴你每天刷手机、玩游戏、办公的安卓系统,它是不是中国的“孩子”呢?这个问题听起来...
电脑如果安装安卓系统,探索安卓... 你有没有想过,如果家里的电脑突然决定要换换口味,不再坚守Windows的阵营,而是拥抱安卓系统呢?想...
安卓手机升级苹果系统,体验全新... 你有没有想过,你的安卓手机突然间变成了苹果的忠实粉丝,想要体验一番iOS系统的魅力呢?这可不是天方夜...
安卓系统短信不通知,享受宁静 你是不是也遇到了这个问题?安卓系统短信不通知,是不是让你抓狂?别急,今天就来给你详细解析一下这个让人...
夏普电视非安卓系统,非安卓系统... 亲爱的读者们,你是否曾对夏普电视的非安卓系统感到好奇呢?今天,就让我带你一探究竟,揭开这个神秘面纱背...
安卓系统43适配软件,软件升级... 你有没有发现,你的安卓手机最近是不是有点儿“水土不服”?别急,别急,让我来给你揭秘为什么你的安卓系统...
安卓系统有车载系统吗吗,智能驾... 你有没有想过,当你坐在车里,享受着旅途的悠闲时光,手机上的安卓系统是不是也能派上用场呢?没错,我就要...
安卓8.1系统解锁方法,畅享自... 你有没有想过,你的安卓手机里隐藏着无数的小秘密?比如,解锁安卓8.1系统,就能让你的手机焕发出全新的...
安卓系统怎么打开邮件,安卓系统... 你有没有想过,每天那么多邮件,怎么才能快速打开它们呢?尤其是当你用的是安卓系统手机的时候。别急,今天...
封闭安卓系统安装软件,一步到位... 你有没有想过,为什么你的安卓手机里有些软件只能通过官方渠道安装呢?今天,就让我带你一探究竟,揭开封闭...
小米mipad升级安卓系统,解... 你有没有发现,最近小米Mipad的安卓系统升级可是个大热门呢!这不,我就迫不及待地来和你聊聊这个话题...
哪个安卓系统体验好,揭秘安卓系... 你有没有想过,手机里的安卓系统就像是个大厨,不同的版本就是不同的拿手好菜,有的让你回味无穷,有的却让...
安卓系统开发测试,全方位技术解... 你有没有想过,那个陪伴你每天刷手机、玩游戏、办公的安卓系统,是怎么从无到有,一步步成长起来的呢?今天...
安卓系统怎么查配置,轻松掌握设... 你有没有想过,你的安卓手机里藏着多少秘密?别小看这些配置信息,它们可是了解你手机性能的“小侦探”呢!...
pve下安装安卓系统,PVE环... 你有没有想过,在你的PVE服务器上安装一个安卓系统呢?听起来是不是有点酷炫?想象你的服务器不仅能够运...