cavenkaka
- 浏览: 205430 次
- 性别:
- 来自: 武汉
-
文章列表
字典树，又称单词查找树，Trie树，是一种树形结构，典型应用是用于统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度的减少无谓的字符串比较，查询效率比哈希表高。Trie树示意图如附件图所示：该trie树存有abc、d、da、dda四个字符串，如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL。Trie的特点：1. 根结点不包含任何字母。2. 其余结点仅包含一个字母(非元素)3. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 4. 每个结点的子节点包含字母不同。5. ...
今天闲来无事，观察了一下自己这么久做的题目，也总结了一下自己所做题的类型，基本上还处于最简单的那种题目的阶段，与大牛的差距还是非常之大。大致总结下，自己目前掌握了以下的知识：
题目大意：给你一段字符串，让你求出在中间最少加入几个字符可以让他变成一段回文子串。
解题思路：假设S是一段字符串，S'是S的逆串，则只需求出S与S'的最长公共子序列即可的长度即可，最后用字符串的长度减去最长公共子序列的长度即是这道题目所求的加入的字母的长度。转化为LCS问题即可
注意：本题的内存开销非常大，由于题目中给出0<=N<=5000，
1. 静态数组 开销大小为5001*5001的int是铁定超的.据说用short int的话不会MLE，有兴趣的同学可以试试
2.动态数组 单纯的申请动态数组是不能解决这个问题的，动态数组只能增加空间利用率，但是本题最恶劣的 ...
大致题意：
输入一个n层的三角形，第i层有i个数，求从第1层到第n层的所有路线中，权值之和最大的路线。
规定：第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。
解题方法：
用二维数组way[][]靠左存储三角形内的数据，那么连线规则变更为
way[i][j] → Way[i+1][j]
或 Way[i][j] → Way[i+1][j+1]
注意：way[][]初始化为输入时的三角形数值，此时way[i][j]表示该点位置上的权值，没输入的位置初始化为0。
代码如下：
#include <iostream>
using ...
题意解释：
有n个等级的珠宝，等级依次升高，等级越高价钱越高，每买一个等级的任何数量的珠宝必须多付10颗此种珠宝的价钱，可以用高等级的珠宝代替低等级的，问要买到若干规定的数量和等级珠宝的最少花费。例如买5颗价值为10的、100颗价值为20的珠宝，有两种方案：一种为分别买两种等级的珠宝价钱为(5+10)*10+(100+10)*20 = 2350；另一种是将等级低的（即价格低）的珠宝全部换为等级高的，此时价钱为(5+100+10)*20 = 2300，故第二种方案较优。
解题思路：
首先需要证明一点，用高一等级的代替低一等级的必须是连续代替。例如 3 5，90 7，100 12要想代替3 ...
是POJ2533的扩展题。题意不难，令到原队列的最少士兵出列后，使得新队列任意一个士兵都能看到左边或者右边的无穷远处。就是使新队列呈三角形分布就对了。士兵的排列就是如附件所示所示：图片中的蓝色士兵的身高和红色士兵的身高是完全没有关系的。
要求最少出列数，就是留队士兵人数最大，如图：
即左边的递增序列人数和右边的递减序列人数之和最大因而可转化为求“最长不降子序列”和“最长不升子序列”问题。进一步转化为从头部求出最长不下降子序列与从尾部求出最长不下降子序列即可，分别求出二者的大小，最后用队列长度减去二者之和就是我们所求的出列的士兵个数。
具体代码如下：
#inclu ...
在做这道题目之前，首先让我们了解一下什么是LIS算法，LIS俗称最长不下降子序列，最长不下降子序列是一个非常常见的小问题,首先让我们了解一下什么是LIS
一 LIS描述如下：
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lis=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
二 对于这类的题目一般有一下两种解法：
a、O(n^2)算法，思路如下：
（a[1]...a[n] 存的都是输入的数） 1、对于a[n]来说，由于它是最后 ...
从程序可以看出，第i个位置到L所删除的字符数，总是先取最坏情况，只有可以匹配单词时才进入第二条方程进行状态优化更新。
题意就是给出一个主串，和一本字典，问最少在主串删除多少字母，可以使其匹配到字典的单词序列。
PS:是匹配单词序列，而不是一个单词
不多说，看程序
主要是知道状态方程的含义
dp[i]表示从message中第i个字符开始，到第L个字符（结尾处）这段区间所删除的字符数，初始化为dp[L]=0
由于我的程序是从message尾部向头部检索匹配，所以是下面的状态方程：
dp[i]=dp[i+1]+1 不能匹配，最坏情况下删除最多字母
题意：
这道题的意思是给你一堆钱，各种面值的都有，比如10块的5张，5块的3张，2块的1张，请找出利用这些钱可以凑成的最接近且小于给定的数字cash的数额，比如cash=33块。我们可以取3张10块+2张1块=32，就是我们可以找到的那个最接近且小于33的数额。
思路：
多重背包问题的一种变形运用，比较简单。dp[i]用来表示第i大小金额的值是否能够取到。
代码如下：
#include <iostream>
using namespace std;
struct mac
{
int n;
int d;
}nd[1 ...
题意:给出字母个数,和有限个有序对(a<b)求出能确定字母序列的最少的条件个数.即,从第一个条件开始,往下,当加入某一条件时,如果能够确定这个序列,则输出这个序列,如果得出矛盾则说明冲突,如果所有条件都完毕也没有结果,则输出不能确定.思路:每读一个有序对,添加一条边,然后对其拓扑排序,如果成功,则输出序列,如果不成功,判断其是否有环,如果有环,输出冲突,如果没有定论,则读入下一个有序对.当所有有序对读完还没有结果,输出不能确定.
代码如下：
#include<iostream>
#include<cstdio>
#include<cstrin ...
大致题意:
科普文一篇，文章80%都是无用信息，因为都是常识，但是又不得不看，因为有20%是常人不知道的历史常识。
定义：
Goog month ： 该月第一个工作日为星期一的月份
Luckly month： 该月最后一个工作日为星期五的月份
问： 给定一个Gregorian Calendar格里高公历的 时间闭区间（就是包括端点的年月了）
【开始年、月】~【结束年、月】
在这个时间区间内，有多少个Goog month，有多少个Luckly month
文章要点：
Gregorian Calendar格里高公历 就是现在广泛使用公历（西历），下面简 ...
大致题意：
给定一个字符串，从任意位置把它切为两半，得到两条子串
定义 子串1为s1，子串2为s2，子串1的反串为s3，子串2的反串为s4
现在从s1 s2 s3 s4中任意取出两个串组合，问有多少种不同的组合方法
规定：
（1） 串Si不能和其 反串 组合
（2） Si+Sj 与 Sj+Si 是两种组合方式（但未必是不同的组合方式）
思路：字符串ELFHash 哈希，针对本题来说就是把组合后的字符串转化为数字存起来，进行比较。
代码如下：
//题意:给定一个字符串，从任意位置把它切为两半，得到两个子串
//定义子串1为s1，子 ...
题意：
定义D-pairs表示取字符串s中相距为D的两个字母所构成的字母对，该字母对中两个字母的位置顺序与他们在主串s中的位置顺序一致。定义D-unique表示，若从字符串s中取出所有相距为D的字母对D-pairs，且这些D-pairs都是独一无二的，那么成字符串s是一个D-unique串。D的取值范围为0~s.len()-2
思路：用STL里面的vector 即可 暴力破解：
代码如下：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
...
大致题意：
给出一个整数n，(1 <= n <= 200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。
解题思路：
首先暴力枚举肯定是不可能的 1000ms 想不超时都难，而且枚举还要解决大数问题。。
要不是人家把这题放到搜索，怎么也想不到用BFS。。。
题目大意是就是何处一个图，n个顶点和m条边，每个边都有最大承载量，现在我要从1点运送货物到n点，求能运送货物的最大重量。对于数据，第一行为t代表测试数据个数，第二行为n和m（意义见上），接着m行，每行三个整数分别是代表一条边的起点，终点及最大承重量。输出能运送货物的最大重量，格式见样例。注意数据输完后还要再多输一个空行。对于数据，从1运到3有两种方案方案1：1-2-3，其中1-2承重为3，2-3承重为5，则可以运送货物的最大重量是3（当大于3时明显1到不了2）方案2：1-3，可知1-3承重为4，故此路可运送货物的最大重量是4，故答案输出4
解题思路：这道题其实就是一个最短路径的变形问题， ...