当前位置：首页 > news >正文

UVa 628 Password

news 2026/7/6 8:56:03

题目描述

给定一个由若干单词组成的字典和若干规则，每个规则由字符#和0组成，其中#表示从字典中选取一个单词，0表示选取一个数字（000到999）。要求生成所有可能的密码，即用字典中的单词依次替换规则中的#，用数字替换规则中的0，得到的所有字符串。输出时按规则顺序，同一规则下按字典顺序（单词按字典输入顺序，数字按升序）。输入可能包含多组数据（每组由字典和若干规则组成）。

输入格式

第一行为一个整数nnn（0<n≤1000 < n \le 1000<n≤100），表示字典中的单词数量。接下来nnn行，每行一个单词（长度111到255255255，由字母和数字组成）。随后一行是一个整数mmm（m<1000m < 1000m<1000），表示规则数量。接下来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，其中#个数为aaa，0个数为bbb，则密码总数为na×10bn^a \times 10^bna×10b。由于b≤7b \le 7b≤7，aaa受规则长度限制（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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intn,m,password[260];string dictionary[110];voidbacktrack(string rule,intdepth){if(depth==rule.length()){for(inti=0;i<rule.length();i++){if(password[i]>=0)cout<<dictionary[password[i]];elsecout<<(char)('0'+password[i]+10);}cout<<'\n';}else{if(rule[depth]=='#'){for(intj=0;j<n;j++){password[depth]=j;backtrack(rule,depth+1);}}else{for(intj=0;j<=9;j++){password[depth]=j-10;backtrack(rule,depth+1);}}}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string rule;while(cin>>n){for(inti=0;i<n;i++)cin>>dictionary[i];cout<<"--\n";cin>>m;for(inti=1;i<=m;i++){cin>>rule;for(intj=0;j<rule.length();j++)if(rule[j]=='0')rule[j]='$';backtrack(rule,0);}}return0;}