小G的ACM之路

题意： 有n个学生在学校，他们有n个真名，以及n个假名。 求如何真名和假名，匹配使得LCP和最大。解析： 先给真名和假名标号，然后插入到字典树上。 一颗字典树上面的每个节点，保存的是每个字符串前缀的编号。 然后对字典树进行dfs，然后优先选择深的匹配，并标记。 然后回溯匹配。mymy codecode#include <cstdio>#include <cstr

题意： 有n和DNA序列，求出他们中公共前缀长度和有相同公共前缀DNA序列乘积的最大值。解析： 这题用trie来搞，用trie存储所有的DNA序列，然后每个节点有个val值，还有一个length表示的是存储以该节点结尾的DNA序列的数目，最后求出length*val最大的，就是最终答案。mymy codecode#include <cstdio>#include <cstring>#

题意： 给一个单词字典A={str[0],str[1],...}A=\{str[0], str[1], ...\}，再给定一系列的单词B={s[0],s[1],s[2],...}B = \{s[0], s[1], s[2], ...\}，求字典A中以s[i]为前缀的单词有多少。解法： 先建字典数，然后再查询每个给定的单词为前缀出现了多少次。mymy codecode#include <c

解析： 找出能唯一标示一个字符串的最短前缀。解析： Trie树。val表示有多少个单词节点。先将所有单词保存在Trie树中，然后一个一个地查找，当到达某个节点时val==1。表示到当前位置只有一条路，那么从根到该节点组成的字符串便是该单词的最短前缀。总结： RE了一个下午，才知道，遍历字符串的时候要先求出字符串的长度，然后根据这个长度进行遍历，而我之前是用指针偏移来做的，这样可能会R

题意： 首先要写一个添加字符串操作，比如说我输入“1 abc”就是添加字符串abc。然后写查询城市名称操作比如说我输入“2 abcabc”就是查询abcabc是否是所有添加过的字符串中前后缀组合（或本身就是某单词的前缀或后缀），输出“YES”或“NO”。 字符串不会超过100个字符！操作总数不超过50000个。解析： 利用Trie构建两个字典树，前缀树和后缀树，先将字符串正着和插入前

题意： 判断输入的电话号码的前缀，是否是其他电话号码，如果是其他号码就输出NO，否则输出YES。解析： 这题的思路很简单，直接利用Trie树求解。 先把所有的电话号码从1到n进行标号，并插入Trie树中，然后利用Trie树查找每个电话号码，如果在查找的过程中遇到val != 0就return，判断返回的结果是不是当前的电话号码的编号，如果不是就return false。mymy c

题意： 给定一个长度不超过30000的字符串SS，然后给定n(n<=4000)个长度不超过100的字符串aia_i，问用aia_i组合成SS有多少种方案数，由于数量可能很大，最终结果mod 20071027。题解： 本来想学习一下字典树的，但是这题用到了dp。 dp[i]dp[i]表示从ii开始到SS末尾有多少种组合方案。 那么dp公式为：dp[i]=∑dp[i+len(x)]

题意： 输入一个字典，字典格式为“英语 外语”的一一映射关系 然后输入若干个外语单词，输出他们的 英语翻译单词，如果字典中不存在这个单词，则输出“eh”解析： 对于所有给定的单词建立一颗字典树，然后对于每次给出的单词用字典树进行查询。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>usin

题意： f(A,B)f(A,B)表示：B在A中作为子串出现的次数。 题目给出n个证据，m个子弹 AiA_i是证据，BiB_i是子弹，题目问：所有BiB_i对每个AiA_i造成的伤害是多少，即每个BiB_i在AiA_i中出现的次数总和。解析： 不会AC自动机，所以就用字典树水了一发，没想到过了。 先把所有的BiB_i插入字典树中，然后枚举每个AiA_i的后缀，查询每个前缀在

题意： 输入IPv4地址空间中的一些子网号，构成一个网络集合。 输出个数最小的一个网络集合，要求其与输入集合没有交集，且相对IPv4地址空间全集，是输入集合的补集。 输出集合包含的子网号，格式遵循网络规范。解析： 这题可以用Trie树来搞。 每个IP地址由32位二进制组成。整个地址空间可以表现为一棵二叉树。 以下4个子网的覆盖情况： 0.0.0.0/1 （

题意： 给定一个序列，求选定一段区间的亦或和最大值和最小值。解析： 由于是区间问题，很容易就能想到是要先求前缀异或和。 可以对所有前缀和建立字典树，节点的末尾保存二进制转化成十进制的值。 先查询，再插入。 可以先将所有的的数字转化成二进制字符串，高位在前，低位在后。 最大值很简单，查找时然后尽量往反向走； 最小则需要尽量往正向走。 知道走到尽头时把找到的

题意： 给你很多对单词，单词相当于一个点，一对单词相当于一条边，问这么多对的单词能否组成一条欧拉路，要求每条边都要经过。解析： 题目数据很大，每个单词最多10个字母，据说用map映射会TLE。 所有要改用字典树进行hash。 判断欧拉路径或者回路需要满足两个条件。 图上所有点联通 度数为奇数个的节点只有0个或者2个。具体做法： 判断连通性就用并查集，判断是否只

题意： 给定若干个字符串，将其分组，按照组成元素相同为一组，输出数量最多的前5组，每组按照字典序输出所。 有字符串。数量相同的输出字典序较小的一组。注意： 每个输出时每个字符串只能出现一次。解析： 可以先将所有的字符串利用字典树hash，并利用vector进行保存。 然后对vector进行标号，这样只要对标号进行排序，而不用对vector进行排序。效率大大提高。mymy

题意： 给出n个模式串，串中除开小写字母外，’?’代表一个字符，’*’代表可空的任意字符串，然后再给出m个字符串，问有多少个模式串可以与之匹配。解析： 可以通过模式串建立字典树，接着根据字符串去dfs就行了。 需要注意的就是遇到当前节点为*则还可以继续走当前结点，每次dfs要么字典树匹配深度加1，要么字符串位置加1，记录每个结点保存模式串的终点的编号，建一个邻接表储存各个结点的模式串

背景：为了方便九宫格手机用户发短信，希望在用户按键时，根据提供的字典（给出字符串和频数），给出各个阶段最有可能要打的单词。题意： 首先给出的是字典，每个单词有一个出现频率。然后给出的是询问，每个询问有一个数字字符串，代表在手机上按了哪些键，以1结束。问按键的过程中最可能出现的单词分别是哪些。 注意：hell的权值为hell hello hellmoun 的权值和。 即一个字符串前