题目分析Impecunia\texttt{Impecunia}Impecunia政府通过发行Bonus Bonds\texttt{Bonus Bonds}Bonus Bonds来筹集资金。债券编号原本是777位数字前面加上111位区域代码111–999后来扩展为101010位数字其中从左向右第333位即从右向左第888位表示区域代码。中央区域的代码为000并且中央区域的编号从000000000100000000010000000001开始不能全为000。每月每个区域独立抽奖。抽奖设备会生成101010个数字流每个流对应一个数位。第111个中奖号码由每个流的第111位数字组成第222个中奖号码由每个流的第222位数字组成依此类推。设备需要调整每个流的数字分布使其与实际已售债券在该数位上的数字分布一致。题目要求对于每个输入行包含下一个待售债券的101010位编号以及一个目标数位位置ppp1≤p≤101 \le p \le 101≤p≤10输出一个101010行的表格第iii行i0,1,…,9i 0,1,\dots,9i0,1,…,9表示在该数位位置上数字iii出现的总次数。解题思路核心问题已知从起始编号到N−1N-1N−1号的所有有效债券NNN为下一个待售编号统计这些编号在指定数位111索引从左向右上各数字出现的次数。关键处理编号的结构输入是101010位数字但第333位是区域代码需要将其移除才能得到真正的编号范围。例如输入4810000000第333位是1真正的编号是481000000999位。起始编号对于非中央区域区域代码111–999编号从000开始因为原方案中区域代码非零编号可以从000开始。对于中央区域区域代码000编号从000000000100000000010000000001开始即111。计数方法采用数位统计的方法。对于目标数位ppp如果p3p 3p3即区域代码位该位在所有有效编号中都是固定的区域代码值因此该数字出现次数就是有效编号的总数其他数字出现000次。如果p≠3p \neq 3p3则需要计算在该数位上每个数字出现的次数。对于非区域代码位将其在原999位编号中的索引idxidxidx计算如下若p3p 3p3则idxp–1idx p – 1idxp–1若p3p 3p3则idxp–2idx p – 2idxp–2然后利用数位统计公式计算每个数字iii000–999在[0,N−1][0, N-1][0,N−1]范围内第idxidxidx位上出现的次数。排除无效编号中央区域的有效编号从111开始因此需要减去数字000多算的一次当i0i 0i0且区域代码为000时总数减111。算法复杂度对于每个输入只需O(10×位数)O(10 \times \text{位数})O(10×位数)的时间非常高效。代码实现// Bonus Bonds// UVa ID: 182// Verdict: Accepted// Submission Date: 2017-07-20// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string nextBondNumber,desiredPosition;voidcountTimes(){// 获取区域代码第3位和目标数位位置intregionnextBondNumber[2]-0,positionstoi(desiredPosition);// 移除区域代码位得到9位有效编号字符串nextBondNumber.erase(nextBondNumber.begin()2);longlongnumberstoll(nextBondNumber);// 特殊情况没有有效债券if(number0||(number1region0)){for(inti1;i10;i)coutrightsetw(11)0endl;return;}// 将 N-1 转换为数字向量便于逐位处理vectorintbn;for(autoc:to_string(number-1))bn.push_back(c-0);while(bn.size()nextBondNumber.length())bn.insert(bn.begin(),0);// 统计 0-9 每个数字在目标数位上出现的次数for(inti0;i9;i){longlongtotal0;// 情况1目标数位是区域代码位第3位if(position3){if(iregion)totalnumber;}else{// 计算在9位编号中的索引位置intidxposition3?position-2:position-1;if(idx0){// 高位部分贡献for(intj0;jidx;j)totalbn[j]*pow(10,7-j);}// 当前位小于 bn[idx] 时低位全排列if(ibn[idx])totalpow(10,bn.size()-idx-1);// 当前位等于 bn[idx] 时低位取 tail1if(ibn[idx]){longlongtail0;for(intjidx1;jbn.size();j)tailtail*10bn[j];totaltail;total1;}}// 中央区域需要排除全0编号if(i0region0)total-1;coutrightsetw(11)total\n;}}intmain(){intcases0;while(cinnextBondNumberdesiredPosition){if(desiredPosition0)break;if(cases)cout\n;countTimes();}return0;}总结本题的核心在于理解债券编号的特殊结构区域代码嵌入在数位中以及数位统计的技巧。通过将问题分解为101010个独立的数位统计子问题利用数学公式O(1)O(1)O(1)计算每个数字的出现次数避免了枚举所有编号的低效做法。中央区域需要特殊处理起始编号为111而非000这一细节。