UVa 826 Symbolic Numerical System

题目描述给定一个字母表A[s0,s1,…,sk]A [s_0, s_1, \ldots, s_k]A[s0​,s1​,…,sk​]k≥3k \ge 3k≥3每个符号sis_isi​有一个位置值p(si)ip(s_i) ip(si​)i。选定一个基符号bbb满足p(b)≥2p(b) \ge 2p(b)≥2则任意非负整数NNN可表示为rrr位数字dr−1…d1d0d_{r-1} \ldots d_1 d_0dr−1​…d1​d0​其中每个di∈Ad_i \in Adi​∈A且p(di)p(b)p(d_i) p(b)p(di​)p(b)并且N∑i0r−1p(di)⋅[p(b)]i. N \sum_{i0}^{r-1} p(d_i) \cdot [p(b)]^i.Ni0∑r−1​p(di​)⋅[p(b)]i.该表示记为(dr−1…d1d0)b(d_{r-1} \ldots d_1 d_0)_b(dr−1​…d1​d0​)b​。给定一个字母表不含字符?以及三个部分已知的数字字符串其中?表示未知数字每个位置至多一个?要求判断是否存在一个基bbb使得第三个数字等于前两个数字之和按该基解释。若存在多个输出位置最小的基。若存在解则输出四行基符号、完整指定的三个数字将?替换为适当数字否则无输出。输入格式第一行为一个正整数表示测试用例个数随后有一个空行。每个测试用例包含四行第一行为字母表AAA之后三行为三个数字字符串可能含有?每个字符串不含空格。各测试用例之间有一个空行。输出格式对于每个测试用例若存在解则输出四行第一行为基符号随后三行为完整数字替换?为对应符号。不同测试用例的输出之间用一个空行分隔。若不存在解则无任何输出。样例输入1 *!30zx9bdk ?z b !*?样例输出d bz b !*0题目分析字母表AAA中的每个符号对应一个位置值从000开始。基符号bbb的位置值p(b)p(b)p(b)即为该进制系统的基数且必须满足p(b)≥2p(b) \ge 2p(b)≥2。数字字符串中的每个字符除?外必须满足其位置值小于基数否则该基数无效。加法按位进行从最低位右侧开始考虑进位。由于两个加数可能长度不同缺失的高位视为000。目标数也可能长度不同。给定三个字符串中可能存在?表示该位数字未知但约束保证同一位置至多一个?。因此对于任意位置最多只有一个数在该位是?其余两个数在该位要么已知要么不存在视为000。我们需要找到最小的基数即位置值最小的基符号使得存在一种填充?的方式满足加法等式。解题思路枚举所有候选基符号按位置值升序排列。对于每个候选基执行以下检查步骤1\texttt{1}1. 合法性检查遍历三个字符串中的所有已知字符若其位置值大于等于候选基数则该基无效。步骤2\texttt{2}2. 从最低位字符串最右端开始按位进行深度优先搜索DFS\texttt{DFS}DFS同时处理进位。设当前处理位索引为iii从000开始进位为ccc000或111。对于第iii位获取三个数在该位的字符若该位已超出字符串长度则视为不存在值为000且不是?。步骤3\texttt{3}3. 根据该位未知字符的情况最多一个?确定该位的数字值若无?则直接验证v1v2cv_1 v_2 cv1​v2​c是否等于v3base×c′v_3 \text{base} \times cv3​base×c′其中c′cc′是下一进位000或111。若相等则递归处理下一位并尝试c′0c 0c′0和c′1c 1c′1。若有一个?则根据已知的v1,v2,v3v_1, v_2, v_3v1​,v2​,v3​和进位ccc解出未知数字的值检查是否在[0,base−1][0, \text{base}-1][0,base−1]区间内然后确定下一进位并递归。步骤4\texttt{4}4. 当处理完所有位即所有字符串的最高位之后时若进位为000则找到一组解记录并立即终止搜索因为基按升序枚举第一个找到的解即为最优。步骤5\texttt{5}5. 若所有候选基均失败则无解。由于每个位置至多一个?搜索空间很小且基数最大为字母表长度减111最多707070枚举可行。代码实现// Symbolic Numerical System// UVa ID: 826// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 读取非空行跳过空行stringreadNonEmptyLine(){string line;while(getline(cin,line)){if(!line.empty())returnline;}return;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;string dummy;getline(cin,dummy);// 消耗第一行剩余换行符boolfirstOutputtrue;for(inttc0;tcT;tc){string AreadNonEmptyLine();string s1readNonEmptyLine();string s2readNonEmptyLine();string s3readNonEmptyLine();unordered_mapchar,intpos;for(inti0;i(int)A.size();i)pos[A[i]]i;// 收集候选基按位置升序vectorpairint,charbases;for(charch:A){intppos[ch];if(p2)bases.push_back({p,ch});}sort(bases.begin(),bases.end());boolfoundfalse;string out1,out2,out3;charbaseChar0;for(autopr:bases){intbasepr.first;charbcpr.second;// 检查所有已知数字的位是否均小于基值boolvalidtrue;autocheckDigits[](conststrings){for(charc:s){if(c?)continue;if(pos[c]base){validfalse;break;}}};checkDigits(s1);if(!valid)continue;checkDigits(s2);if(!valid)continue;checkDigits(s3);if(!valid)continue;intlen1s1.size(),len2s2.size(),len3s3.size();intmaxLenmax(max(len1,len2),len3);string tmp1s1,tmp2s2,tmp3s3;boolmemo[75][2]{};boolokfalse;functionbool(int,int)dfs[](intidx,intcarry)-bool{if(idxmaxLen)returncarry0;if(memo[idx][carry])returnfalse;// 获取该位字符不存在则视为 \0charc1(idxlen1)?s1[len1-1-idx]:\0;charc2(idxlen2)?s2[len2-1-idx]:\0;charc3(idxlen3)?s3[len3-1-idx]:\0;intv10,v20,v30;boolunk1false,unk2false,unk3false;if(c1\0)v10;elseif(c1?)unk1true;elsev1pos[c1];if(c2\0)v20;elseif(c2?)unk2true;elsev2pos[c2];if(c3\0)v30;elseif(c3?)unk3true;elsev3pos[c3];// 尝试两种可能的进位for(intnewCarry0;newCarry1;newCarry){intx-1;if(unk1){xv3base*newCarry-v2-carry;if(x0xbase){tmp1[len1-1-idx]A[x];if(dfs(idx1,newCarry))returntrue;tmp1[len1-1-idx]?;}}elseif(unk2){xv3base*newCarry-v1-carry;if(x0xbase){tmp2[len2-1-idx]A[x];if(dfs(idx1,newCarry))returntrue;tmp2[len2-1-idx]?;}}elseif(unk3){xv1v2carry-base*newCarry;if(x0xbase){tmp3[len3-1-idx]A[x];if(dfs(idx1,newCarry))returntrue;tmp3[len3-1-idx]?;}}else{if(v1v2carryv3base*newCarry){if(dfs(idx1,newCarry))returntrue;}}}memo[idx][carry]true;returnfalse;};okdfs(0,0);if(ok){foundtrue;baseCharbc;out1tmp1;out2tmp2;out3tmp3;break;}}if(found){if(!firstOutput)cout\n;firstOutputfalse;coutbaseChar\n;coutout1\n;coutout2\n;coutout3\n;}}return0;}总结本题通过枚举进制基数并利用深度优先搜索逐位验证加法解决了部分信息已知的未知进制加法问题。关键点在于利用每个位置至多一个未知数字的特性将回溯搜索限制在可行范围内。按位置升序枚举基保证了第一个解即为位置最小的基。代码实现了完整的解析、合法性检查和递归求解时间复杂度为O(∣base∣⋅L⋅2)O(|\text{base}|\cdot L \cdot 2)O(∣base∣⋅L⋅2)其中LLL为最大数字长度满足题目限制。该解法充分体现了组合搜索与进制转换的结合。