最新要闻
- 焦点快播:20亿的交易被华为反对 没任何可能合作 诺基亚坚持要卖鼎桥母公司股权
- 黄仁勋主持 台北电脑展NVIDIA发布会敲定!RTX 4060 Ti/4060要来了
- 焦点消息!《塞尔达传说:王国之泪》终极预告发布:短发公主绝美 盖侬真身登场
- 天天微资讯!仿真-定向耦合器
- 速讯:AMD发布RDNA3架构Radeon Pro W7000系列专业显卡:AI性能提升2.7倍、满血3999美元
- 天天播报:比“500万内最好的SUV”更好!魏牌蓝山上市:27.38万元起
- 当前聚焦:纯白机身美翻了!影驰RTX 4070星曜OC图赏
- 为什么今年沙尘暴突然这么严重?40多年植树造林白干了?
- 环球播报:79888元!大疆Inspire 3发布:全画幅8K电影无人机
- 葵花药业实控人杀妻案4年后:两女儿接班
- 【世界独家】大疆悟3曝光:吊着一台摄像机 支持8K 75fps视频录制
- 每年减少6吨补给 我国空间站氧气100%再生:已达世界领先水平
- 环球今日报丨强力透气 森马旗下棉致男士冰丝休闲裤34.5元
- 每日关注!双碳ETF: 招商基金管理有限公司关于旗下基金投资关联方承销证券的公告
- 热讯:苹果寻觅中国制造之外新选择:正推动将MacBook转到泰国组装
- 今日看点:安卓之光未发先火!超1000位米粉下单小米13 Ultra
广告
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
1811 E Living Sequence 两种解法
(资料图)
思维 进制转换 数位DP 无前导0 T3Problem - 1811E - Codeforces
题目大意
从一个不含有数字4的递增序列中找第k个数并输出。如 \(1,2,3,5,6,7,8,9,10,11,12\), \(k = 4\) 时输出 \(5\)。
思路1
有一个巧妙的解法:考虑这个问题, 从一个没有限制的从1开始的递增序列找出第k个数, 显然就是十进制的k。而这里则可以定义新的进制为 "012356789" 9进制, 那么k对应的就是这个特殊的九进制数, 我们只需要把它转换为十进制就行。
二转十:
while(k)ans += k % 2, k /= 2;
九转十:
while(k)ans += k % 9, k /= 9;
代码1
#include #include #include using namespace std;using LL = long long;int a[20];int cnt = 0;int main(){ cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); string s = "012356789"; int T; cin >> T; while (T--) { LL k; cin >> k; cnt = 0; while (k) a[cnt++] = s[k % 9] - "0", k /= 9; for (int i = cnt - 1; i >= 0; i--) cout << a[i]; cout << endl; }}
思路2
也可以考虑数位DP, 定义 \(f(i,j)\) 为长度为i, 且最高位为j的数, 可以写出这样的初始化函数来得到 \([1,i]\) 的满足条件的数的个数:
void init(){ for (int i = 0; i <= 9; i++) if (i != 4) f[1][i] = 1; for (int i = 2; i <= N - 1; i++) { for (int j = 0; j <= 9; j++) { if (j == 4) continue; for (int k = 0; k <= 9; k++) f[i][j] += f[i - 1][k]; } }}
然后再实现查找前缀和 \([1,num]\) 的满足条件的数的个数, 题目中的 \(k\) 最大为 1e12, 直接二分结果, 找最左边且 \(dp(mid) = k\) 的值就是最终结果。
记得要处理前导0, 方法是在首尾不加上0开头的部分, 最后再加一遍所有长度小于 num.size() 的部分。
代码2
#include #include #include #include #include #include using namespace std;const int N = 17;typedef long long ll;const ll INF = 1e17;ll f[N][10];void init(){ for (int i = 0; i <= 9; i++) if (i != 4) f[1][i] = 1; for (int i = 2; i <= N - 1; i++) { for (int j = 0; j <= 9; j++) { if (j == 4) continue; for (int k = 0; k <= 9; k++) f[i][j] += f[i - 1][k]; } }}ll dp(ll x){ if (!x) return 0; vector nums; while (x) nums.push_back(x % 10), x /= 10; ll res = 0; for (int i = nums.size() - 1; i >= 0; i--) { int x = nums[i]; for (int j = (i == nums.size() - 1); j < x; j++) res += f[i + 1][j]; if (x == 4) break; if (!i) res++; } for (int i = 1; i <= nums.size() - 1; i++) for (int j = 1; j <= 9; j++) res += f[i][j]; return res;}int main(){ init(); int T; cin >> T; while (T--) { ll k; cin >> k; ll l = -1, r = 1e13; while (l != r - 1) { ll mid = l + r >> 1; if (dp(mid) < k) l = mid; else r = mid; } cout << r << endl; } return 0;}
关键词:
-
天天热门:容器操作,应用部署,迁移与备份,Dockerfile
容器操作,应用部署,迁移与备份,Dockerfile上节回顾 1docker启动,停止,查看状态命令systemctlstartdockersystemctlstopdocker
来源: 1811 E Living Sequence 两种解法
ChatGPT进化,人性消失,究竟是好是坏?
每日聚焦:第137篇:重学ES6模块化
天天热门:容器操作,应用部署,迁移与备份,Dockerfile
焦点快播:20亿的交易被华为反对 没任何可能合作 诺基亚坚持要卖鼎桥母公司股权
黄仁勋主持 台北电脑展NVIDIA发布会敲定!RTX 4060 Ti/4060要来了
焦点消息!《塞尔达传说:王国之泪》终极预告发布:短发公主绝美 盖侬真身登场
天天微资讯!仿真-定向耦合器
今日报丨java 处理常量字符串过长 & springboot 项目读取 resouces 文件夹下的文件内容
ORACLE还原恢复启动时数据库报ORA-00704, ORA-00604, ORA-00904
世界速读:linux环境下安装Docker
世界关注:百度松果菁英班--oj赛(第二次)
面试题百日百刷-kafka篇(三)
速讯:AMD发布RDNA3架构Radeon Pro W7000系列专业显卡:AI性能提升2.7倍、满血3999美元
天天播报:比“500万内最好的SUV”更好!魏牌蓝山上市:27.38万元起
当前聚焦:纯白机身美翻了!影驰RTX 4070星曜OC图赏
为什么今年沙尘暴突然这么严重?40多年植树造林白干了?
环球播报:79888元!大疆Inspire 3发布:全画幅8K电影无人机
葵花药业实控人杀妻案4年后:两女儿接班
【世界独家】大疆悟3曝光:吊着一台摄像机 支持8K 75fps视频录制
每年减少6吨补给 我国空间站氧气100%再生:已达世界领先水平
环球今日报丨强力透气 森马旗下棉致男士冰丝休闲裤34.5元
当前热点-夜莺监控V6初探
每日关注!双碳ETF: 招商基金管理有限公司关于旗下基金投资关联方承销证券的公告
热讯:苹果寻觅中国制造之外新选择:正推动将MacBook转到泰国组装
今日看点:安卓之光未发先火!超1000位米粉下单小米13 Ultra
巴菲特对苹果推崇至极!出1万美元买不走你的iPhone但能买走你的福特车
当前快报:新能源厂商销量榜 长城、五菱、小鹏汽车全部接近腰斩
环球焦点!飞腾CPU走出国门 非洲电厂将用上“中国芯”
每日关注!Java GC基础知识
天天微资讯!KMP(字符串匹配算法)
焦点快报!银行发现7位数存款5年未动急寻人:联系电话是空号
每日热文:RTX 4090与RTX 3080 Ti移动旗舰显卡大PK:没想到性能差距巨大
自动驾驶为啥这么难!技术问题?还是方向错了?
每日视点!T-1000未来或成真!《终结者》之父:AI太强可以造成世界末日
焦点消息!被狗抓破是否会得狂犬病上热搜:博主“科普”网友纷纷不认账
当前热门:三分钟完成静态网站托管
每日视讯:ChatGPT吃我饭,还要掀我碗
cookies、sessionStorage与localStorage在Vue中的使用
有关拦截器拦截指定的url并作出处理返回数据
环球热点评!皇马这批人如果拿到6个欧冠,历史地位也没变化?受害者只有C罗?
环球短讯!华为5G回来了?余承东体验AITO问界M5智驾版:重大更新引人遐想
疯狂白菜价 DDR5正式跌破百元 国产枭鲸8GB内存只要99.9元
全球观热点:表现持平GPT-4!知乎“知海图AI”投入内测
《终结者》之父卡梅隆:AI太厉害将能造成世界末日
环球速读:云南万人大型泼水现场互送祝福:欢度泼水节
全球即时:全栈混合云综合架构方案研究和落地
环球观热点:详解GaussDB(DWS)的query_band负载识别与应用
快看:零基础快速入门WebRTC:基本概念、关键技术、与WebSocket的区别等
【世界时快讯】Java集成工作流审批机制,多个项目实际运用优化版本(干货)
世界快播:Natasha入门(一)
环球观热点:恒生指数13日收涨0.13% 生物医药行业领涨
焦点报道:许昌市东城区:普法宣传进校园 精心护苗筑平安
【全球时快讯】NVIDIA最新调查:80%的RTX 40系显卡用户会启用光追和DLSS
【天天播资讯】侧透玻璃机箱!微星海皇戟AS台式机上新:i7+RTX 4070
世界新消息丨同跑硬件杀手《赛博朋克2077》 RTX 4080与RTX 4090有多大差距?
世界今日讯!Win掌机不用指头戳屏幕了!Win12有望加入“掌机模式”
世界微动态丨下周一!国内油价预计涨0.44元/升 或创今年最大涨幅
尼尔森IQ:中国消费市场回暖 绿色变革赋能品牌可持续增长
天天速读:MegEngine 使用小技巧:使用 Optimizer 优化参数
每日动态!图片压缩&视频截取
全球观速讯丨Mac | iOS | Windows:安装Stable diffusion教程
世界短讯!科创板收盘播报:科创50指数低开低走跌2.59% 软件服务及半导体股跌幅居前
世界热讯:简历上写QQ邮箱会掉分吗引热议 网友:邮箱也分三六九等?
全焦段光学覆盖!小米13 Ultra影像参数公布:1+3黄金组合
环球消息!4999元起 荣耀MagicBook 14 2023笔记本发布:5项世界第一
天天即时:优酷回应非会员遇3000多秒广告:bug已修复 是文案显示问题
iPhone 15 Pro固态按键设计临时改了!只因难度太大
天天最资讯丨动态代理与Spring AOP
在LINQPad中使用FreeSql查询数据库
minio分片上传
12函数进阶
环球快看点丨[Docker]Namespace与Cgroups
快看:本周最火AutoGPT!GitHub3.6万+标星:解决复杂任务全程无需人类插手
环球微速讯:性能升级 13代酷睿来了? 华为MateBook笔记本新品即将发布
曾力推每天睡4小时 张朝阳建议年轻人别睡懒觉不要熬夜
每日动态!李书福抢跑马斯克发小钢炮!冰箱彩电大沙发全标配:理想直呼内行
【环球热闻】售价高达15000元!宾得专为黑白摄影推出K-3 Mark III Monochrome
金色的草地课文朗读音频_金色的草地课文
焦点精选!论结构化、系统性的学习
【天天热闻】RocketMQ是是如何管理消费进度的?又是如何保证消息成功消费的?
【天天聚看点】C# 根据前台传入实体名称,动态查询数据
每日关注!电商流量分析怎么做?试试这款数据工具 DataLeap!
Intel突然杀死服务器整机业务!新CEO连砍十余刀挽救亏损
马保国直播带货现演“闪电五连鞭”:销量惨淡 网友只看不买
手把手教你如何免费Midjourney Adobe FireFly AI绘图—Window本地快速部署stable diffusion AI绘图及使用指南(小白
克里克森_克里克拉克
每日速递:日本部分地区出现大量黄沙:能见度不足10公里
环球热点!高颜值!关晓彤晒华为nova 11:本月发
每日资讯:开启影像光学新时代!小米13 Ultra搭载全焦段5000万像素徕卡四摄
真反向虚标!实测比亚迪秦PLUS EV冠军版:标610开出646.5
5.98万起真不贵!五菱缤果上市两周狂卖10000台:再成爆款
【3D建模工具】上海道宁与McNeel为您提供强大的专业3D造型软件
环球快资讯丨学系统集成项目管理工程师(中项)系列04c_项目管理一般知识(下)
【大兴调查研究】临夏税务:“把脉问诊”助企纾困
今日热闻!新款特斯拉Model 3实车首曝:大灯更精神、颜值再提升
焦点短讯!张艺谋:《满江红》票房让我很意外 20亿就是伟大胜利
观热点:美曾通报生物实验室感染病毒的小白鼠逃了:去年还发生实验猴逃窜
世界快看:5.58万起 五菱荣光新卡上市:2.0L动力、3.3米货厢
当前看点!微信推送8.0.35测试版:和Android 5.0说再见