题目要求
分析
这题看起来好像不难,但要认真读题。
他说的什么间隔为1只不过是一句废话,告诉你就是普通的矩阵地图而已。
其实数据不可能是只有1行的,2行为一组,每一组都是独立的,要考察每一组里兔八哥能不能被猎人K.O.
那怎么才算K.O.呢?问题就转化为一张点阵图中两个点是否直接相连(中间不穿过其他点),所有的东西就看做物理上的质点(或者就是平面上一个纯粹的点)吧。
也就是说,Δy与Δx最小公约数是1!
好了,gcd 呗,欧几里得算法!
《辗转相除法(欧几里得算法)详解》
但这里如果我们简单地使用int的欧几里得算法,会爆的,全部RE,所以可以考虑BigInteger的gcd()。
使用Java写的这个题基本必定会T掉,因为太慢了,根据多年与Java博弈的经验,我成功地在五次提交之内AC,下面说说一些注意的点:
- 读一定要用BufferedReader,Scanner可以直接nextBigInteger(),看似更好其实更慢了
- 一定要一次把所有的数据读进来,否则肯定会炸,千万别一边读一遍算
- 结果千万不能一次一次的输出,必须使用StringBuilder整合输出内容
- 不要使用字符串连接符,怕影响效率
- split()的时候一定要使用
\\s+
,不然估计会T掉 - 数组别乱开,按照需要的来开,怕MLE
第二个数据点和第十个数据点巨难过,第二个数据点输入数据4.05MB,输出数据454.55KB,一共100000组,数据点十更过分。
为什么强调一定要注意我说的那些数据细节呢?看下面的AC记录就行了,就差一点就失败了:
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);
}
}