kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

TopCoder Marathon 怎么做

和srm一样写个类和函数即可。

以这题为例: http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15683&pm=12593

要求:

1
2
3
4
5
6
7
8
Definition
      
Class:    CirclesSeparation
Method:   minimumWork
Parameters:   double[], double[], double[], double[]
Returns:  double[]
Method signature: double[] minimumWork(double[] x, double[] y, double[] r, double[] m)
(be sure your method is public)
可以写个很简单的:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
import java.io.*;
import java.math.*;
public class CirclesSeparation {
  int N, now;
  double ox[] = new double[1000], oy[] = new double[1000];
  double x[] = new double[1000], y[] = new double[1000];
  double r[] = new double[1000], m[] = new double[1000];
  boolean touch(int i,int j)
  {
      double dis = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
      if (dis > (r[i]+r[j]) * (r[i]+r[j])) {
          return false;
      }
      return true;
  }
  void dfsMove(int ok, int j)
  {
      double px = x[j] - x[ok];
      double py = y[j] - y[ok];
      double dis = Math.sqrt((x[j]-x[ok])*(x[j]-x[ok]) + (y[j]-y[ok])*(y[j]-y[ok]));
      double dd = r[ok] + r[j] - dis + 0.001;
      x[j] += dd * px / dis;
      y[j] += dd * py / dis;
      //System.out.println(x[j] + "\t" + y[j]);
      int i;
      for (i=0;i<=now;i++) {
          if (i != j && touch(i, j)) {
              dfsMove(j, i);
          }
      }
  }
  public double[] minimumWork(double[] ix, double[] iy, double[] ir, double[] im) {
      int i,j,k,l;
      N = ix.length;
      for (i=0;i<N;i++) {
          ox[i] = ix[i];
          oy[i] = iy[i];
          x[i] = ix[i];
          y[i] = iy[i];
          r[i] = ir[i];
          m[i] = im[i];
      }
      for (i=1;i<N;i++)
      {
          now = i;
          for (j=0;j<i;j++) {
              if (!touch(i, j)) continue;
              dfsMove(i, j);
          }
      }
      double ret[] = new double[N+N];
      for (i=0;i<N;i++) {
          ret[i+i] = x[i];
          ret[i+i+1] = y[i];
      }
      return ret;
  }
}

按照格式写,然后返回结果就可以。这是最基本的。

其实我们可以用他提供的工具先做调试

一般每题会有available.这样一个链接,
进去后

1、先下载页面顶上 CirclesSeparationVis.jar 和 一些其他的东西(如果有)
2、在这行In other words, you should implement the following pseudocode in the main method of your solution:的后面会给出一些输入输出步骤,把他们翻译成对应语言的输入输出,并且把他们写在主函数中,像这题的:
1
2
3
4
5
6
7
8
9
10
11
12
13
N = parseInt(readLine())
for (i=0; i < N; i++)
	x[i] = parseDouble(readLine())
for (i=0; i < N; i++)
	y[i] = parseDouble(readLine())
for (i=0; i < N; i++)
	r[i] = parseDouble(readLine())
for (i=0; i < N; i++)
	m[i] = parseDouble(readLine())
ret = minimumWork(x, y, r, m)
for (i=0; i < 2*N; i++)
	printLine(ret[i])
flush(stdout)

翻译成java的是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {
	Scanner cin = new Scanner(System.in);
	double x[], y[], r[], m[], ret[];
	int N, i;
	N = cin.nextInt();
	x = new double[N];
	y = new double[N];
	r = new double[N];
	m = new double[N];
	for (i=0;i<N;i++) x[i] = cin.nextDouble();
	for (i=0;i<N;i++) y[i] = cin.nextDouble();
	for (i=0;i<N;i++) r[i] = cin.nextDouble();
	for (i=0;i<N;i++) m[i] = cin.nextDouble();
	CirclesSeparation rrr = new CirclesSeparation();
	ret = rrr.minimumWork(x, y, r, m);
	for (i=0;i<N+N;i++) {
		System.out.println(ret[i]);
	}
}

把这个函数加到最基本的当中,这样一个就形成一个完整的可执行程序,编译它生成对应目标代码。

1
$ javac CirclesSeparation.java
3、再往下可以找到一句类似于:
1
java -jar CirclesSeparationVis.jar -exec "<command>"

的语句。

1
java 的<command>是 java CirclesSeparation

所以运行:

1
java -jar CirclesSeparationVis.jar -exec "java CirclesSeparation" 

就可以看到结果了。

可以用 -seed=X 来选择第几组样例,可以用 -novis 来关闭图形显示

4、当用这个工具的时候System.out.println()的输出会被工具截获,要输出调试信息可以用System.err.println()
5、有时候需要改CirclesSeparationVis.jar代码,以满足我们的调试需求。可以下载CirclesSeparationVis.java,然后javac编译之,在使用的时候改用:
1
java CirclesSeparationVis -exec "java CirclesSeparation"
6、用long t=System.currentTimeMillis()统计时间,是千分之一秒