- 浏览: 201990 次
- 性别:
- 来自: 武汉
文章列表
poj 3253STL建立哈弗曼树
- 博客分类:
- 哈弗曼树
题意:给你n块长度已知的木板,已知FJ每次能连接两个木板成为一个新的木板,新的木板长度为两块木板之和。问FJ把n块木板连接起来成最后的一块木板的长度最小是多少?
思路:基础的haffman树。用优先队列去做,要记住haffman几段关键的代码。
还是stl写的猛!!!这个题目倒不是很难(毕竟有discuss,呵呵),就看成赫夫曼树,然后求所有非叶子节点的总和就行了。不过看算法导论上将建立赫夫曼树要用到优先级队列,这个我还真懒的写,呵呵,所以就现学的优先队列。
代码如下:
#include <iostream>
#include <queue>
usin ...
题意:在平面内给出n个点,问你这些点一共能组成几个不相等的正方形?
思路:几何 + 二分。先排序,然后枚举任意两点(x1,y1)(x2,y2),则如果存在点(x1+y1-y2,y1-x1+x2)(x2+y1-y2,y2-x1+x2)则它们能构成一个正方形(这里方向是确定的,否则还有一种可能)。所以用二分查询是否存在这两个点,有的话ans就+1。最后的ans要/2,因为正方形都重复算了一次。
关于二分查找的代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
cons ...
题意:对于方程:a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0 ,有xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}. 现在给出a1,a2,a3,a4,a5的值,求出满足上面方程的解有多少个。
思路:hash的应用。暴力枚举的话会达到100^5,明显会超时。所以将方程分成a1x13+ a2x23 和 -(a3x33+a4x43+ a5x53 )两部分,若这两部分相等,则为方程的一个解。
一开始以为hash的优化效果不会很明显,因为觉得代码的大部分时间会消耗在o(100^3)求方程后部分的值上,后来看了别人的解题报告,发 ...
题意:判断有没有两朵相同的雪花。每朵雪花有六瓣,比较花瓣长度的方法看是否是一样的,如果对应的arms有相同的长度说明是一样的。给出n朵,只要有两朵是一样的就输出有Twin snowflakes found.,如果任何两个都是不一样的输出No two snowflakes are alike。n=100,000。
思路:最简单的就是枚举每两片雪花,判断他们是否相同。时间复杂度为O(n*n),显然效果不理想。有没有更好的算法呢?hash:每读进一片雪花,将雪花hash,判断hash表里是否有相同的hash值,有相同的hash值,从链表中一一取出并判断是否同构,是同构得出结果。然后将该雪花加入到 ...
数据结构者,“数据间关系+数据存储方式”也。
选择何种数据结构,取决于需要解决什么样的问题。
任何一个数据结构都有它的优势,这个优势说白了就是“本数据结构在进行XX操作时快”,而选择何种数据结构就看要解决的问题需要在数据结构上进行何种操作来决定。
哈希表就是体现这个道理的一个很好的例子。
哈希表提供这么一种其它数据结构并不擅长的操作:
“在理想情况下,能用常量时间查找到指定值的数据
题意:给出一个长度为n的数列,你每一次可以随意交换其中两个数字的位置。问你至少交换几次,才能使得这个数列是个单调递增数列。
思路:逆序数。归并排序求逆序数:
归并排序主要是二路归并排序,采用分治的思想:对于某个数组a[n]排序,先将前半部分排序,再将后半部分排序,最后归并两部分。归并排序是一种稳定的排序方式,且时间复杂度为O(n*log2n)。归并排序还可以求一串数中的逆序数。在归并相邻的两个有序子数组:
XlowXlow+1Xlow+2...Xmid和Ymid+1Y2Y3Y4..Yhigh的过程中,令i=low,j=mid+1,其中:
排序分为以下几大类:a:插入排序;b:选择排序;c:交换排序;d:归并排序;e:基数排序。
a:插入排序:分为直接插入排序与希尔排序。直接插入排序的思想是:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序,时间复杂性为o(n^2),空间复杂度为O(1)。
poj 2388代码:
#include <iostream>
u ...
题意大概是农场主要找出体重处于中间的母牛,实际上是要求在规定时间内给出一组数据的中间数,说白了,就是各种排序,数据的个数是奇数,n/2正好处于中间,可以用STL模板,也可以不用,代码分别如下:
代码一:不用STL模板。自己写的快速排序:
#include <iostream>
using namespace std;
const int Max=10002;
void QuickSort(int a[],int low,int high)
{
int i,j;
if(low>high)
return;
i=low;
j=high;
i ...
关于图论的一些问题暂时到此结束,下面进入数据结构专题,首先讨论串的问题:
题意:
先输入一个字典,再输入一些字符串,在字典里找到与该字符串相同的单词,若没有,找到与其差一个的单词:多一个字符or少一个字符or错一个字符
输入:
一个字典,#结束
输入n个字符串,在字典中查找,一共有五种情况:
输出:
** is correct
String: string1 string 2
关于输出的操作,一共分为五种情况 a:两个单词完全一致,则输出 **is correct
如果长度相差为一或者为O(有一个单词不一样),这时有二种情况,1: 相差为一(分为两种情况1:大于一2 ...
poj 3259
- 博客分类:
- bell_flaod算法
- c++
- 最短路径
题意:John的农场里field块地,path条路连接两块地,hole个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来,看到了离开之前的自己。
思路:bellman_ford。 ...
poj 1860
- 博客分类:
- 最短路径
- c++
- bell_flaod算法
提示:关键在于反向利用Bellman-Ford算法
题目大意
有多种汇币,汇币之间可以交换,这需要手续费,当你用100A币交换B币时,A到B的汇率是29.75,手续费是0.39,那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加
货币的交换是可以重复多次的,所以我们需要找出是否存在正权回路,且最后得到的s金额是增加的
poj 1125
题目大意是股票经纪人要在一群人中散布一个谣言,而谣言只能在亲密的人中传递,题目各处了人与人之间的关系及传递谣言所用的时间,要求程序给出应以那个人为起点,可以在最短的时间内让所有的人都得知这个谣言。要注意从a到b传递的时间不一定等于从b到a的时间,如果没有方案能够让每一个人都知道谣言,则输出"disjoint"。(有关图的连通性,你懂得!但好像不用考虑这种情况一样能AC,只能说测试数据有点小水!)题目数据的输入第一行为n,代表总人数,当n=0时结束程序,接着n行,第i+1行的第一个是一个整数t,表示第i个人与t个人的关系要好,接着有t对整数,每对的第一个数 ...
folyd思想(动归,可以包含负权值的边,但不能有负环):
将图G中顶点编号,从1到n。现在考虑从i到j的最短路径,若k是这条路上的中间结点,那么由i到k和由k到j的这两条子路径应分别是由i到k和由k到j的最短路径。否则,这条由i到j的路径就不是具有最小长度的路径。于是,最优性原理成立,这表明有使用动态规划的可能性。如果k是编号最高的中间结点,那么由i到k的这条路径上就不会有比k-1更大的结点通过。同样,由k到j路径上也不会有比k-1更大的结点通过。因此,可以把求取一条由i到j的最短路径看成如下过程:首先需要决策哪一个结点是该路径上具有最大编号的中间结点k,然后就再去求由i到k和 ...
在一个图中,若从一个结点到另一个结点存在着路径,定义路径长度为一条路径上所经过的边的权值之和。从一个结点到令一个结点可能存在着多条路径,路径最短的那条称作最短路径,其长度成为最短路径长度或者最短距 ...
kruskal思想:
对图G的所有边按权值从小到大排序,每次取一条边,若此边的两个结点属于同一个连通分量,则舍弃这条边;若不属于同一个连通分量,则将这条边加入到最小生成树中。当所有结点属于同一个连通分量时,构造完毕。
kruskal设计:
一个边的结构体。有几个关键问题:
如何判断两个结点是否属于一个连通分量:
每个连通分量都用其中一个结点来标识,p[]数组用来表示结点的父节点(初始p[i]=i),真正的头结点满足p[i]=i;首先根据传进来的边的两个顶点,用findSet找出点所属的父节点(递归,条件x==p[x]),若父节点相同,显然属于同一个连通分 ...