题目描述给定一个由若干单词组成的字典和若干规则每个规则由字符#和0组成其中#表示从字典中选取一个单词0表示选取一个数字000到999。要求生成所有可能的密码即用字典中的单词依次替换规则中的#用数字替换规则中的0得到的所有字符串。输出时按规则顺序同一规则下按字典顺序单词按字典输入顺序数字按升序。输入可能包含多组数据每组由字典和若干规则组成。输入格式第一行为一个整数nnn0n≤1000 n \le 1000n≤100表示字典中的单词数量。接下来nnn行每行一个单词长度111到255255255由字母和数字组成。随后一行是一个整数mmmm1000m 1000m1000表示规则数量。接下来mmm行每行一个规则长度不超过255255255由字符#和0组成其中至少含有一个0#可有可无。输入包含多组这样的数据直到文件结束。输出格式对于每组数据首先输出一行--两个连字符。然后对于每条规则按顺序输出所有匹配的密码即按照规则中#和0的位置用字典中的单词和数字替换后产生的全部字符串。同一规则下数字部分按升序000到999生成单词部分按字典输入顺序依次替换形成笛卡尔积。字典序由规则中#和0的位置决定即替换顺序固定为从左到右。样例输入2 root 2super 1 #0 1 admin 1 #0#输出-- root0 root1 root2 2super0 2super1 2super2 2super3 2super4 2super5 2super6 2super7 2super8 2super9 -- admin0admin admin1admin admin2admin admin3admin admin4admin admin5admin admin6admin admin7admin admin8admin admin9admin题目分析本题是典型的排列组合生成问题。规则中的每个#位置可以放置任意一个字典单词每个0位置可以放置任意一个数字000到999。最终密码由规则串中的符号顺序决定只需依次替换即可。由于0出现次数最多777次#出现次数不限但规则长度有限因此组合数量可能很大但题目要求全部输出只需递归枚举。解题思路读入字典单词存入数组。读入规则个数对每条规则将规则中的0替换为另一个字符如$以便在递归中区分数字和单词位置代码中直接用rule[j] 0判断但改为$是为了在回溯时统一处理。使用深度优先搜索DFS\texttt{DFS}DFS遍历规则串的每个位置若当前位置字符为#则枚举所有字典单词按输入顺序将对应单词输出或存储到临时数组继续递归。若当前位置字符为$即原0则枚举数字000到999继续递归。当遍历完规则串所有位置时将临时数组中的内容拼接成密码并输出。每组数据开始时输出--每条规则生成的密码连续输出不同规则间无额外空行。复杂度分析设字典大小为nnn规则长度为LLL其中#个数为aaa0个数为bbb则密码总数为na×10bn^a \times 10^bna×10b。由于b≤7b \le 7b≤7aaa受规则长度限制L≤255L \le 255L≤255但n≤100n \le 100n≤100在最坏情况下数量可能极大但题目要求全部输出因此必须接受。递归深度为LLL每次递归枚举nnn或101010种选择时间复杂度正比于输出数量。代码实现// Passwords// UVa ID: 628// Verdict: Accepted// Submission Date: 2016-08-27// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intn,m,password[260];string dictionary[110];voidbacktrack(string rule,intdepth){if(depthrule.length()){for(inti0;irule.length();i){if(password[i]0)coutdictionary[password[i]];elsecout(char)(0password[i]10);}cout\n;}else{if(rule[depth]#){for(intj0;jn;j){password[depth]j;backtrack(rule,depth1);}}else{for(intj0;j9;j){password[depth]j-10;backtrack(rule,depth1);}}}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string rule;while(cinn){for(inti0;in;i)cindictionary[i];cout--\n;cinm;for(inti1;im;i){cinrule;for(intj0;jrule.length();j)if(rule[j]0)rule[j]$;backtrack(rule,0);}}return0;}总结本题通过深度优先搜索枚举规则中每个符号的所有可能选择生成所有密码。关键点在于用数组password记录每个位置选择的索引单词索引或负数表示数字。数字位置用负值表示输出时转换回字符。规则中0替换为$便于在递归中区分。输出顺序由规则顺序和字典顺序自然决定因为单词按输入顺序枚举数字按升序枚举。该解法直接暴力的生成所有组合适合规则中0数量少的情况若0数量较多最多 7 个输出量可能巨大但题目要求如此。