Java in ACM/ICPC

Java在ACM/ICPC中的特点
在ACM/ICPC中使用Java需要注意的问题
Java与高精度计算

1.Java在ACM/ICPC中的特点

Java的语法和C++几乎相同

Java在执行计算密集任务的时候并不比C/C++慢多少，只是IO操作较慢而已

Java 简单而功能强大，有些东西用Java实现起来更为方便

比如：输入输出、字符串解析、高精度

Java不易犯细微的错误

C/C++中的指针

“if (n = m) ... ”

Java与Eclipse

2.在ACM/ICPC中使用Java需要注意的问题

java程序结构

Java in ACM/ICPC-LMLPHP

Java I/O

JDK1.5.0新增的Scanner类很适合用于AMC/ICPC的输入

使用Scanner类的一般步骤

1.导入Scanner类

import java.util.Scanner;

2.创建Scanner类的对象

Scanner cin=new Scanner(System.in); //从标准输入读入数据

Scanner cin=new Scanner(“12 30”)); //从字符串读入数据

3.使用Scanner类的对象读入各种类型的数据

cin.nextInt()

cin.nextDouble();

…

Scanner类的常用方法

1.读入数据

Scanner类方法	对应C操作	对应C++操作
int n = cin.nextInt();	scanf("%d", &n);	cin >> n;
String s = cin.next();	scanf("%s", s);	cin >> s;
double t = cin.nextDouble();	scanf("%lf", &t);	cin >> t;
String s = cin.nextLine();	gets(s);	cin.getline(...);
BigDecimal b=cin.nextBigDecimal();

2.判断是否还有数据

cin.hasNext() 或 cin.hasNextInt() 或 cin.hasNextDouble()

Scanner类的用方法示例：

import java.util.*;

public class Main{

    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);

        while(sc.hasNext()){

            char ch=(char)sc.nextInt();

            System.out.print(ch);

        }

    }

}

标准输出

System.out.print(…); //不输出换行

System.out.println(…); //输出换行

import java.io.*;

public class Main{

    static PrintStream cout=System.out;

    public static void main(String[] args){

        int n=3,m=5;

        cout.println(n);  // 输出3

         //同一行输出多个整数可以用

        cout.println(n+" "+m);

    }

}

用DecimalFormat类控制浮点数小数位数

import java.text.DecimalFormat;

控制方法

构造特定的DecimalFormat对象：DecimalFormat f=new DecimalFormat(“#.00#”);

构造函数中的参数是模式字符串，0指一位数字，#指除0以外的数字

使用DecimaFormat对象格式化需要输出的浮点数：System.out.println(f.format(12.1234));

DecimalFormat示例

import java.text.*;

public class decimalformat{

    public static void main(String[] args){

        DecimalFormat f = new DecimalFormat("#.00#");

        DecimalFormat g = new DecimalFormat("0.000");

        double a = 123.4509, b = 0.12;

        System.out.println(f.format(a));

        System.out.println(g.format(a));

        System.out.println(f.format(b));

        System.out.println(g.format(b));

    }

}

运行结果：

123.451

.12

0.120

格式化输出的另一种方法是利用System.out.printf(“格式字符串”,…)，其用法和c的printf基本一致

int a=10;

float b=2.35f;

System.out.printf("%d %10.5f\n", a, b);

字符串（String）

String类常用方法：

构造字符串：

String s=“abcde”;

char[] chs={‘a’,’b’,’c’,’d’,’e’};

String s=new String(chs);

取得字符串中某个字符：

char ch=s.charAt(1);    //ch=‘b’;

求子串：

System.out.println(s.substring(0, 3)) // output “abc"

System.out.println(s.substring(1, 3)) // output “bc"

System.out.println(s.substring(1)) // output “bcde"

拆分字符串：

String s=“123:34:55”;

String[] ss = s.split(“:”);

for(int i=0;i<ss.length;i++) System.out.println(ss[i]);

运行结果：

123

替换字符串：

String s=“2009-07-26”;

System.out.println( s.replace(‘-’,’//’) ); //输出2009/07/26

String s=“0.123456”;

System.out.println( s.replaceAll(“^0”,””) ); //输出.123456

String中的字符不能改变，如果需要改变可以使用StringBuffer

其他注意的事项

Java数组是对象，定义后必须初始化，如 int[] a = new int[100]; 数组长度由length成员得到，如System.out.println(a.length);

Arrays类提供的一些有用方法：

Arrays.fill()

Arrays.sort()

Arrays.binarySearch()

布尔类型为 boolean，只有true和false二值，在 if (...) / while (...) 等语句的条件中必须为boolean类型。

在C/C++中的 if (n % 2) ... 在Java中无法编译通过。

Java也提供了类似STL的集合类：

Vector，ArrayList，Map，Queue，Stack，Hashtable

3.Java与高精度计算

PKU1001-exponentiation（求幂）:

Sample Input

95.123 12

0.4321 20

5.1234 15

6.7592 9

98.999 10

1.0100 12

Sample Output

548815620517731830194541.899025343415715973535967221869852721

. 00000005148554641076956121994511276767154838481760200726351203835

429763013462401

43992025569.928573701266488041146654993318703707511666295476720493

953024

29448126.764121021618164430206909037173276672

90429072743629540498.107596019456651774561044010001

1.126825030131969720661201

用C/C++解决的方法

C/C++的pow函数无法达到需要的精度

C/C++用数组来模拟乘法运算提高精度

java代码:

import java.math.*;

import java.util.*;

public class Main{

    public static void main(String[] args){

        Scanner in=new Scanner(System.in);

        while(in.hasNext()){

            BigDecimal val=in.nextBigDecimal();

            int n=in.nextInt();

            BigDecimal ret=val.pow(n).stripTrailingZeros();

            System.out.println( ret.toPlainString().replaceAll("^0", "") );

        }

    }

}

BigDecimal类

高精度的有符号十进制数字

构造一个高精度数字

BigDecimal (int val)

BigDecimal (double val)

BigDecimal (String val)

BigDecimal d1=new BigDecimal(1);

BigDecimal d2=new BigDecimal(0.1);

BigDecimal d3=new BigDecimal("0.1");

System.out.println("d1="+d1);

System.out.println("d2="+d2);

System.out.println("d3="+d3);

BigDecimal类常用方法：

BigDecimal add(BigDecimal augend)        //  “+”

BigDecimal subtract(BigDecimal subtrahend)    //  “-”

BigDecimal multiply(BigDecimal multiplicand)    //  “*”

BigDecimal divide(BigDecimal divisor)        //  “/”

BigDecimal remainder(BigDecimal divisor)    //  “%”

BigDecimal pow(int n)                //“求幂”

String toPlainString()    //返回不带指数的字符串表示

String toString()        //返回带指数的字符串表示

PKU高精度计算题目:

1131、1205、1220、1405、1503、1604 1894、2084、2305、2325、2389、2413 3101、3199