ITeye博客

从此爱上猫

believexkx · 共 15 篇文章

简单的图论算法

一、图的基本算法 1. 广度优先搜索 (BFS[breadth-first search]) //如果用邻接矩阵来遍历,需要O(v^2);如果用邻接表遍历,需要O(v+e) 2. 深度优先搜索 (DFS[depth-first search])//如果用邻接矩阵来遍历,需要O(v^2);如果用邻接表遍历,需要O(v+e) 3. 拓扑排序 (topological sorting) //O(v+e) 对一个**有向无环图(**Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现…

2012-08-21 23:23 · 图论 · 评论(0)

HDU 1241 Oil Deposits DFS

题意:N*M的图中有一些'@',从该位置往四周8个位置延伸,求几块互不连通的‘@’构成的块。简单的DFS便能搞定 import java.util.Scanner; public class Main{ static int m,n; static char[][] arr=new char[101][101]; public static void main(String[] args) { Scanner scan=new Scanner(System.in); while(true) { m=scan.nextInt(); n=scan.nextInt(); if(m==0) brea…

2012-08-17 22:06 · 图论 · 评论(0)

Eclipse下安装CDT插件,astyle插件

今天从网上搜教程,自己动手在Eclipse下安装了C++ CDT插件。主要是这几天刷题,确实感觉有时C++比java效率高,因此想学C++了。 首先下载CDT,下载地址如下(要先注册登录才能下载) http://download.csdn.net/download/microsoftguy/2104012 安装在任意目录下,但注意解压之后有features和plugins两个文件夹,需要把它们复制到Eclipse的安装目录下,再重启Eclipse即可。 当建立新的工程的时侯,就可以看到已经有了 C 及 C++ 的选项,代表安装成功了。 二、下载安装MinGW 下载地址 http://sour…

2012-08-15 18:49 · CDT插件 · 评论(0)

POJ2823 单调队列

此题用java解和C++解,差距足够足够大,如下图 原题 http://poj.org/problem?id=2823 解题思路 这题还可以用单调队列进行求解。开两个队列,一个维护最大值,一个维护最小值。下面叙述最大队列,最小队列的方法类似。 最大队列保证队列中各个元素大小单调递减(注意,不是单调不上升),同时每个元素的下标单调递增。这样便保证队首元素最大,而且更新的时候队首永远是当前最大。因此,这个队列需要在两头都可以进行删除,在队尾插入。 维护方法 :在每次插入的时候,先判断队尾元素,如果不比待插入元素大就删除,不断删除队尾直到队尾元素大于待插入元素或者队空。删除的时候,判断队首,如果队…

2012-08-13 11:22 · 单调队列 · 评论(0)

POJ3070Fibonacci 矩阵快速幂

POJ3070原题 http://poj.org/problem?id=3070 如图,Fibonacci矩阵解法: import java.util.Scanner; public class Main { Scanner scan=new Scanner(System.in); long n; int w=10000; long[][] a=new long[2][2]; public static void main(String[] args) { new Main().run(); } long[][] multi(long[][] b,long[][] a) { long[][]…

2012-08-12 10:05 · 快速幂 · 评论(0)

POJ1995&& HDU2035 整数快速幂

整数的快速幂 //递归写法 int fastpow(int a,int p) { if(p==0) return 1; if(p%2==1) { int temp=fastpow(a,(p-1)/2); return temp*temp*a; }else{ int temp=fastpow(a,p/2); return temp*temp; } } //非递归写法 int fastpow(int a,int p) { int ret=1; while(p>0) { if(p%2==1) ret=ret*a; a=a*a; p>>=1; } return ret; } 能在 O(log n) …

2012-08-12 09:42 · 快速幂 · 评论(0)

HDU1114 完全背包

完全背包: 完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c*,价值是w*。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 完全背包按其思路仍然可以用一个二维数组来写出: f*=max{f]+k w |0<=k c <=v} 同样可以转换成一维数组来表示: 伪代码如下: for i=1..N for v=0..V f=max{f,f]+w*} 顺序! 想必大家看出了和01背包的区别,这里的内循环是顺序的,而01背包是逆序的。 现在关键的是考虑:为何完全背包可以这么写? 在次我们先来回忆下,01背…

2012-08-11 20:51 · 背包 · 评论(0)

POJ1611The Suspects

http://poj.org/problem?id=1611 import java.util.*; public class Main { Scanner scan=new Scanner(System.in); int[] arr=new int[30010],num=new int[30010]; public static void main(String[] args) { new Main().run(); } int find(int x) { if(arr[x]!=x) arr[x]=find(arr[x]); return arr[x]; } void merge(int …

2012-08-10 08:58 · 并查集 · 评论(0)

POJ2524 并查集 Ubiquitous Religions

并查集:(union-find sets) 一种简单的用途广泛的集合. 并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多,如其求无向图的连通分量个数等。最完美的应用当属:实现Kruskar算法求最小生成树。 http://poj.org/problem?id=2524 import java.util.Scanner; public class Main { Scanner scan=new Scanner(System.in); int[] p=new int[50010]; int num;//最终统计数目 int find(int x) { if(p[x]…

2012-08-10 08:55 · 并查集 · 评论(0)

POJ 3624 01背包问题

01背包问题是动态规划中很基础也很经典的问题,给大家推荐一个网址(背包 九讲),里面讲的很详细。 http://love-oriented.com/pack/P01.html 按我的理解,01背包就是一种特定价值的物品放到背包中去,要么放,要么不放。循环中嵌套的循环用逆序,复杂度为O(N*W) POJ3624原题为 http://poj.org/problem?id=3624 import java.util.Scanner; public class Main { Scanner scan=new Scanner(System.in); /*01背包的状态转移方程为(二维) * f[i][…

2012-08-07 14:23 · 背包 · 评论(0)

POJ 3253--Fence Repair

在写这道题之前,先介绍几点知识。 一、 动态规划(DP) 动态规划(dynamic programming)是求解决策过程最优化的数学方法。早在20世纪50年代初美国数学家R.E.Bellman等人就提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。 DP是对解最优化问题的一种途径、一种方法,而不是一种特殊算法…

2012-07-26 22:31 · DP · 评论(0)

URAL1654 Cipher Message

URAL1654 也是一个典型的栈的问题,只不过这次进栈的是字母而不是HDU1022的火车了 http://acm.timus.ru/problem.aspx?space=1&num=1654 这个题的代码技巧比较高,如果写得妙的话,短短几行就可搞定,当然需要基本功扎实。比如说,这道题首先想到的是用Stack类,然后运用StringBuffer类进行输出,其中的几个方法功能、传入参数、返回值一定要记熟,用起来才游刃有余,如 Ⅰ.append(Object o) 将o追击到此序列,返回StringBuffer类 Ⅱ.charAt(int index) 返回此序列中指定索引处的char值 Ⅲ.i…

2012-07-26 17:37 · 栈 · 评论(0)

HDU1022 Train Problem

查看此图便会很容易的理解什么是栈了——就是只有一个入口(封闭的容器),所以栈的特点就是先进后出,或者后进先出。 提到栈,不得不提指针,进栈时先移指针后进栈,出栈时先出栈后移指针。 下面要说的,此堆非彼堆: 栈的优势是,存取速度比堆要快,仅次于直接位于CPU中的寄存器。但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性。另外,栈数据可以共享。堆的优势是可以动态地分配内存大小,生存期也不必事先告诉编译器,Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是,由于要在运行时动态分配内存,存取速度较慢。 另说下java中==和equals的区别,也加深对栈和堆的理解 ==比较的是两个…

2012-07-26 16:36 · 栈 · 评论(0)

POJ 3629 Card Stacking

POJ 3629也是一个队列题,大意是N个人,K张牌(K是N的整数倍),发牌的人最后发给自己,为了防止发牌者把好牌发给自己,每发一个人便把牌往后挪P张。但每个人都想得到好牌,则设计个程序计算发牌者为了得到好牌应将好牌放到第几位,并按顺序输出。 http://poj.org/problem?id=3629 模拟此发牌过程的算法为: import java.util.Scanner; import java.util.Queue; import java.util.LinkedList; import java.util.Arrays; public class Main { public st…

2012-07-26 16:09 · 优先队列 · 评论(0)

POJ2051 Argus 优先队列

从7月16日就开始进行训练了,但是一直到现在感觉对各种算法理解不透彻,脑子里根本知识框架都没有,从今天起,开始整理自己所学的ACM的知识,发表的博客文章也希望对读者有所帮助,也希望有什么好的算法与大家分享~ 现在就从最基础的队列来讲,队列最基础的原理就是先进先出,以java为例,用到的类库有PriorityQueue、Queue,里面的好多方法大家查一下API,现在介绍几个比较常用的方法。 PriorityQueue 中实现Comparable<>接口,自己根据题意写此接口 Ⅰ.add(E e)将指定元素插入此优先队列中,返回boolean值 Ⅱ.peek() 获取但不移除此队列的头,如果此…

2012-07-26 15:02 · 优先队列 · 评论(0)