UVa1597 - Searching the Web
1 题目理解
刘老师对这题的介绍是这样的:
看到该题,最容易想到的方法,就是对于每次请求,都去搜索1500行文档的信息。但是这样效率过低,会超过3秒的限制时间。故这题靠LRJ给出的题目要求还不够,还需要读英文原题,因为原题里有这道题的解题思路。以下是我对前四段话的翻译(本人英语四级未过,不对翻译质量负责~~):
输入的多篇文档,行数总和不会超过1500行。我一开始以为是每篇文档不会超过1500行,把这题做的太难了,还悲剧的RE。
好吧,上面其实都是废话,这一句也是~~~下面步入主题。
2 基本框架
如果读者想看明白我的解法,建议这里的讲解和代码要配合看。
(我这里说的文档,就是LRJ说的“文章”的意思)
既然总行数少,那么重点应该是放在行操作上。但文档的编号还是对解题有影响的,首先程序输出中,每隔一个文档,要输出10个'-';其次对“NOT”,"AND”也有比较大的算法干扰。不过有办法克服的,相信这个思路是的对的,故我先定义一个基本的数据类型typedef bool Bit[1505]。然后定义一个叫Index的map,以文档中出现的每一个单词为key,对应的值为Bit,Bit[i]=1表示这个单词在i行有出现,否则就是没出现。
同时,定义变量n为文章总数,lines是文档总行数,m是请求总数。用string doc[1505]来存储每行对应的原始内容。所有的编号都是从0开始。
关于文章编号的处理,定义int limit[105],limit[i]表示第i篇文档是第几行开始的,有了limit,就能在整个程序中的区分哪些行是哪些文档的,方便对特定文档进行遍历操作。因为整个程序中包含许多这样的操作:将编号为i的文档,遍历其所有的行j,故我把这个for循环写成一个宏定义,简化代码:#define FOR for (int j = limit[i]; j < limit[i + 1]; j++)。
3 解题思路
分两个大环节,第一个section是:对输入文档信息的初始化操作,包括Index的构建。第二个section是:对每一个请求,给出相应的输出内容。
第一个环节中,计算出lines,limit都不难。主要是Index的构建:对输入的每行信息(如第p行),要找出里面包含的所有单词,将该单词对应的Bit的第p位记为true(注意Bit建立时每位会自动初始化为false)。这里封装一个函数upDate(string s, int p)来辅助操作,它能将s中的单词对应的Bit的第p位记为true。
第二个环节中,我引入一个中介变量,Bit mark,mark[j]表示第j行是否需要输出。分两个小节来处理第二环节,第一个subsection得到四种命令中的某种,只需要负责计算出对应的mark,由第二个subsection来负责mark的输出操作。因为这题的输出格式不太容易控制,每输出一个文档要输出一个结束标志,如果对四种命令都写输出语句,会造成很多不必要的重复和代码量过大。
那么第一个subsection中,如何处理四种命令呢?假设输出的第一个单词对应的Bit是A,第二个单词对应的Bit是B(不一定存在)。那么对于单个单词的查询,mark其实就是A。对于OR操作,只要A与B直接每位进行或操作,就能得到mark,即mark[j] = (A[j]||B[j])。对于NOT操作(比较麻烦),需要使用到前面提到的宏FOR,对每个文档的行进行遍历,如果A[j]的值都是false,代表这篇文章要全部输出,故对应的这块mark[j]都等于true,否则,这块mark[j]都等于false。对于AND操作(最难的一种),也需要对每块单独进行处理,如果这块A和B都有ture的值,代表这篇文档两个单词都有出现,那么这块mark按“OR”同样的方法进行局部赋值,否则这块mark全部等于false。
讲了这么多,其实我的方法也不是最优的,AC这题用了0.8秒,有个大牛用了0.08秒不知道怎么解的。所以我的方法能不能理解其实关系不大,更重要的是自己思考。我写这么多只是想让以后的自己能看懂~~~
4 求解代码
view plain copy 1. //{头文件模板2. #include 3. #include 4. #include 5. #include 6. #include 7. #include 8. #include 9. #include 10. #include 11. #include 12. #include 13. #include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
暂时没有评论,来抢沙发吧~