企业官网建设流程全解析

题目描述

给定一个字母表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=∑i=0r−1p(di)⋅[p(b)]i. N = \sum_{i=0}^{r-1} p(d_i) \cdot [p(b)]^i.N=i=0∑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开始），进位为ccc（000或111）。对于第iii位，获取三个数在该位的字符（若该位已超出字符串长度，则视为不存在，值为000，且不是?）。

步骤3\texttt{3}3. 根据该位未知字符的情况（最多一个?）确定该位的数字值：

• 若无?，则直接验证v1+v2+cv_1 + v_2 + cv1​+v2​+c是否等于v3+base×c′v_3 + \text{base} \times c'v3​+base×c′，其中c′c'c′是下一进位（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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 读取非空行（跳过空行）stringreadNonEmptyLine(){string line;while(getline(cin,line)){if(!line.empty())returnline;}return"";}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;string dummy;getline(cin,dummy);// 消耗第一行剩余换行符boolfirstOutput=true;for(inttc=0;tc<T;++tc){string A=readNonEmptyLine();string s1=readNonEmptyLine();string s2=readNonEmptyLine();string s3=readNonEmptyLine();unordered_map<char,int>pos;for(inti=0;i<(int)A.size();++i)pos[A[i]]=i;// 收集候选基（按位置升序）vector<pair<int,char>>bases;for(charch:A){intp=pos[ch];if(p>=2)bases.push_back({p,ch});}sort(bases.begin(),bases.end());boolfound=false;string out1,out2,out3;charbaseChar=0;for(auto&pr:bases){intbase=pr.first;charbc=pr.second;// 检查所有已知数字的位是否均小于基值boolvalid=true;autocheckDigits=[&](conststring&s){for(charc:s){if(c=='?')continue;if(pos[c]>=base){valid=false;break;}}};checkDigits(s1);if(!valid)continue;checkDigits(s2);if(!valid)continue;checkDigits(s3);if(!valid)continue;intlen1=s1.size(),len2=s2.size(),len3=s3.size();intmaxLen=max(max(len1,len2),len3);string tmp1=s1,tmp2=s2,tmp3=s3;boolmemo[75][2]={};boolok=false;function<bool(int,int)>dfs=[&](intidx,intcarry)->bool{if(idx==maxLen)returncarry==0;if(memo[idx][carry])returnfalse;// 获取该位字符（不存在则视为 '\0'）charc1=(idx<len1)?s1[len1-1-idx]:'\0';charc2=(idx<len2)?s2[len2-1-idx]:'\0';charc3=(idx<len3)?s3[len3-1-idx]:'\0';intv1=0,v2=0,v3=0;boolunk1=false,unk2=false,unk3=false;if(c1=='\0')v1=0;elseif(c1=='?')unk1=true;elsev1=pos[c1];if(c2=='\0')v2=0;elseif(c2=='?')unk2=true;elsev2=pos[c2];if(c3=='\0')v3=0;elseif(c3=='?')unk3=true;elsev3=pos[c3];// 尝试两种可能的进位for(intnewCarry=0;newCarry<=1;++newCarry){intx=-1;if(unk1){x=v3+base*newCarry-v2-carry;if(x>=0&&x<base){tmp1[len1-1-idx]=A[x];if(dfs(idx+1,newCarry))returntrue;tmp1[len1-1-idx]='?';}}elseif(unk2){x=v3+base*newCarry-v1-carry;if(x>=0&&x<base){tmp2[len2-1-idx]=A[x];if(dfs(idx+1,newCarry))returntrue;tmp2[len2-1-idx]='?';}}elseif(unk3){x=v1+v2+carry-base*newCarry;if(x>=0&&x<base){tmp3[len3-1-idx]=A[x];if(dfs(idx+1,newCarry))returntrue;tmp3[len3-1-idx]='?';}}else{if(v1+v2+carry==v3+base*newCarry){if(dfs(idx+1,newCarry))returntrue;}}}memo[idx][carry]=true;returnfalse;};ok=dfs(0,0);if(ok){found=true;baseChar=bc;out1=tmp1;out2=tmp2;out3=tmp3;break;}}if(found){if(!firstOutput)cout<<"\n";firstOutput=false;cout<<baseChar<<"\n";cout<<out1<<"\n";cout<<out2<<"\n";cout<<out3<<"\n";}}return0;}

总结

本题通过枚举进制基数并利用深度优先搜索逐位验证加法，解决了部分信息已知的未知进制加法问题。关键点在于利用每个位置至多一个未知数字的特性，将回溯搜索限制在可行范围内。按位置升序枚举基保证了第一个解即为位置最小的基。代码实现了完整的解析、合法性检查和递归求解，时间复杂度为O(∣base∣⋅L⋅2)O(|\text{base}|\cdot L \cdot 2)O(∣base∣⋅L⋅2)，其中LLL为最大数字长度，满足题目限制。该解法充分体现了组合搜索与进制转换的结合。