believexkx
- 浏览: 21514 次
- 性别:
- 来自: 济南
-
最新评论
文章列表
一、图的基本算法 1.广度优先搜索（BFS[breadth-first search]） //如果用邻接矩阵来遍历，需要O(v^2);如果用邻接表遍历，需要O(v+e) 2.深度优先搜索（DFS[depth-first search]）//如果用邻接矩阵来遍历，需要O(v^2);如果用邻接表遍历 ...
题意：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 ...
今天从网上搜教程，自己动手在Eclipse下安装了C++ CDT插件。主要是这几天刷题，确实感觉有时C++比java效率高，因此想学C++了。
首先下载CDT，下载地址如下（要先注册登录才能下载）
http://download.csdn.net/download/microsoftguy/2104012
安装在任意目录下，但注意解压之后有features和plugins两个文件夹，需要把它们复制到Eclipse的安装目录下，再重启Eclipse即可。
当建立新的工程的时侯，就可以看到已经有了 C 及 C++ 的选项，代表安装成功了。
二、下载安装MinGW
下载地址http://sourc ...
此题用java解和C++解，差距足够足够大，如下图
原题http://poj.org/problem?id=2823
解题思路
这题还可以用单调队列进行求解。开两个队列，一个维护最大值，一个维护最小值。下面叙述最大队列，最小队列的方法类似。
最大队列保证队列中各个元素大小单调递减（注意，不是单调不上升），同时每个元素的下标单调递增。这样便保证队首元素最大，而且更新的时候队首永远是当前最大。因此，这个队列需要在两头都可以进行删除，在队尾插入。
维护方法：在每次插入的时候，先判断队尾元素，如果不比待插入元素大就删除，不断删除队尾直到队尾元素大于待插入元素或者队空。删除的时候，判断队首，如 ...
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(l ...
整数的快速幂
//递归写法
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;
...
完全背包：
完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
完全背包按其思路仍然可以用一个二维数组来写出：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
同样可以转换成一维数组来表示：
伪代码如下：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
顺序！
想必大家看 ...
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];
}
v ...
并查集：(union-find sets)
一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数等。最完美的应用当属：实现Kruskar算法求最小生成树。
...
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背包的状态转移方程为（二 ...
在写这道题之前，先介绍几点知识。
一、动态规划（DP）
动态规划（dynamic programming）是求解决策过程最优化的数学方法。早在20世纪50年代初美国数学家R.E.Bellman等人就提出了著名的最优化原理，把多阶段过程转化为一系列单阶 ...
URAL1654 也是一个典型的栈的问题，只不过这次进栈的是字母而不是HDU1022的火车了
http://acm.timus.ru/problem.aspx?space=1&num=1654
这个题的代码技巧比较高，如果写得妙的话，短短几行就可搞定，当然需要基本功扎实。比如说，这道题首先想到的是用Stack类，然后运用StringBuffer类进行输出，其中的几个方法功能、传入参数、返回值一定要记熟，用起来才游刃有余，如
Ⅰ.append(Object o) 将o追击到此序列，返回StringBuffer类
Ⅱ.charAt(int index) 返回此序列中指定索引处的char值 ...
查看此图便会很容易的理解什么是栈了——就是只有一个入口（封闭的容器）,所以栈的特点就是先进后出，或者后进先出。
提到栈，不得不提指针，进栈时先移指针后进栈，出栈时先出栈后移指针。
下面要说的，此堆非彼堆：
栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。另外，栈数据可以共享。堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。
另说下java中==和equals的区别，也加深对栈和堆的理解
==比 ...
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
{
...
从7月16日就开始进行训练了，但是一直到现在感觉对各种算法理解不透彻，脑子里根本知识框架都没有，从今天起，开始整理自己所学的ACM的知识，发表的博客文章也希望对读者有所帮助，也希望有什么好的算法与大家分享~
现在就从最基础的队列来讲，队列最基础的原理就是先进先出，以java为例，用到的类库有PriorityQueue、Queue，里面的好多方法大家查一下API，现在介绍几个比较常用的方法。
PriorityQueue<E>中实现Comparable<>接口，自己根据题意写此接口
Ⅰ.add(E e)将指定元素插入此优先队列中，返回boolean值
Ⅱ.peek() 获取 ...