P5758题解

我的第一个黑题一、题目描述[题目传送门](https://www.luogu.com.cn/problem/P5758)1.题目大意古梅文明有13 个符号a-m一一对应现代的0到9、和*和这 13 个字符。给定N个古梅文等式保证所有等式合法符合十进制运算、先乘后加、结果相等、无前导零。要求找出唯一确定的符号对应关系按字典序输出若没有任何合法映射输出noway。2、核心规则必须遵守一一对应13 个古梅符a-m分别对应唯一现代符无重复、无遗漏。格式规范每个等式有且仅有一个等号数字无前置零。运算规则十进制、先乘后加、等号两边结果相等。输出要求只输出所有合法映射中都不变的对应关系字典序排列。二、解题思路符号分类先拆分每个等式确定等号位置区分数字符和运算符、*。约束提取运算符不能作数字数字首位不能为 0一一对应。搜索映射枚举所有满足约束的a-m与现代符的一一映射。验证等式将古梅符替换为现代符计算并验证等式是否成立。确定结果统计所有合法映射保留取值唯一的符号按字典序输出。三、题目代码#include bits/stdc.h using namespace std; int n,cnt,pos; bool g[15][15],v[15]; string str[1005]; int ans[15],u[15],a[15],ed[1005],p[15]; string l,r; bool cmp(string x,string y) { int vis[30]; int cnt10,cnt20,i; memset(vis,0,sizeof(vis)); for (i0;ix.size();i) vis[x[i]-a]; for (i0;i26;i) if (vis[i]) cnt1; memset(vis,0,sizeof(vis)); for (i0;ix.size();i) vis[y[i]-a]; for (i0;i26;i) if (vis[i]) cnt2; return cnt1cnt2; } int work(string x) { int sum0,last1,single0,i; bool mult0; if (a[x[0]-a]9) return -1; if (a[x[x.size()-1]-a]9) return -1; for (i0;ix.size()-1;i) if(a[x[i]-a]0a[x[i1]-a]10(i0||a[x[i-1]-a]9)) return -1; for (i0;ix.size();i) { if(a[x[i]-a]10) { if (mult) sumlast*single, mult0, last1; else sumsingle; single0; continue; } if (a[x[i]-a]11) { mult1, last*single, single0; continue; } singlesingle*10a[x[i]-a]; } if (mult) sumlast*single; else sumsingle; return sum; } void dfs(int k,int t) { int i,tmp1,tmp2; if (kpos) k; while (ed[t]k-1 tn) { l; r; for (i0;istr[t].size();i) if (a[str[t][i]-a]!12) llstr[t][i]; else break; i; for (;istr[t].size();i) rrstr[t][i]; tmp1work(l); tmp2work(r); if (tmp1-1 || tmp2-1) return; if (tmp1!tmp2) return; t; } if (kcnt tn) { if (cnt12) { int s0; for (i0;i13;i) if (a[i]!-1) sa[i]; for (i0;i13;i) if (a[i]-1) a[i]78-s; } for (i0;i13;i) if (ans[i]-2 cnt12) continue; else if (ans[i]-1) ans[i]a[i]; else if (ans[i]!a[i]) ans[i]-2; return; } for (int i0;i12;i) { if (v[i] || !g[p[k]][i]) continue; a[p[k]]i; v[i]1; dfs(k1,t); v[i]0; a[p[k]]-1; } } int main() { int i,j; scanf(%d,n); for (i1;in;i) cinstr[i]; sort(str1,strn1,cmp); for (i0;i13;i) for (j0;j13;j) g[i][j]1; for (i0;i13;i) a[i]-1; for (i1;in;i) { memset(u,0,sizeof(u)); for (j1;jstr[i].size()-1;j) u[str[i][j]-a]; for (j0;j13;j) if (u[j]!1) g[j][12]0; g[str[i][0]-a][10]g[str[i][0]-a][11]g[str[i][0]-a][12]0; jstr[i].size()-1; g[str[i][j]-a][10]g[str[i][j]-a][11]g[str[i][j]-a][12]0; } memset(v,0,sizeof(v)); for (i1;in;i) { for (j0;jstr[i].size();j) if (!v[str[i][j]-a]) p[cnt]str[i][j]-a, v[p[cnt]]1; ed[i]cnt; } if (cnt!12) { for (i1;icnt;i) ans[p[i]]-1; for (i0;i13;i) if (ans[i]0) ans[i]-2; } else for (i0;i13;i) ans[i]-1; memset(v,0,sizeof(v)); for (i1;icnt;i) if (g[p[i]][12]!0) { a[p[i]]12; posi; dfs(1,1); for (j0;j13;j) a[j]-1; } for (i0;i13;i) if (ans[i]-1) { coutnoway\n; return 0; } for (i0;i13;i) if (ans[i]0) { coutchar(ia); if (ans[i]12) cout; else if (ans[i]11) cout*; else if (ans[i]10) cout; else coutans[i]; coutendl; } return 0; }这个代码是我最开始写的代码当时我的思路有5个步骤步骤 1输入处理与排序读取 n 个等式字符串按字符串中不同字符数量升序排序优先处理字符少的等式提前剪枝无效搜索提升效率步骤 2约束条件预处理建图g[][]用二维数组g[i][j]标记字母 i 能否映射为符号 jg[i][j]1表示允许0表示禁止提前排除非法映射等号映射值 12只能出现在等式中间禁止出现在字符串首尾加号(10)、乘号*(11)禁止出现在字符串首尾数字0-9遵守数字语法规则步骤 3字符统计与编号统计所有等式中出现过的字母给这些字母编号存入数组p[]记录每个等式处理完时对应的字符编号ed[]用于逐等式验证步骤 4深度优先搜索DFS 剪枝验证核心这是代码的灵魂暴力枚举字母的映射关系边搜索边验证提前排除错误方案固定等号字母遍历所有可能作为的字母g[i][12]1固定其映射为12递归枚举给剩余字母依次分配 0-9、、*保证不重复逐等式验证每分配一个字符就验证已处理的等式是否合法拆分等式为左表达式右表达式调用work()函数计算表达式数值若左右不相等 / 语法非法直接剪枝停止当前分支搜索合法解记录找到满足所有等式的映射后存入答案数组ans[]步骤 5结果处理与输出整合所有合法解的公共映射唯一确定的字母→符号若无合法解输出noway有解则按格式输出字母 对应的数字 / 符号结果提交后发现最后一个测试点TIE了所以哪儿错了呢原来是但搜索剪枝不够强、枚举顺序极差、重复计算极多导致大数据点直接超时。于是……标准代码出世四、题目标准AC代码#includebits/stdc.h using namespace std; int n; string s[1005]; char ch[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, , *, }; bitset13bit[13]; int vis[13]; int dui[13]; bitset13op; int ok; int b[1 13], dp[1 13]; int ord[13], ap[13]; int ans_ap[13], ans_ord[13], ans_rnk[13]; vectorintf[13]; inline int lowbit(int x) { return x (-x); } inline bool check(string x) { int len x.size(); char a ; char b ; char c *; char d 0; if (x[0] a || x[0] b || x[0] c || x[len - 1] a || x[len - 1] b || x[len - 1] c)return 0; int num_a 0; for (int i 0; i len; i) { num_a (x[i] a); } if (num_a ! 1)return 0; for (int i 1; i len; i) { if (x[i] a || x[i] b || x[i] c) { if (x[i - 1] a || x[i - 1] b || x[i - 1] c) { return 0; } } } for (int i 0; i len - 1; i) { if (i 0 || x[i - 1] a || x[i - 1] b || x[i - 1] c) { if (x[i] d) { if (x[i 1] ! a x[i 1] ! b x[i 1] ! c) { return 0; } } } } return 1; } inline int js(string x) { int s 1; int ans 0; for (int i 0; i x.size(); i) { if (0 x[i] x[i] 9) { int sum 0; while (i 1 x.size() 0 x[i 1] x[i 1] 9) { sum sum * 10 x[i] - 0; i; } sum sum * 10 x[i] - 0; s * sum; } else if (x[i] ) { ans s; s 1; } } ans s; return ans; } inline bool solve(string s) { for (int i 0; i s.size(); i) { s[i] ch[dui[s[i] - a]]; } if (!check(s))return 0; for (int i 0; i s.size() ; i) { if (s[i] ) { return js(s.substr(0, i)) js(s.substr(i 1)); } } } inline void dfs(int now) { for (auto to : f[now - 1]) { if (!solve(s[to]))return; } if (now 13) { ok 1; for (int i 0; i 13; i)bit[i][dui[i]] 1; return; } if (vis[ans_ord[now]]) { dfs(now 1); return; } for (int i op._Find_first(); i ! op.size(); i op._Find_next(i)) { dui[ans_ord[now]] i; op[i] 0; dfs(now 1); op[i] 1; if (ok)return; } } inline bool can(int x, int y) { for (int i 0; i 13; i) { op[i] 1; dui[i] 0; vis[i] 0; } vis[x] 1; dui[x] y; op[y] 0; ok 0; dfs(0); return ok; } int he 0; inline void dfs1(int now) { for (int i 0; i now; i) { if (ap[i] ans_ap[i])return; if (ap[i] ans_ap[i])break; } if (now 13) { for (int j 0; j 13; j) { ans_ap[j] ap[j]; ans_ord[j] ord[j]; } return; } for (int i op._Find_first(); i ! op.size(); i op._Find_next(i)) { ord[now] i; op[i] 0; he ^ (1 i); ap[now] dp[he]; dfs1(now 1); op[i] 1; he ^ (1 i); } } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin n; for (int i 1; i n; i) { cin s[i]; int sum 0; for (int j 0; j s[i].size(); j) { if (s[i][j] a || s[i][j] m) { cout noway endl; return 0; } sum | 1 (s[i][j] - a); } b[sum]; } for (int i 0; i 13; i)op[i] 1; for (int i 0; i (1 13); i) { for (int j i; j; j (j - 1) i) { dp[i] b[j]; } } dfs1(0); for (int i 1; i n; i) { int mx 0; for (int j 0; j s[i].size(); j) { for (int k 0; k 13; k) { if (ans_ord[k] s[i][j] - a) { mx max(mx, k); break; } } } f[mx].emplace_back(i); } for (int i 0; i 13; i)ans_rnk[ans_ord[i]] i; for (int i 0; i 13; i) { for (int j 12; j 0; --j) { if (can(i, j))bit[i][j] 1; if (bit[i].count() 1)break; } if (bit[i].count() 0) { puts(noway); return 0; } } for (int i 0; i 13; i) { if (bit[i].count() 1) { cout char(a i) ch[bit[i]._Find_first()] endl; } } return 0; }我这个代码的思路依旧是5个步骤步骤 1预处理输入收集约束读取所有等式统计每个等式用到的古梅符号标记无效输入非 $a-m$ 字符直接判无解。用位运算 / 数组记录每个等式的字符集合为后续剪枝做准备。步骤 2优化搜索顺序关键剪枝不按 $a-m$ 顺序暴力枚举而是按字符出现频率 / 约束强度排序优先枚举在等式中出现次数多、约束强的字符提前排除非法映射大幅减少搜索次数。用动态规划预处理字符组合的约束权重确定最优的枚举顺序。步骤 3深度优先搜索DFS枚举映射这是核心逻辑递归枚举每个古梅符号对应的现代算符满足一一对应每个现代算符只能用一次用bitset/vis数组标记已使用。实时验证每确定一个符号就立即验证已替换的等式不合法直接回溯剪枝。完整验证枚举完 13 个符号后验证所有等式完全合法。步骤 4等式合法性校验两大核心函数(1格式合法性检查 check()必须满足整个式子有且仅有 1 个等号运算符、*、不能在式子首尾不能连续出现如 ab 非法数字不能有前置零如 012 非法单独0合法。(2运算结果计算 js()遵循先乘后加规则先计算所有乘法部分再计算加法拆分等号左右两边判断计算结果是否相等。步骤 5筛选唯一确定的映射用bitset13 bit[13]记录每个古梅符号所有可能对应的现代算符遍历所有合法映射统计每个符号的可选值若bit[i]中只有 1 个 1 → 该符号对应关系唯一输出若bit[i]无 1 → 无合法映射输noway若大于 1 个 1 → 无法确定不输出。题解结束了完结给个赞吧