|
|
| |
|
SGOI14之《图书检索》解题报告
|
||||
［摘要］  ［题意简述］ 给定一个由若干长为N（N≤10）的01串构成的集合Ｓ，易知M=|S|≤1024 。定义： ①查询器q 是一个长为Ｎ且由"_","0","1"组成的字符串； ②查询器q的输出集 
；③合法查询器  满足：
；④关键查询器 
。任务一：求所有的合法查询器； 任务二：求所有的关键查询器。 ［算法分析］  首先求解任务一，根据题意叙述，我们很容易可以想到枚举算法：①构造所有的查询器；②分别除去Ｇ中不满足合法查询器某一个条件的查询器即可得到解。 第①步是非常容易的，查询器的每一位都有3种选择，根据乘法原理，一共可以产生出  个查询器。下面除去不满足第一个条件的查询器：根据题意，我们对每一个查询器q生成所有的
则q不是合法查询器，即从G中去掉。而 的产生，亦可使用dfs（如算法１）。这样第一步的过滤的算法复杂度大约是
。接着过滤不满足条件二的查询器，首先定义布尔函数：
易知 
，但是找到一个比q大的合法查询器还是非常麻烦的，于是我们再定义另一个函数： 可以得出，若有合法查询器  ，则一定有查询器
反之也成立。（这个定理较为简单，请同学们自己证明）。因此，我们可以将q 的每一个非"_"位尝试改成"_"成为tq
，若tq 满足合法查询器的条件一，则q 就不是一个合法的查询器。在实现时，我们可以在第一步过滤的时候将每一个查询器是否满足条件一存入一个布尔数组中，在第二步过滤时即可方便许多。这样第二步过滤的时间复杂度是O(N)级，空间复杂度是
。整个任务一求解的时间复杂度为
级。接着求解任务二，现在我们已经得到所有合法查询器的集合G了，因此任务二也就显得十分简单了，G 中的每一个查询器q ，并将q 的输出集中每一个01串标号；最后扫描 S中每一个01串，若该串仅被一个查询器标号，那么这个查询器就是关键查询器。下面计算一下求解任务二的时间复杂度：G 中最多有
个元素，生成每一个元素的输出集的时间复杂度是 ，因此总时间复杂度是 级。最后，在编程实现时，我们可以利用编码技术，提高程序效率，并使程序更加简洁。 ［总结］ 本题算法比较简单，只要理清思路，编程细心，即可做对。 |
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |