Monthly Archives: July 2010

java简单上手

对于ACMer来说,java语言最大的优势就是BigInteger,Bigecimal,String三个类.这三个类分别是高精度整数,高精度浮点数和字符串,之所以说这个是它的优势是因为java的这三个类有丰富的成员函数可以调用,在比赛中可以省去敲大数模板的时间.

这里只讲一些在短时间内上手java的基础知识,java是一门非常强大的语言,要深入学习是需要花很长时间的.

一.准备工作

安装JDK (java development kit即JAVA开发工具包)

这里首先需要说明一下java的一些特殊性.一般我们的教材上介绍程序设计语言时会把它们按照运行方式的不同分为解释型和编译型(概念略),虽然java也有一个虚拟机来"解释执行",但java并不是完全的解释型也不是编译型,可以认为是"部分"编译.一个java程序经过"编译"变成字节码再运行在虚拟机上,所以它比一般的编译型程序慢,比一般的解释型程序快.

如果你在至诚ACM的机房看这篇文章,以上的一大段都是废话了解一下就行,请跳到下面的"第一个Java程序"开始看.
这里我们使用的是JDK6,可以到SUN的网站下载:http://www.oracle.com/technetwork/java/javase/downloads/index.html
下载完成后,安装按默认路径即可。

配置环境变量如下:

JAVA_HOME = C:Program FilsJavajdk1.6.0_20 (版本不同路径会略有不同)
PATH = %JAVA_HOME%bin;%JAVA_HOME%lib;%JAVA_HOME%jrelib;
CLASSPATH = .;%java_home%lib;%java_home%libtools.jar (前面要加.表示当前路径).

其实到这里Java的开发环境就已经完成了,但是对于不熟悉命令行编译的朋友最好能安装一个IDE(Integrated Development,集成开发环境).

现在比较流行的Java集成开发环境有IBM的Eclipse和Sun的Netbeans.至于安装配置什么的对于软件专业的学生应该不是什么难事,实在不行Google一下.
Eclipse:http://www.eclipse.org/downloads/
Netbeans:http://zh-cn.netbeans.org/

其实我个人还是推荐使用Netbeans,java和Netbeans都是Sun的东西,Sun对自家的东西自然会支持的好一些.
知道Eclipse这个单词是什么意思么?查一下,很有趣的.

二.第一个java程序

用任何你喜欢的编辑器(比如我最长用的是Vim)写如下代码:

public class Main{
    public static void main(String[] argc)
      {
		System.out.println("Hello World");
      }
}

并保存为Main.java
(注意大小写,Java是大小写敏感的语言,你的类名和这个文件名必须相同)

在命令行下输入

javac Main.java  //编译
java Main        //运行

Read more »

PKU 2823 解题报告

Sliding Window

Time Limit: 12000MS Memory Limit: 65536K
Case Time Limit: 5000MS

Description

An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position Minimum value Maximum value
[1  3  -1] -3  5  3  6  7  -1 3
 1 [3  -1  -3] 5  3  6  7  -3 3
 1  3 [-1  -3  5] 3  6  7  -3 5
 1  3  -1 [-3  5  3] 6  7  -3 5
 1  3  -1  -3 [5  3  6] 7  3 6
 1  3  -1  -3  5 [3  6  7] 3 7

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Read more »

PKU 2559解题报告

Largest Rectangle in a Histogram

Time Limit: 1000MS Memory Limit: 65536K

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,...,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Read more »

SGU 111 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=111

111. Very simple problem

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

You are given natural number X. Find such maximum integer number that it square is not greater than X.

Input

Input file contains number X (1≤X≤101000).

Output

Write answer in output file.

Read more »