兔八哥与猎人(洛谷P1170题题解,Java语言描述)

题目要求

题目链接

兔八哥与猎人(洛谷P1170题题解,Java语言描述)

分析

这题看起来好像不难,但要认真读题。
他说的什么间隔为1只不过是一句废话,告诉你就是普通的矩阵地图而已。

其实数据不可能是只有1行的,2行为一组,每一组都是独立的,要考察每一组里兔八哥能不能被猎人K.O.

那怎么才算K.O.呢?问题就转化为一张点阵图中两个点是否直接相连(中间不穿过其他点),所有的东西就看做物理上的质点(或者就是平面上一个纯粹的点)吧。

也就是说,Δy\Delta yΔy与Δx\Delta xΔx最小公约数是111!

好了,gcdgcdgcd 呗,欧几里得算法!
《辗转相除法(欧几里得算法)详解》

但这里如果我们简单地使用int的欧几里得算法,会爆的,全部RE,所以可以考虑BigInteger的gcd()。

使用Java写的这个题基本必定会T掉,因为太慢了,根据多年与Java博弈的经验,我成功地在五次提交之内AC,下面说说一些注意的点:

  • 读一定要用BufferedReader,Scanner可以直接nextBigInteger(),看似更好其实更慢了
  • 一定要一次把所有的数据读进来,否则肯定会炸,千万别一边读一遍算
  • 结果千万不能一次一次的输出,必须使用StringBuilder整合输出内容
  • 不要使用字符串连接符,怕影响效率
  • split()的时候一定要使用 ,千万不能使用\\s+,不然估计会T掉
  • 数组别乱开,按照需要的来开,怕MLE

第二个数据点和第十个数据点巨难过,第二个数据点输入数据4.05MB,输出数据454.55KB,一共100000组,数据点十更过分。

为什么强调一定要注意我说的那些数据细节呢?看下面的AC记录就行了,就差一点就失败了:

兔八哥与猎人(洛谷P1170题题解,Java语言描述)

AC代码(Java语言描述)

import java.io.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder result = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());
        String[] x1_arr = new String[num], y1_arr = new String[num], x2_arr = new String[num], y2_arr = new String[num];
        for (int i = 0; i < num; i++) {
            String[] temp1 = reader.readLine().split(" "), temp2 = reader.readLine().split(" ");
            x1_arr[i] = temp1[0];
            x2_arr[i] = temp2[0];
            y1_arr[i] = temp1[1];
            y2_arr[i] = temp2[1];
        }
        reader.close();
        for (int i = 0; i < num; i++) {
            BigInteger x1 = new BigInteger(x1_arr[i]), y1 = new BigInteger(y1_arr[i]), x2 = new BigInteger(x2_arr[i]),
                    y2 = new BigInteger(y2_arr[i]);
            if ((x2.subtract(x1)).gcd((y2.subtract(y1))).equals(BigInteger.ONE)) {
                result.append("no\n");
            } else {
                result.append("yes\n");
            }
        }
        System.out.print(result);
    }
}
上一篇:源码研究:php变量


下一篇:一、求最大公约数