P1617 爱与愁的一千个伤心的理由【洛谷算法习题】

P1617 爱与愁的一千个伤心的理由网页链接P1617 爱与愁的一千个伤心的理由题目背景本道题目隐藏了两首歌名找找看哪~~~《爱与愁的故事第一弹·heartache》第二章。经历了心痛后爱与愁大神不行了。题目描述月落乌啼问爱与愁大神为什么爱与愁大神写了一个数字n nnn ≤ 9999 n \le 9999n≤9999说翻译成英语就知道为什么了。月落乌啼接过这个数字后本想翻译成英语但是班主任叫他去帮个忙。他想尽快知道答案于是这个艰巨的任务就拜托你了。标准美式英语仅在末两位 $ \le 10$ 时加and且没有连字符。输入格式只有一行一个数n nnn ≤ 9999 n \le 9999n≤9999输出格式一行英文表示n nn翻译成英语的答案。输入输出样例 #1输入 #15208输出 #1five thousand two hundred and eight输入输出样例 #2输入 #25280输出 #2five thousand two hundred eighty输入输出样例 #3输入 #35000输出 #3five thousand输入输出样例 #4输入 #45028输出 #4five thousand and twenty eight说明/提示输出行初不大写。按标准美式英语输出即两个非零的数中间没零则不加and行末无句号。解题思路本题是数字转英文单词的模拟题需要根据美式英语规则将一个不超过 9999 的整数翻译成对应的英文表达。核心在于处理千位、百位、十位、个位的拼接以及特殊连接词and的使用条件。1. 问题等价转化数字范围输入为整数n nn且0 ≤ n ≤ 9999 0 \le n \le 99990≤n≤9999。可直接作为字符串读入逆序后方便按位处理。英文表达规则数字0 00单独输出zero。千位数字后接thousand百位数字后接hundred。十位为2 ∼ 9 2\sim92∼9时使用twenty、thirty等词十位为1 11时与个位组合成ten、eleven等特殊词十位为0 00时直接跳过。个位为1 ∼ 9 1\sim91∼9时输出对应单词个位为0 00且十位非0 00时不输出个位。and的添加规则标准美式英语当存在更高位千位或百位且较低两位需要表达时通常需要使用and连接。具体判断若百位为0 00但十位或个位不为0 00且千位存在则在千位后添加and。若百位不为0 00十位为0 00个位不为0 00则在百位后添加and。其他情况不加and。例如5028→ five thousandandtwenty eight5208→ five thousand two hundredandeight5280→ five thousand two hundred eighty不加and。2. 算法实现字符串预处理读入数字字符串s若长度为1 11且为0则直接输出zero。否则将字符串反转存入r使r[i]对应原数字从低位开始的第i ii位0 00个位1 11十位2 22百位3 33千位。从高位到低位遍历i len − 1 → 0 i \text{len}-1 \to 0ilen−1→0千位与百位i 1 i 1i1若当前位非零输出对应数字单词和单位thousand或hundred。百位特殊处理i 2 i 2i2若百位为0 00且后面两位十位或个位中有非零则输出and用于连接千位和后面的数字。十位处理i 1 i 1i1若十位为0 00当个位和百位都非零时输出and例如5208 52085208中的百位2 22和个位8 88。若十位非零且不为1 11输出对应的twenty~ninety单词。若十位为1 11直接输出对应的ten~nineteen单词由于已覆盖个位输出后即可结束。个位处理i 0 i 0i0若个位非零输出对应单词。输出格式各单词之间用空格分隔行末无多余空格首字母不需要大写。3. 复杂度分析时间复杂度O ( L ) O(L)O(L)其中L LL为数字位数L ≤ 4 L \le 4L≤4常数级。空间复杂度O ( 1 ) O(1)O(1)仅使用几个预定义数组和变量。总结本题通过字符串反转将数字各位与单位数组索引对齐按从高位到低位的顺序依次输出并根据题目规定的美式英语and使用条件进行判断。整个模拟过程清晰分支简单适合直接实现。代码简要说明预定义数组a[10]数字0 ∼ 9 0\sim90∼9的英文单词索引0 00为空。b[4]单位数组b[2]hundred,b[3]thousand。c[10]十位2 ∼ 9 2\sim92∼9的英文单词。d[10]数字10 ∼ 19 10\sim1910∼19的英文单词。主流程读入字符串s特判单个字符0。反转得到r从高位向低位遍历。根据i的值分别处理千位/百位、十位、个位并在适当位置输出and。遇到十位为1 11时直接输出 teens 单词并返回避免重复输出个位。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;string a[10]{,one,two,three,four,five,six,seven,eight,nine};string b[4]{,,hundred,thousand};string c[10]{,,twenty,thirty,forty,fifty,sixty,seventy,eighty,ninety};string d[10]{ten,eleven,twelve,thirteen,fourteen,fifteen,sixteen,seventeen,eighteen,nineteen};intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s;cins;if(s.size()1){if(s[0]0){coutzero;return0;}couta[s[0]-0];return0;}string rs;reverse(r.begin(),r.end());for(ll is.size()-1;i0;i--){if(i1r[i]0){couta[r[i]-0] b[i] ;}if(i2){if(r[i]0(r[1]!0||r[0]!0))coutand ;}if(i1){if(r[i]0){if(r[0]!0r[2]!0)coutand ;}else{ll xr[i]-0;if(x!1){coutc[x] ;}else{xr[0]-0;coutd[x] ;return0;}}}if(i0)couta[r[i]-0];}return0;}