P1555 尴尬的数字 Awkward Digits B网页链接P1555 尴尬的数字 Awkward Digits B题目背景Bessie 刚刚学会了不同进制数之间的转换但是她总是犯错误因为她的两个前蹄不能轻松的握住钢笔。题目描述每当 Bessie 将一个数转换成新的进制时她总会写错一位数字。例如她将14转化成2 22进制数正确的结果是1110但她可能会写成0110或1111。Bessie 从不会意外地增加或删减数字所以她可能会写出以0开头的错误数字。给出 Bessie 转换后N NN的2 22进制形式和3 33进制形式请计算出N NN的正确数值用十进制表示。N NN可能会达到10 9 10^9109输入数据保证解的存在唯一性。输入格式第一行N NN的2 22进制表示有一位是错误的数字。第二行N NN的3 33进制表示有一位是错误的数字。输出格式仅一行N NN的正确数值。输入输出样例 #1输入 #11010 212输出 #114解题思路本题利用暴力枚举纠错的思想。已知原数N NN的二进制和三进制表示各恰好有一位写错在N ≤ 10 9 N \le 10^9N≤109的限制下位数极少可直接枚举所有可能的纠错组合找出唯一使两个进制转换结果相等的数。1. 问题等价转化输入两个字符串B BB错误的二进制和T TT错误的三进制。纠错方式二进制位只有0 00和1 11写错一位意味着将该位的值取反0 ↔ 1 0 \leftrightarrow 10↔1。三进制位有0 , 1 , 2 0,1,20,1,2写错一位意味着该位的正确值可能是另外两个数字之一。目标对于每一对可能的纠错方案即改变二进制的一位、改变三进制的一位计算纠正后的二进制值X XX和三进制值Y YY若X Y X YXY则该值就是正确的N NN。2. 算法实现读入并解析将二进制字符串B BB和三进制字符串T TT转换为数字数组方便逐位修改。双重枚举遍历二进制串的每一位i ii将该位取反0变11变0。遍历三进制串的每一位j jj记录该位原始值x xx。依次尝试将该位改为另外两个数字k ∈ { 0 , 1 , 2 } ∖ { x } k \in \{0,1,2\} \setminus \{x\}k∈{0,1,2}∖{x}。对每次修改后的二进制数组和三进制数组分别按权展开计算十进制值a n s 2 ans2ans2和a n s 3 ans3ans3。若a n s 2 a n s 3 ans2 ans3ans2ans3则找到答案输出并结束程序。恢复三进制位为原始值x xx。恢复二进制位再次取反还原。输出找到的相等值即为正确数字N NN。3. 复杂度分析位数N ≤ 10 9 N \le 10^9N≤109二进制最多30 3030位三进制最多20 2020位。枚举量最多30 × 20 × 2 ≈ 1200 30 \times 20 \times 2 \approx 120030×20×2≈1200次检查每次检查需要O ( 位数 ) O(位数)O(位数)计算十进制值总操作数极小完全可以瞬间完成。总结利用错误只有一位且进制转换唯一匹配的性质暴力枚举二进制和三进制的所有纠错方案计算并比较十进制值简洁且高效。代码简要说明输入处理用scanf读取两个字符串并将字符转换为数字0减0得到数组mp2和mp3同时记录长度l2、l3。双重循环外层遍历二进制下标i ii将该位取反。内层遍历三进制下标j jj记录原值x xx循环k 0..2 k0..2k0..2若等于原值则跳过否则赋值mp3[j]k。分别计算ans2和ans3。若相等输出ans2并返回。恢复三进制位为x xx继续尝试下一个k kk。内层结束后恢复二进制位。结果程序在找到唯一解后直接输出并退出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll ans2,ans3;ll mp2[100000],mp3[100000];ll l2,l3;chars[100000];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%s,s);for(ll i0;i(ll)strlen(s);i){s[i]-0-1;mp2[i]s[i]-1;l2i1;}scanf(%s,s);for(ll i0;i(ll)strlen(s);i){s[i]-0-1;mp3[i]s[i]-1;l3i1;}for(ll i0;il2;i){for(ll j0;jl3;j){ll xmp3[j];for(ll k0;k2;k){if(mp2[i]1)mp2[i]0;elsemp2[i]1;mp3[j]k;ans20;for(ll l0;ll2;l)ans2ans2*2mp2[l];ans30;for(ll l0;ll3;l)ans3ans3*3mp3[l];if(mp2[i]1)mp2[i]0;elsemp2[i]1;mp3[j]x;if(ans2ans3){printf(%lld,ans2);return0;}ans2ans30;}}}return0;}