8.27网易笔试题
我共通过两题，最后一题一直超时。
第一题，贴墙纸。
思路：把需要的所有墙纸贴好，然后取出中间的m*m的子矩阵就可以了
代码如下：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while (T-- > 0) {
int n = in.nextInt();
int m = in.nextInt();
char[][] a = new char[n][];
for (int i = 0; i < n; i++) a[i] = in.next().toCharArray();
getCenterMatrix(n, m, a);
}
}
private static void getCenterMatrix(int n, int m, char[][] a) {
int width = 1 + ((m - n - 1) / (2 * n) + 1) * 2;
//System.out.println("width = " + width);
char[][] c = new char[width*n][width*n];
for (int i = 0; i < c.length; i += n) {
for (int j = 0; j < c.length; j += n) {
for (int k = 0; k < n; k++) {
for (int h = 0; h < n; h++) {
c[i+k][j+h] = a[k][h];
}
}
}
}
int st = (width * n - m) / 2;
for (int i = st; i < st+m; i++) {
for (int j = st; j < st+m; j++) {
System.out.print(c[i][j]);
}
System.out.println();
}
System.out.println();
}
} 第二题，求矩阵覆盖的面积。难点在于有多个矩阵覆盖了同一块区域，但是这块区域的面积只能被计算一次。如果暴力去做可能会超时，于是观察题目数据量，矩形的坐标范围在[0,1000]之间，同时矩阵的数量为[1, 500]，所有可以考虑枚举Y轴，然后把包含这个Y轴的所有矩阵在这条Y轴上的面积都计算一遍！为了计算的快速，需要先按照x0坐标排序，问题就转化为了如下问题：
给你一堆线段, [1,3], [5, 7],...,请你算出线段所覆盖的最大长度！这样就能算出每一个Y坐标覆盖的面积，然后把0-1000的面积加起来就是总的面积了。
注意：边缘不能重复计算，比如矩阵[0,0,1,1]的面积为1，而不是4，也就是说y为0时不可以和y为1时同时计算。我在代码中没有考虑矩阵的下边缘。
if (i > y0 && i <= y1) // 不考虑下边缘AC代码如下：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
int x0, y0, x1, y1;
while (T-- > 0) {
int n = in.nextInt();
ArrayList<int[]> recs = new ArrayList<>();
for (int i = 0; i < n; i++) {
x0 = in.nextInt();
y0 = in.nextInt();
x1 = in.nextInt();
y1 = in.nextInt();
recs.add(new int[]{x0, y0, x1, y1});
}
// 按照x0排序
recs.sort(Comparator.comparingInt(o -> o[0]));
// 找出有效矩阵
boolean[] ok = new boolean[n];
for (int i = 0; i < n; i++) {
if (!ok[i]) {
for (int j = i + 1; j < n; j++) {
if (crossed(recs.get(i), recs.get(j))) {
ok[i] = ok[j] = true;
}
}
}
}
//System.out.println(Arrays.toString(ok));
int area = 0;
for (int i = 0; i <= 1000; i++) {
int len = 0, st = -1, end = -1;
for (int j = 0; j < n; j++) {
if (!ok[j]) continue;
int[] t = recs.get(j);
x0 = t[0];
y0 = t[1];
x1 = t[2];
y1 = t[3];
//if (y1 == i) continue;
if (i > y0 && i <= y1) { // 不考虑下边缘
if (x0 > end) {
len += x1 - x0;
end = x1;
} else if (x1 > end) {
len += x1 - end;
end = x1;
}
}
}
area += len;
}
System.out.println(area);
}
}
private static boolean crossed(int[] r1, int[] r2) {
// x0 >= x1
if (r1[0] >= r2[2] || r2[0] >= r1[2]) return false;
// y0 >= y1
if (r1[1] >= r2[3] || r2[1] >= r1[3]) return false;
return true;
}
} 思路：枚举所有可能的边，但是超时。。。有AC大佬给个思路吗？
