学步园

题目链接：poj 2408 Anagram Groups 题目大意：给定若干个字符串，将其分组，按照组成元素相同为一组，输出数量最多的前5组，每组按照字典序输出所 有字符串。数量相同的输出字典序较小的一组。 解题思路：将所有的字符串统计字符后hash，排序之后确定每组的个数并且确定一组中字典序最小的字符串。根据个数 以及字符串对组进行排序。 #include <cstdio> #include <cstring> #include <vector> #includ...

题目链接：poj 3764 The xor-longest Path 题目大意：给定一棵树，每条边上有一个权值，找出一条路径，使得路径上权值的亦或和最大。 解题思路：dfs一遍，预处理出每个节点到根节点路径的亦或和rec，那么任意路径均可以表示rec[a] ^ rec[b]，所以问题 就转换成在一些数中选出两个数亦或和最大，那么就建立字典树查询即可。 #include <cstdio> #include <cstring> #include <algorithm> using namespace...

题目链接：poj 3208 Apocalypse Someday 题目大意：给定n，输出第n大包含666的数字。 解题思路：数位dp，用类似AC自动机的思想进行转移。首先dp[i][j]表示说i位最后有j个连续6的情况数，这个预处理出 来。那么dp[i][3]即为i位有多少个满足的数。给定n，先确定位数d。然后从最高位向下判断，一开始肯定是需要3个连续 的6，所以u为3，然后根据后面添加的数字动态修改u值进行判断。 #include <cstdio> #include <cs...

题目链接：poj 1195 Mobile phones 题目大意：四种操作 0 s：清空(1,1)~(s,s) 1 x y a：在(x,y)点加上a 2 x1 y1 x2 y2：询问矩形(x1,y1)~(x2,y2)的和。 3：结束 解题思路：纯二维树状数组。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1030; #define lowbit(x) ((x)&(-x)) int fenw[maxn+5][maxn+5]; void add (int x, int y, int a) ...

题目链接：poj 2763 Housewife Wind 题目大意：给定一棵树，然后2种操作： 0 u：输出路径s到u的权值和，并且s变成u 1 i w：节点i增加w 解题思路：树链剖分，然后用线段树维护，单点修改区间查询。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100005; int N, Q, S, ne; int first[maxn], jump[maxn * 2]; int id, far[maxn], son[maxn], cnt...

题目链接：poj 3237 Tree 题目大意：给定一棵树，三种操作： CHANGE i v：将i节点权值变为v NEGATE a b：将ab路径上所有节点的权值变为相反数 QUERY a b：查询ab路径上节点权值的最大值。 解题思路：树链剖分，然后用线段树维护节点权值，成端更新查询。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10005; const int INF = 0x3f3f3f3f; int ...

题目链接：spoj 375. Query on a tree 题目大意： poj 3237的简化版，用同一份代码都能过。 解题思路：略。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10005; const int INF = 0x3f3f3f3f; #define lson(x) ((x)<<1) #define rson(x) (((x)<<1)|1) int val[maxn]; int lc[maxn << 2], rc[maxn << 2], s[maxn <&l...

题目链接：poj 3693 Maximum repetition substring 题目大意：求一个字符串中循环子串次数最多的子串。 解题思路：对字符串构建后缀数组，然后枚举循环长度，分区间确定。对于一个长度l，每次求出i和i+l的LCP，那么以i为起点，循环子串长度为l的子串的循环次数为LCP/l+1，然后再考虑一下从i-l+1~i之间有没有存在增长的可能性。 #include <cstdio> #include <cstring> #include <vector> #include <alg...

题目连接：zoj 3430 Detect the Virus 题目大意：给定一个编码完的串，将每一个字符对应着表的数值转换成6位二进制，然后以8为一个数值，重新形成字符 串，判断给定询问串是否含有字符集中的串。 解题思路：主要是题意，逆编码部分注意，转换完了之后，可能有字符'\0'，所以不能用字符串的形式储存，要用int型 的数组。注意有相同串的可能。 #include <cstdio> #include <cstring> #include <queue> #i...

题目链接：poj 2778 DNA Sequence 题目大意：给定一些含有疾病的DNA序列，现在给定DNA长度，问有多少种不同的DNA序列是健康的。 解题思路：对DNA片段建立AC自动机，因为最多10个串，每个串最长为10，所以最多可能有100个节点，在长度为n时 以每个节点终止的健康字符串个数形成一个状态集，通过AC自动机形成的边可以推导出n+1的状态集，走到单词节点是 非法的，所以同样的我们可以先走到单词节点，但是从单词节点不向后转...