小红的数字拆解时间限制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;}