cavenkaka
- 浏览: 197388 次
- 性别:
- 来自: 武汉
-
文章列表
题意：FJ有n头牛，编号为1~n，它们并没有按照编号的顺序排好队列。现在，FJ只知道每一个牛前面有多少只牛的编号比它大。问你能不能判断出所有牛的编号。
思路：线段树。关键：每次最后一只牛的编号是可以确定的，即为pre[i]+1，将其编号从所有牛中删除，则倒数第二只牛的编号又可以确定为pei[i]+1，依此类推。
代码如下：
#include<iostream>
using namespace std;
const int Max = 8005;
struct
{
int l, r, len; // 用len存储这个区间的数字个数。
...
题意：给出[1,n]区间内每个点的数值，让你执行下面的操作: 1. C a b w : 区间[a,b]上所有点的数值加上w。 2. Q a b : 输出区间[a,b]上所有点的数值之和。
思路：经典线段树。静态建树，成段修改，区间求和。用普通的线段树去做肯定超时，因为成段修改的时候会是o(n)。关键在于用add记录对应区间内所有元素的增量，并对查询函数进行相应的修改。注意修改和查询的一个很关键的性质：区间[node[u].left,node[u].right]必定包含区间[left,right]。
#include<iostream>
u ...
题意：Farmer John有n头牛按照编号顺序排好，第i头牛高度为hei[i]，现在给出区间[a,b]，问这个区间内的最高的牛和最低的牛相差多高。
思路：基础线段树。 静态建树，求区间最大值与最小值之差。跑得要点慢。
代码如下：
#include<iostream>
using namespace std;
const int Max = 50005;
struct
{
int l, r, max, min;
}node[3*Max];
int hei[Max], ma, mi;
int max1(int a, int b) ...
题意：略。
思路：基础的线段树，静态建树，更新结点，查询信息。代码如下：
#include<iostream>
using namespace std;
const int Max = 50005;
struct data
{
int l, r, num;
}node[3*Max]; // 线段树节点的数据结构。
int num[Max];
void BuildTree(int left, int right, int u)
{ // 建树。
node[u].l = left;
node[u].r ...
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
线段树至少支持下列操作：
Insert(t,x)：将包含在区间 int 的元素 x 插入到树t中； ...
题意：给你一个字符矩阵，求出它的最小覆盖子矩阵，即使得这个子矩阵的无限复制扩张之后的矩阵，能包含原来的矩阵。 即二维的最小覆盖子串。
思路：KMP很好的一道题。首先易证：最小覆盖子矩阵一定靠左上角。那么，我们考虑求出每一行的最小重复串长度，所有行的最小重复串的长度的lcm就是最小重复子矩阵的宽。然后我们对列也做相同的操作。于是我们就可以求得最小重复子矩阵的大小了。（这里要注意一点：当所得的宽大于原来的宽时，就让等于原来的宽，长也如此）。算法实现：算法的核心在于高效的求出每一行和每一列的最小重复串，这个可以最原串做一次KMP中的get_next()。（注：以上部分为转载）
代码如下：
...
题意：给你n个的串，求出它们的最长公共子串，如果不存在这个子串，则输出“IDENTITY LOST”，如果存在多个最长公共子串，则输出字典序最小的那一个。
思路：枚举+KMP。与poj3080类似，详情见poj3080
#include<iostream>
#include<cstring>
using namespace std;
const int nMax = 4002;
const int mMax = 202;
char text[nMax][mMax], pat[mMax];
int n, ma, lent[nMax], le ...
题意：给你n个长度都为60的串，求出它们的最长公共子串，如果这个子串的长度 < 3则输出“no significant commonalities”，如果存在多个最长公共子串，则输出字典序最小的那一个。
思路：枚举+KMP。枚举第一个串的所有后缀串（而不是枚举第一个串的所有子串），每一个后缀串做一次KMP，求出这些串的与其余所有串的最长匹配。
#include<iostream>
#include<cstring>
using namespace std;
const int Max = 62;
char text[10][Max], ...
题意：给你一个字串（模式串）和一个母串（文本），问字串在母串中出现的次数。
思路：最基础的KMP算法。在匹配完成一个之后，应该j=next[j],不能j=0，保证模式串在文本的所有种出现情况都包含到，这里注意下就可以了。
代码如下：
// #include<iostream>
#include <iostream>
using namespace std;
const int pMax=10005;
const int tMax=1000005;
int next[pMax];
int lenp,lent;
char text[tMax ...
题意：给你一个串，如果这个串存在一个长度为n的前缀串，和长度为n的后缀串，并且这两个串相等，则输出他们的长度n。求出所有的长度n。
思路：KMP中的get_next()。对前缀函数next[]又有了进一步的理解，str[1]~~str[next[len]]中的内容一定能与str[1+len-next[len]]~~str[len]匹配（图1）。然后呢我们循环地利用next，由于next的性质，即在图2中若左红串与左绿串匹配，则左红串比与右绿串匹配，因为图1
这题可以加深对KMP的懂得！题意：给出一个字符串，对于它的每个（each）前缀（prefix）长度 i （2<=i），求能由一个子串构成这个前缀的最大字串数量。看例子可以清楚些吧。我是看别人的才知道的。具体看以参考：
http://jovesky.info/blog/2011/08/25/poj-1961-period-c-language-version/
例子：
字符串为aabaabaabaab前2位也就是aa是a反复2次前6位也就是aabaab是aab反复2次前9位也就是aabaabaab是aab反复3次前12位也就是aabaabaabaab是aab反复4次
解题思路：经由过 ...
字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
一：让我们先来看基本的简单匹配算法：
先来看一个简单匹 ...
大致题意：
输入一个字典，字典格式为“英语à外语”的一一映射关系
然后输入若干个外语单词，输出他们的 英语翻译单词，如果字典中不存在这个单词，则输出“eh”
解题思路：trie树
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
const int Max = 260050;
const int branchNum = 26;
struct tree_node
{
char re[11]; // 存储对 ...
题意：给出n个数字串，问其中是否有一个串是另一个串的前缀。（静态建树的模板）
思路：基础的Trie。必须使用静态建树，否则会超时。还有就是有可能是前面的串是后面的串的前缀，也有可能后面的串是前面的串的前缀，如：
221122121
代码如下：
#include<iostream>
using namespace std;
const int Max = 100000;
const int branchNum = 10;
struct tree_node
{
bool isstr;
tree_node *next[branc ...
题意：给出n个单词（1<=n<=1000），求出每个单词的非公共前缀，如果没有，则输出自己。
思路：基础的trie。
只要基本了解Trie的构造与查找过程，就可以去做了。
代码如下所示：
#include<iostream>
using namespace std;
const int Max = 1002;
const int branchNum = 26;
struct tree_node
{
int count; // 记录用到这个节点的单词数量，如果=1，则证明其为这个单词唯一的节点。
tree_nod ...