第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-193 Password Suspects(C++&Java)
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
Password Suspects
资源限制
内存限制：128.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
你是一个秘密犯罪组织the Sneaky Underground Smug Perpetrators of Evil Crimes and Thefts(SUSPECT)里的电脑高手。SUSPECT最新的邪恶犯罪目标是他们最大的对手the Indescribably Clever Policemen’s Club（ICPC），一切都已经准备就绪，除了一件小事：ICPC的主机密码。
密码仅有小写字母’a’-‘z’构成。此外，通过各种偷窥，你已经确定了密码的长度，和一些（可能重叠）密码中的子串，尽管你不清楚他们出现在密码的哪个位置。
例如，你知道密码的长度是10个字符且你观察到了子串“hello”和“world”。那么密码一定是“helloworld”或者“worldhello”。
问题在于这些信息是否能将密码的可能数缩减到一个合理的范围内。要回答这个问题，你的任务是写一个程序判断可能的密码的总数目，如果可能的密码数目不超过42，打印出所有可能密码。
输入格式
第一行包含两个整数N和M，分别表示密码的长度和已知的密码中子串的数量。接下来M行，每行一个密码中的已知子串。
输出格式
第一行输出Y，Y表示可能的密码的数目。如果Y不超过42，接下来按照字典序，每行一个密码，依次输出所有可能的密码。
样例输入
10 2
hello
world
样例输出
2
helloworld
worldhello
样例输入
10 0
样例输出
141167095653376
样例输入
4 1
icpc
样例输出
1
icpc
数据规模和约定
1<=N<=25，0<=M<=10，子串长度<=10，所有字符均为小写字母’a’-‘z’，输入数据保证答案不超过10^15。
C++语言
#include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 200; const int maxm = 26; LL dp[maxn][40][1<<11]; bool vis[maxn][40][1<<11]; char tmp[40]; char s[40]; int n,m; struct Acautomata{ int ch[maxn][maxm],val[maxn],fail[maxn],root,sz; int newnode(){ val[sz] = 0; memset(ch[sz],0,sizeof(ch[sz])); return sz++; } void init(){ sz = 0; root = newnode(); } void insert(char *s, int v){ int u = root, len = strlen(s); for(int i = 0; i < len; i++){ int now = s[i] - 'a'; if(!ch[u][now]){ ch[u][now] = newnode(); } u = ch[u][now]; } val[u] |= v; }// void build(){ queue <int> q; fail[0] = 0; for(int i = 0; i < maxm; i++){ int u = ch[0][i]; if(u){ q.push(u); fail[u] = 0; } } while(q.size()){ int u = q.front(); q.pop(); for(int i = 0; i < maxm; i++){ int v = ch[u][i]; if(!v){ ch[u][i] = ch[fail[u]][i]; continue; } q.push(v); int j = fail[u]; while(j && !ch[j][i]) j = fail[j]; fail[v] = ch[j][i]; val[v] |= val[fail[v]]; } } }// LL dfs(int u,int len,int st) { if(vis[u][len][st]) return dp[u][len][st]; vis[u][len][st] = 1; LL &ans = dp[u][len][st]; if(len == n){ if(st == (1<<m)-1) return ans = 1; else{ return ans = 0; } } ans = 0; for(int i = 0; i < maxm; i++){ ans += dfs(ch[u][i], len+1, st|val[ch[u][i]]); } return ans; } void print_path(int u,int len,int st) { if(len == n) { for(int i = 1; i <= len; i++) printf("%c",tmp[i]); printf("\n"); return ; } for(int i = 0; i < maxm; i++) { tmp[len+1] = 'a' + i; if(dp[ch[u][i]][len+1][st|val[ch[u][i]]]) { print_path(ch[u][i],len+1,st|val[ch[u][i]]); } } } }ac;//自定义了一个 int main() { int ks = 1; while(scanf("%d%d",&n,&m) != EOF) { if(n == 0 && m == 0) break; ac.init();// for(int i = 0; i < m; i++){ scanf("%s",s); ac.insert(s, 1<<i); } ac.build();// memset(vis,0,sizeof(vis)); //memset(dp,0,sizeof(dp)); LL ans = ac.dfs(0,0,0); //printf("%lld\n",ans); printf("%lld\n",ans); if(ans <= 42) ac.print_path(0,0,0); } return 0; }
Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.concurrent.ConcurrentLinkedQueue; public class Main { public static void main(String[] args) { int n = 0; int m = 0; try { // 读取数据 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nm = br.readLine().split(" "); n = Integer.parseInt(nm[0]); m = Integer.parseInt(nm[1]); // 构建AC自动机 AC ac = new AC(n, m); for(int i = 0; i < m; i ++) { ac.insert(br.readLine(), i); } br.close(); ac.build(); long ans = ac.dfs(0, 0, 0); System.out.println(ans); if(ans <= 42) ac.print(0, 0, 0); } catch (IOException e) { e.printStackTrace(); } } } class AC{ int maxWord = 105; // AC自动机最大记录字母数，最大等于m*字符串最大长度=100，但是还有根节点，不妨设105 int dicLen = 26; // 每一个结点的最大子结点数，即有多少个字母 int maxLen = 30; // 最大密码长度 这里也是个点，不知道为什么写25会出错 int state = (1<<10) + 5; // 1 << M，实际上是一个用二进制表示的状态集，“1”位表示这个词已经出现过了 long[][][] dp = new long[maxWord][maxLen][state]; // 深度搜索、动态规划的矩阵 设d[u][len][state]表示最后一个是字典树的u结点 已选长度为len，状态为state的剩余种数 int[] fail = new int[maxWord]; // 状态转移表 int[] val = new int[maxWord]; // 用一个二进制化的整数表示当前已经出现了多少个词 全0表示当前没有出现词 全1表示字典中的词全出现了 int[] out = new int[dicLen]; // 输出用 public int[][] trie = new int[maxWord][dicLen]; // 字典树 private int nodeIndex = 1; // 当前的下标 0表示根结点 int n; int m; public AC(int n, int m) { this.n = n; this.m = m; for(int i = 0; i < maxWord; i ++) { // 对数组全部赋-1，-1表示没有搜索过，0表示搜索过但是没有匹配项 for(int j = 0; j < maxLen; j ++) { for(int k = 0; k < state; k ++) { dp[i][j][k] = -1; } } } } public void insert(String word, int v) { int pre = 0; for (int i = 0; i < word.length(); i ++) { int code = toInteger(word.charAt(i)); if (trie[pre][code] == 0) { // 如果字典树中不存在这个结点 trie[pre][code] = nodeIndex ++; // 增加一个结点 记录这个值 } pre = trie[pre][code]; } val[pre] |= (1 << v); // 标记状态 如果AC自动机经过pre结点，则val[pre]记录的词都出现在了字符串中 } /**构建next列表*/ public void build() { ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<Integer>(); // java自带的队列就是LinkedList 但LinkedList是线程不安全的 这里必需用线程安全的 因为有递归调用问题 // 把root的所有的子结点加入到队列中，并将这些结点的fail指向根结点 fail[0] = 0; for (int c = 0; c < dicLen; c ++) { int u = trie[0][c]; if (u != 0) { fail[u] = 0; queue.add(u); } } while (!queue.isEmpty()) { // 弹出一个结点 int r = queue.poll(); // 遍历下面的每一个结点 for (int c = 0; c < dicLen; c ++) { int u = trie[r][c]; if (u == 0) { // 如果字典树中不存在当前遍历的结点 trie[r][c] = trie[fail[r]][c]; // 子结点指向父节点失败结点的对应子结点 continue; } queue.add(u); int v = fail[r]; while (v != 0 && trie[v][c] == 0) // 如果还存着fail结点，并且这个结点的对应子结点却不存在，实际就是访问所有fail链 v = fail[v]; fail[u] = trie[v][c]; // 要么存在 要么为0 val[u] |= val[fail[u]]; // 当前遍历这个结点的状态集等于 当前状态集 并上 失败结点指向的状态集 } } } public long dfs(int now, int len, int st) { if (dp[now][len][st] != -1) // 如果已经搜索过这个结点，直接返回 return dp[now][len][st]; dp[now][len][st] = 0; // 否则，开始搜索这个结点 if (len == n) { if (st == (1 << m) - 1) // 假设输入的m是3，则1 << m后减1得 000...000111，表示3个词都出现了 return dp[now][len][st] = 1; return dp[now][len][st] = 0; } for (int i = 0; i < dicLen; i++) dp[now][len][st] += dfs(trie[now][i], len + 1, st|val[trie[now][i]]); return dp[now][len][st]; } public void print(int now, int len, int st) { if (len == n) { for (int i = 0; i < len ; i ++) System.out.print((char)(out[i] + 'a')); System.out.println(); return; } for (int i = 0; i < dicLen; i ++) { // 递归查找结果 if (dp[trie[now][i]][len + 1][st|val[trie[now][i]]] > 0) { out[len] = i; print(trie[now][i], len + 1, st|val[trie[now][i]]); } } } public int toInteger(char c) { return c - 'a'; } }
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
