最新要闻
- 焦点速讯:黑夜传说演员表_传说演员表
- 全球新动态:比尔·盖茨反击马斯克:暂停AI的发展并不能解决问题
- 每日报道:比亚迪海龙等4款超跑概念图亮相!你觉得哪款最帅?
- 环球讯息:长城汽车:一位新能源砖家 利润高可能是因为新能源卖的差
- 狠人!印度一男子爬火车摸25000伏高压电 瞬间成火球吓坏网友
- 重点聚焦!104MB缓对锐龙7 7800X3D核显无用:鸡血提升不存在
- 【全球新视野】真的有那么好?试完深蓝SL03我明白了
- 天天观点:四年创收20亿美元!微软XGP PC用户突破1500万
- 大神出手!安卓14/骁龙8 Gen2双双被破解:一键ROOT
- 南非一客机驾驶舱惊现剧毒眼镜蛇往人身上爬 飞行员神勇应对:平安降落
- 全球今日讯!石家庄:医师资格考试报名材料即将发放
- 天天观热点:老司机不刹车?特斯拉潮州事故车主不服鉴定 车顶维权女车主:厂商应公开完整数据
- 世界聚焦:为救高烧幼童 高铁破例停车2分钟
- 【独家】你敢体验吗?菲律宾推出网红蟒蛇按摩服务:40元享受30分钟
- AI抢饭碗成真!近500家企业用ChatGPT取代员工:有公司省超10万美元
- 世界头条:苏炳添回应手机从小米换成苹果:合约已到期 旧手机摔坏了
广告
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
天天热讯:数位dp
数位dp
思想
一般来说,题目是要求在区间\([l,r]\)中符合某一种条件的数的个数
(相关资料图)
我们用前缀和的思想考虑,分别求出\([1,r]\)和\([1,l-1]\)中数的个数相减即为所求
这里采用记忆化搜索的方式实现
模板
#include#include#include#define int long long//这是因为数位问题的结果一般比较大,直接使用longlongint dp[N][N][……];//DP数组,第一维代表数的长度,其他维由具体问题决定vectornums;//分解出的每一位数字int len;int dfs(int pos, status, int limit, int zero){ if(pos>len) return //根据status返回结果,不是0就是1; if(!zero && !limit && dp[pos][status]!=-1) return dp[pos][status]; int last = limit ? nums[len-pos-1] : 9; int ans = 0; for(int i=0;i<=last;++i){ ans += dfs(pos-1,newStatus,newLead,limit&&i==last); } if(!zero&&!limit) dp[pos][status] = ans; return ans;}int calc(int n){ if(!n) return //视具体情况 nums.clear(); memset(dp,-1,sizeof dp); while(n) nums.push_back(n%10),n/=10; len = nums.size(); return dfs(0,……)}
说明
\(zero\)表示是否有前导零,当考虑的数是否需要记录和数位中0有关的数时需要前导零标记,无关时可以没有\(zero\)标记
举个例子:假如我们要从 \([0,1000]\) 找任意相邻两数相等的数
显然 \(111,222,888\) 等等是符合题意的数
但是我们发现右端点 \(1000\) 是四位数
因此我们搜索的起点是 \(0000\) ,而三位数的记录都是 \(0111,0222,0888\) 等等
而这种情况下如果我们直接找相邻位相等则 \(0000\) 符合题意而 \(0111,0222,0888\) 都不符合题意了
所以我们要加一个前导0标记
例题1 Windy数
#include#include#includeusing namespace std;int dp[12][12],len;vectornums;int dfs(int pos,int pre, int limit,int zero){if(pos>len-1) return 1;if(!limit&&!zero&&dp[pos][pre]!=-1) return dp[pos][pre];int ans = 0;int res = limit?nums[len-pos-1]:9;for(int i=0;i<=res;i++){if(ipre-2&&!zero) continue;ans += dfs(pos+1,i,limit&&(i==res),!i&&zero);}if(!limit&&!zero) dp[pos][pre] = ans;return ans;}int calc(int n){if(n==0) return 1;memset(dp,-1,sizeof dp);nums.clear();while(n) nums.push_back(n%10),n/=10;len = nums.size();return dfs(0,-2,1,1);}int main(){int a,b;cin>>a>>b;cout<
例题2 手机号码
#include#include#include#define int long longusing namespace std;int f[15][15][15][2][2][2],len; //[位置][前一位][前两位][是否有8][是否有4][是否连续3个] vectornums;int dfs(int pos,bool limit,int pre1,int pre2,bool _8,bool _4,bool _3){if(_8&&_4) return 0;if(pos>len-1) return _3;if(!limit&&f[pos][pre1][pre2][_8][_4][_3]!=-1) return f[pos][pre1][pre2][_8][_4][_3];int ans = 0;int res = limit?nums[len-pos-1]:9;for(int i=0;i<=res;i++){ans+=dfs(pos+1,limit&&(i==res),i,pre1,_8||i==8,_4||i==4,_3||(i==pre1&&pre1==pre2));}if(!limit) f[pos][pre1][pre2][_8][_4][_3] = ans;return ans;}int calc(int n){memset(f,-1,sizeof f);nums.clear();while(n){nums.push_back(n%10);n/=10;}if(nums.size()!=11) return 0;int res = 0;len = nums.size();for(int i=1;i<=nums[len-1];i++){res+=dfs(1,i==nums[len-1],i,0,i==8,i==4,0);}return res;}signed main(){int l,r;cin>>l>>r;cout<
例题3 圆数
#include#include#include#includeusing namespace std;int f[35][35][35],len;vectornums;int dfs(int pos,int sum1,int sum0,int limit,int zero){if(pos>len-1) return sum0>=sum1;if(!limit&&!zero&&f[pos][sum1][sum0]!=-1) return f[pos][sum1][sum0];int ans = 0;int res = limit?nums[len-pos-1]:1;for(int i=0;i<=res;i++){if(zero&&(!i)) ans+=dfs(pos+1,0,0,limit&&i==res,1);else{ans+=dfs(pos+1,sum1+(i==1),sum0+(i==0),limit&&i==res,0); }}if(!limit&&!zero) f[pos][sum1][sum0] = ans;return ans;}int calc(int n){if(!n) return 1;nums.clear();memset(f,-1,sizeof f);while(n) nums.push_back(n%2),n/=2;len = nums.size();int res = 0;res += dfs(0,0,0,1,1);return res;}int main(){int l,r;cin>>l>>r;cout<
例题4 同类分布
#include#include#include#define int long longusing namespace std;int f[20][200][200],len,mod;vectornums;int dfs(int pos,int sum,int st,int limit){if(pos>len-1) return sum==mod&&st==0;if(!limit&&f[pos][sum][st]!=-1) return f[pos][sum][st];int ans = 0;int res = limit?nums[len-pos-1]:9;for(int i=0;i<=res;i++){ans+=dfs(pos+1,sum+i,(10*st+i)%mod,limit&&(i==res));}if(!limit) f[pos][sum][st] = ans;return ans;}int calc(int n){if(!n) return 0;nums.clear();int res = 0;while(n) nums.push_back(n%10),n/=10;len = nums.size();for(mod=1;mod<=9*len;mod++){memset(f,-1,sizeof f);res+=dfs(0,0,0,1);}return res;}signed main(){int a,b;cin>>a>>b;cout<
关键词:
-
当前热文:W1R3S
W1R3S下载地址https: download vulnhub com w1r3s w1r3s v1 0 1 zip安装直接丢到vm中1、主机发现sudonmap-sn10 20
来源:
-
-
-
当前热文:W1R3S
天天热讯:数位dp
今日看点:kill 进程时遇到的一件有意思的事情
焦点速讯:黑夜传说演员表_传说演员表
全球新动态:比尔·盖茨反击马斯克:暂停AI的发展并不能解决问题
每日报道:比亚迪海龙等4款超跑概念图亮相!你觉得哪款最帅?
环球讯息:长城汽车:一位新能源砖家 利润高可能是因为新能源卖的差
狠人!印度一男子爬火车摸25000伏高压电 瞬间成火球吓坏网友
重点聚焦!104MB缓对锐龙7 7800X3D核显无用:鸡血提升不存在
全球热资讯!SpringBoot中如何编写一个优雅的限流组件?
环球今热点:一文快速了解火山引擎 A/B 测试平台
小程序对接三方插件契约锁
【全球新视野】真的有那么好?试完深蓝SL03我明白了
诺基亚E72i手机什么时候上市的?诺基亚E72i手机参数
摩尔庄园怎么获得桑叶?摩尔庄园怎么收获农作物?
龙之谷白屏是怎么回事?龙之谷白屏怎么解决?
天天观点:四年创收20亿美元!微软XGP PC用户突破1500万
大神出手!安卓14/骁龙8 Gen2双双被破解:一键ROOT
南非一客机驾驶舱惊现剧毒眼镜蛇往人身上爬 飞行员神勇应对:平安降落
闲鱼曝光率突然下降怎么办?闲鱼曝光率怎么提高?
闲鱼对方被处置能回复消息吗?闲鱼对方被处置能正常发货吗?
全球热文:某公司技术经理媚上欺下,打工人应怼尽怼,嘤其鸣兮,求其友声!
焦点讯息:用上这几种.NET EF Core性能调优,查询性能飙升
全球今日讯!石家庄:医师资格考试报名材料即将发放
天天观热点:老司机不刹车?特斯拉潮州事故车主不服鉴定 车顶维权女车主:厂商应公开完整数据
世界聚焦:为救高烧幼童 高铁破例停车2分钟
【独家】你敢体验吗?菲律宾推出网红蟒蛇按摩服务:40元享受30分钟
AI抢饭碗成真!近500家企业用ChatGPT取代员工:有公司省超10万美元
世界头条:苏炳添回应手机从小米换成苹果:合约已到期 旧手机摔坏了
【世界快播报】K8S学习圣经6:资源控制+SpringCloud动态扩容原理和实操
环球热议:顶象受邀加入“数字政府网络安全产业联盟”
Blender插件:Muscle System
天天短讯!两单REIT业绩说明会首次在上海证券交易所成功举办
世界热消息:招商银行信用卡网银(中国邮政储蓄余额查询)
焦点精选!什么情况?马自达要给CX-50征集中文名:越境、行也、俊驰、览乐你投谁
全球即时看!工资六千的岗位面试了6轮!女生发视频吐槽
世界观点:TikTok回应英国政府巨额罚款:乐见罚款大幅度降低
李国庆称羡慕周鸿祎离婚:没争夺控制权 你就乐吧
嫦娥五号采集月壤立功:中国科学家刷新月球死亡时间
环球资讯:EasyMR 安全架构揭秘:如何管理 Hadoop 数据安全
小程序容器助力组装移动银行超级APP
【环球报资讯】GPS北斗卫星时钟服务器在飞机场内网中的应用
和讯个股快报:2023年04月06日 紫天科技(300280),该股K线呈现“乌云盖顶”形态
头条:24小时长效锁水 妮维雅男士精华露39.9元狂促:送洁面乳50gx2
车市“价格战”开打一月:新车销量未回暖 二手准新车被坑惨
速递!杨元庆:联想过去三年营收增长1100亿 PC业务还是第一
焦点快报!游客开车陷进沙滩:拖车开口要价5千 待会涨潮至少要5万
环球动态:最快6月2日早就能玩到!《暗黑4》全球解锁时间公开
世界视点!清明时节祭祖扫墓 “小三通”客运航线往来忙碌
每日短讯:全网最详细中英文ChatGPT-GPT-4示例文档-会议笔记文档智能转摘要从0到1快速入门——官网推荐的48种最佳应用场景(附python/node.
世界即时:Linux在游戏界的口碑树立
前端设计模式——MVC模式
福岛核电站1号机组底座受损严重!日本民众集会反对核污水排海
环球新消息丨特斯拉发布“宏图计划3”完整文件 10万亿美元改变地球
形似“摄魂怪” 澳大利亚悉尼惊现破片云:颜色漆黑、预示狂风暴雨
全球今热点:Redmi Note 12 Turbo好评率99%!卢伟冰:得到极大认可 把竞品甩在后面
快看点丨划时代产品!特斯拉新款小型电动汽车公布 目标销量4200万辆
世界速读:我2022年8月18月去医院做牙齿矫正,但是我只交了定金,后续也没拿到牙套
SpringBoot如何进行限流,老鸟们还可以这样玩!
环球微资讯!Podman Compose 新手指南
环球今热点:美国ADP就业数据不及预期 暗示劳动力需求降温
焦点快报!深赛格:融资净买入132.4万元,融资余额1.03亿元(04-04)
天天报道:中国为何未研制出ChatGPT?中科院包云岗:需要优秀技术团队、雄厚资金
苏炳添用iPhone 14引热议 本人回应:与小米合约到期 手机摔坏才换
大妈捡手机要好处费2包烟见面变500元被吐槽:你捡到会痛快归还吗?
焦点速读:NV不愁卖!2023年PC游戏硬件市场继续萎缩:AMD、Intel显卡要打对折卖
每日资讯:沪广深去年公积金个贷降两成 今年超60地优化公积金政策
天天速递!科技伦理审查提速 AI“变坏”设防
天天最资讯丨核污水将倒入大海 降低水产品辐射分析精度!日本1.8亿粒扇贝不明原因死亡
世界快看:64位才是王道!《英雄联盟》13.7版本今日更新:32位Win系统续一条命
汽车仪表盘显示感叹号加个圆圈_汽车仪表盘显示感叹号
【天天报资讯】读SQL进阶教程笔记10_HAVING下
Python 开发环境安装
世界热文:海盗船192GB DDR5内存套装开卖:带上“光污染” 7699元!
天天百事通!研究了2600多篇爆仓文学后 我好像搞懂人是怎么变赌狗的了
天天看点:无数人的童年回忆:重制后把我裤子都感动湿了
标准版也要有高刷了!iPhone全系列或于2025年引入LTPO技术
【环球时快讯】穿越之汉武帝
世界微速讯:彻底崩了!AI遭全球“围剿” A股咋应对?超9000人联名“封杀” 巴菲特又要“抄底”?
【打怪升级】【jvm】关于jvm内存模型及GC调优
【当前热闻】房东称闰二月要多交1个月房租 网友:这是住在月亮上吗?
ChatGPT需要1万张NVIDIA A100显卡 国内仅有6家公司做到
全球快消息!杭州一男子坐地铁自带沙发 怎么过的安检?地铁回应
焦点热讯:Lambda
TVM Deploy Runtime[施工中]
环球精选!股债二八平衡策略
世界实时:20年来最优秀游戏处理器!AMD锐龙7 7800X3D首发评测:大幅超越i9-13900KS
周鸿祎离婚给前妻90亿 李国庆羡慕:没争夺控制权 他就乐吧
RTX 3060登顶Steam神卡 AMD显卡被黑?竟是国内玩家的锅
全球快资讯丨“索要千万逼死老公案”五年后一审宣判:妻子翟欣欣退还男方上千万财产
环球热头条丨我的第一个项目(九) :飞机大战Vue版本塞到主页
Unity开发Hololens2—环境配置
设计模式(三十二)----综合应用-自定义Spring框架-自定义Spring IOC-自定义Spring IOC总结
CS50-Python实验3,4
天天精选!00后都开始立遗嘱了:微信号、QQ号、游戏账号成热门虚拟财产
《他是谁》烂尾 编剧疑似甩锅剧本总监:感谢你把剧本改成这
世界快讯:莱万:若留拜仁或会失去踢球的乐趣 在巴萨除了进球我有不同角色
【全球热闻】上映25周年纪念!《泰坦尼克号》4K重映版票房破2000万
每日热点:全球首例真人状告机器人!澳大利亚一市长准备告ChatGPT诽谤
Cesium 案例(二)Web MapTile Service with Time