小红的数字拆解【牛客tracker 每日一题】-北京尧图网络

小红的数字拆解时间限制1秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一个偶数她希望你将其切割成尽可能多的偶数。你能帮帮她吗输入描述一个偶数x xx。1 ≤ x ≤ 10 10 5 1≤x≤10^{{10}^5}1≤x≤10105输出描述输出若干行从小到大输出每个偶数。示例1输入1024输出2 4 10说明拆分成 10 2 4 10241024三个偶数。示例2输入999999999999999999999999990输出999999999999999999999999990示例3输入202020输出0 0 0 2 2 2解题思路本题是贪心切割字符串排序的模拟题核心是利用偶数的末位判定特性通过最短分段策略得到最多的偶数段再按大数规则排序输出。1. 最优切割策略一个数是偶数当且仅当它的末位是偶数数字0、2、4、6、8。要切割出最多的偶数段就要让每一段尽可能短每个偶数数字单独作为一段的末尾前面仅拼接连续的奇数数字。这样总段数等于原数中偶数数字的个数达到理论上限每段至少包含一个偶数数字不可能更多。2. 字符串分割实现从左到右遍历输入字符串遇到连续奇数时继续向后延伸直到找到第一个偶数数字。将起点到该偶数的闭区间作为一个切割段存入结果列表。从偶数的下一个位置继续重复上述过程直到遍历完成。输入保证为偶数因此末尾一定是偶数分割不会有剩余字符。3. 大数排序规则由于数字长度可达10 5 10^5105位无法转为整型比较采用字符串比较规则长度优先位数更短的数数值一定更小。字典序次之长度相同时按字符字典序从小到大排列对应数值从小到大。4. 复杂度分析分割过程一次线性遍历时间复杂度O ( L ) O(L)O(L)L LL为数字长度。排序过程设段数为k kk最多为L LL排序时间复杂度为O ( k log ⁡ k ) O(k \log k)O(klogk)单次比较最坏为O ( L ) O(L)O(L)整体可在1秒内完成。总结核心逻辑以每个偶数数字为分段结尾、前置连续奇数的贪心策略得到最多段数再按「长度优先、字典序为辅」的规则对所有段从小到大排序逐行输出。关键操作连续奇数匹配偶数结尾的分段方式、字符串大数比较排序、超长数字的纯字符串处理。效率保障分段仅需一次遍历排序复杂度可控完全适配十万位级别的输入规模。代码简要说明分段逻辑双指针i、j从左向右遍历j从i开始向后跳过所有奇数直到遇到偶数。将区间[i, j]作为一个分段存入向量v随后i跳到j1继续分割。排序比较函数先比较两段的长度通过下标差间接比较相对大小与实际长度一致短段在前。长度相同时逐位比较字符字典序小的段排在前面。输出结果按排序后的顺序遍历所有分段逐位输出对应字符每个分段占一行。输入优化关闭流同步并解绑 tie提升超长字符串的读取与输出效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s;cins;vectorpllv;for(ll i0,j0;i(ll)s.size();){ji;while(j(ll)s.size()((s[j]-0)%21))j;v.push_back({i,j});ij1;}sort(v.begin(),v.end(),[](pll x,pll y)-bool{if(x.second-x.first!y.second-y.first)returnx.second-x.firsty.second-y.first;for(ll k0;kx.second-x.first;k){if(s[kx.first]!s[ky.first])returns[kx.first]s[ky.first];}returnfalse;});for(ll i0;i(ll)v.size();i){for(ll jv[i].first;jv[i].second;j)couts[j];cout\n;}return0;}

小红的数字拆解【牛客tracker 每日一题】

相关推荐

零基础单片机开发入门系列：8天从裸机开发到打通RTOS

MLX框架入门：为什么Inkling-mlx-2bit是Apple Silicon的最佳选择

GripMock安全最佳实践：保护你的Mock服务器免受攻击

更多资讯

STM32H743双核实战指南：480MHz性能落地的关键陷阱与决策逻辑

离线可用的软考机考模拟系统：技术选型与提分实践

ruflo：规则驱动的流程引擎如何实现动态路由与规则集解耦

直流减速电机PI闭环控制实战：从原理到参数整定

棒板电极空气电晕放电仿真：从电场建模到击穿电压预测

ITIL 4迁移的五大隐形陷阱：从价值流到数据治理的落地指南

今日更新

在S3C2410上移植Nucleus RTOS：启动、驱动与实时性调优实战

2026年Turnitin降重降AI二合一红黑榜：能过和别碰

2026期刊投稿AI写作工具实测：6款打分谁更值得用

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？