128kj
- 浏览: 600500 次
- 来自: ...
-
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
文章列表
关于树状数组,参看:http://128kj.iteye.com/blog/1743633
POJ3067题意：
东海岸与西海岸分别有N和M个城市，现在修高速公路连接东西海岸的城市，求交点个数。
做法：记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时，满足（x1-x2）*（y1-y2） < 0。所以，将每条路按x从小到达排序，若x相同，按y从小到大排序。 然后按排序后的公路用树状数组在线更新，求y的逆序数之和即为交点个数。
详细说明如下。 记第i条边的端点分别为xi,yi。
由于x是从小到大排序的，假设当前我们在处理第k条 ...
public class biSearch {
/**
* @param args
* 作者：undoner
/*
折半查找--当查找表是有序表时，可采用折半查找;
基本思想：在有序表中，取中间元素作为比较对象，若给定值K与中间记录关键字相等，则查找成功；
若给定值K小于中间记录的关键字，则在表的左半区继续查找；
若给定值K大于中间记录的关键字，则在表的右半区继续查找，不断重复，直到查找成功/失败。
*/
//折半查找非递归算法
//查询成功返回该对象的下标序 ...
public class seqSearch {
/**
* @param args
*/
/*
顺序查找又称线性查找;
基本思想：从查找表的一端开始，向另一端逐个按给定值K与关键字进行比较，若找到，查找成功;
并给出记录在表中的位置；若整个表检测完，仍未找到与K值相同的关键字，则查找失败;
优点：对表中数据的存储没有要求，对于链表，只能进行顺序查找；
缺点：当n值很大时，平均查找长度较大，效率低；
*/
//无监视哨的情况，查询成功返回该对象的下标序号，失败时返回 ...
关于树状数组，请参考：http://128kj.iteye.com/blog/1743633
POJ 2481题意：
有n头牛(编号为1~n)，每一头牛都有一个吃草区间[S, E]，如果对于牛i和牛j来说，它们的吃草区间满足下面的条件则证明牛i比牛j强壮：Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的吃草区间，要求输出每头牛有几头牛比其强壮。
其中:1 <= N <= 100000, 0 <= S < E <= 100000
样例:
Sample Input
3 ...
一、树状数组是干什么的？
平常我们会遇到一些对数组进行维护查询的操作，比较常见的如，修改某点的值、
求某个区间的和，而这两种恰恰是树状数组的强项！当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是O(N)，如果实时的对数组进行M次修改或求和，最坏的情况下复杂度是O(M*N)，当规模增大后这是划不来的！而树状数组干同样的事复杂度却是O(M*lgN)，别小看这个lg，很大的数一lg就很小了。
二、树状数组的定义
如图所示，红色矩形表示的数组C[]就是树状数组。
给定序列（数列）A，我们设一个数组C满足
C1 = ...
import java.util.Scanner;
/*线段树空间计算程序 Power By:Comzyh*/
class segment {//线段树节点
int b,e;
}
public class SegmentTree{//线段树，用数组实现
static int M=5000000;
segment seg[];
int Nnode;//节点数
int LastNode;//最后一个节点
public ...
解题中经常用到自定义排序，把这篇文章放到这里备用。
当需要排序的集合或数组不是单纯的数字型时，通常要用到两个接口Comparator或Comparable，以简单的方式实现对象排序或自定义排序。
一、Comparator
强行对某个对象collection进行整体排序的比较函数，可以将Comparator传递给Collections.sort或Arrays.sort。
接口方法：
/**
* @return o1小于、等于或大于o2，分别返回负整数、零或正整数。
*/
int compare(Object o1, Object o2);
例：
import java.u ...
POJ2299题意：
给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。例如将"91054"变成"01459",最小交换6次,如果直接暴力，会超时。
样例:(2次测试)
Sample Input
5 序列中数的个数
9
1
0
5
4
3 序列中数的个数
1
2
3
0 n=0结束
Sample Output
6
0
其中需排序的数的范围0---999 999 999；显然数组不能开这么大,序列中数的个数N不大于500000,故先要将给出的序列离散到[1,500000]。
例: in ...
离散化是一种常用的技巧，有时数据范围太大，可以用来放缩到我们能处理的范围。
比如：数的范围0---999 999 999，而数的个数N不大于500000,故给出的数一定可以与1.。。。N建立一个一一映射；
例: int a[] = {10000000, 10, 2000, 20, 300};
那么离散化后a[] = {5, 1, 4, 2, 3},是一个一一对应关系，而且满足原来的大小关系，
有些情况下它们可以互相替代。
下面是代码：
import java.util.Scanner;
import java.util.Arrays;
import java.util.Compa ...
设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下，有A[i]>A[j]，则（i，j）就称为A中的一个逆序对（inversion）
现给出一个数列，求该数列中的逆序对数（逆序数）。最直接的暴力方法；
两层for循环就可以算出来逆序数：每遇到一个元素回头遍历寻找比其大的元素个数即可，
当然向后寻找比其小的元素个数也可以，复杂度为O(n^2)，代码：
int sum = 0;
for(int i = 0; i < size; ++i) {
for(int j = i+1; j < size; ++j){
...
问题：有n只奶牛排成一列，他们有各自的身高Hi，有Q个区间，分别求出这些区间中最高和最矮的差值。
Sample Input
6 3 (六只奶牛，下面分别是它们的身高，3个区间)
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.Outpu ...
在http://poj.org/上用JAVA解题一般用Scanner类来进行输入，但对时间要求严格的题，用它可能会超时，我解POJ1823的时候就遇到这样的问题，后改用StreamTokenizer类进行输入，就过了。看来后者处理输入的效率要高点。
现小结如下：
1、类java.io.StreamTokenizer可以获取输入流并将其分析为Token（标记）。
StreamTokenizer的nextToken方法读取下一个标记
2、默认情况下，StreamTokenizer认为下列内容是Token:字母、数字、除c和c++注释符号以外的其他符号。
如符号“/”不是Toke ...
继续上文"线段树入门学习(二）" http://128kj.iteye.com/blog/1739064
请先看题POJ1823:
旅馆有三种操作：1入住，同时给你两个数i，M，其中i表示连续房间的起始房号，M表示房间数量；2退房，同时给你两个数i，M，其中i表示连续房间的起始房号；3查询，要求输出整个旅馆中，房号相连的最大空房间数量。
样例：
Sample Input
12 10 (房间号1 -12,有10个操作)
3
1 2 3
1 9 4
3
2 2 1
3
2 9 2
3
2 3 2
3
Sample Output
12
4
4
6
10
网上大 ...
继续上文http://128kj.iteye.com/blog/1738772：
在那里用链状结构实现了二叉线段树，下面程序使用一维数组以完全二叉树的方式来存储。
先看一维数组存储线段树到底需要开多大的数组，网上有一个计算程序：
import java.util.Scanner ...
先看网上的介绍：
线段树也叫区间树，顾名思义，线段树是一种基于区间的树，每个节点表示一个“线段”或“区间”。树的根节点表示是“整体”的区间，左右子树分别表示这个区间的左半边和右半边。
基本结构及性质
假设要构造一个表示N个区间大小的线段树，线段树的根节点表示区间[0,N-1]，然后将区间分成两半，分别为左右子树表示，这样的线段树的节点只有2N-1个，是O(N)级别的，如图所示表示构造区间[1-5]的线段树。
1）存储：
线段树可以使用链状结构动态构造，这样的优点是节省空间，空间复杂度在2N，但是缺点就是编程复杂度大，执行效率低；
所以线段树一般是使用一维数组以 ...