网易互娱 08.27 笔试 100+90+100

网易互娱第三题刚好熟悉相关方法，侥幸过了。

第1题 模拟题 （AC）

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int p = 0; p < n; p++) {
            int len = in.nextInt();
            int size = in.nextInt();
            char[][] pic = new char[len][len];
            for(int i = 0; i < len; i++){
                String str = in.next();
                pic[i] = str.toCharArray();
            }
            int left = (size - len)/2;
            int leftCnt = left / len;
            int leftOffset = left % len;
            int cnt = leftCnt*2+1;
            for(int i = 0; i < leftOffset; i++){ // offset 行
                printLine(pic, leftOffset, len-leftOffset+i, cnt);
            }
            for(int i = 0; i < cnt * len; i++) {
                printLine(pic, leftOffset, i%len, cnt);
            }
            for(int i = 0; i < leftOffset; i++) {
                printLine(pic, leftOffset, i, cnt);
            }
        }
    }

    public static void printLine(char pic[][], int offset, int idx, int cnt){
        for(int i = 0; i < offset; i++){
            System.out.print(pic[idx][pic.length-offset+i]);
        }
        for(int i = 0; i < cnt; i++){ // cnt 个重复的
            for(int j = 0; j < pic.length; j++){
                System.out.print(pic[idx][j]);
            }
        }
        for(int i = 0; i < offset; i++){
            System.out.print(pic[idx][i]);
        }
        System.out.println();
    }

第2题 有效长方形面积 (90% 超时)

N个长方形，可能互相覆盖。若两个长方形存在覆盖面积(area>0)，则两个长方形为有效长方形。计算有效长方形的覆盖面积。(0 <= x,y <= 1000)

求满分过程(划掉，原来最多只有一个重叠，在计算是否重叠时就直接处理好了，哭了)

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int p = 0; p < t; p++) {
            int n = in.nextInt();
            boolean ok[] = new boolean[n];
            int arr[][] = new int[n][4];
            for(int i = 0; i < n; i++){
                arr[i][0] = in.nextInt();
                arr[i][2] = in.nextInt();
                arr[i][1] = in.nextInt();
                arr[i][3] = in.nextInt();
                for(int j = 0; j < i; j++) {
                    if(check(arr[i], arr[j]) || check(arr[j], arr[i])) {
                        ok[j] = true;
                        ok[i] = true;
                    }
                }
            }
            boolean vis[][] = new boolean[1000][1000];
            for(int i = 0; i < n; i++){
                if(!ok[i]) continue;
                for(int x = arr[i][0]; x < arr[i][1]; x++) {
                    for(int y = arr[i][2]; y < arr[i][3]; y++) {
                        vis[x][y] = true;
                    }
                }
            }
            int cnt = 0;
            for(int i = 0; i < 1000; i++) {
                for(int j = 0; j < 1000; j++) {
                    if(vis[i][j]) cnt++;
                }
            }
            System.out.println(cnt);
        }

    }

    public static boolean check(int a[], int b[]) {
        boolean bxl = a[0] <= b[0] && b[0] < a[1], bxr = a[0] < b[1] && b[1] <= a[1], bxin = b[0] <= a[0] && b[1] >= a[1], bxout = b[0] >= a[0] && b[1] <= a[1];
        boolean byl = a[2] <= b[2] && b[2] < a[3], byr = a[2] < b[2] && b[3] <= a[3], byin = b[2] <= a[2] && b[3] >= a[3], byout = b[2] >= a[2] && b[3] <= a[3];
        return (bxin || bxout || bxr || bxl) && (byin || byout || byl || byr);
    }

第3题 手机屏锁 （AC）

手机屏锁，9个点，问使用可用的点，能够展示的不同的图形有多少种。
'.' 代表可用，'X' 代表不可用。

输入：

3 // 3组数据
...  // 1组第一行
XXX  // 1组第二行
XXX  // 1组第三行
...  // 2组第一行
XXX  // 2组第二行
X.X  // 2组第三行
.X.  // 3组第一行
X.X  // 3组第二行
.X.  // 3组第三行

输出：

3
22
111

第1组，0-1，0-2 或者 0-1-2，1-2 共3种图形。

思路：9个点一共只有28条边，用int二进制就可以表示边的出现情况，即代码中的pic。edges就是边的情况。

获得为'.'的节点，进而获得全排列，根据全排列的情况计算图的样子。

public class Main{
    static int edges[][] = {
            {0,         1<<1,       (1<<2)+(1<<1),      1<<3,           1<<13,          1<<21,          (1<<3)+(1<<8),      1<<25,          (1<<13)+(1<<19)},
            {1<<1,      0,          1<<2,           1<<14,          1<<4,           1<<15,          1<<26,          (1<<4)+(1<<9),      1<<27},
            {(1<<2)+(1<<1), 1<<2,       0,              1<<22,          1<<16,          1<<5,           (1<<16)+(1<<18),    1<<28,          (1<<5)+(1<<10)},
            {1<<3,      1<<14,      1<<22,          0,              1<<6,           (1<<6)+(1<<7),      1<<8,           1<<17,          1<<23},
            {1<<13,     1<<4,       1<<16,          1<<6,           0,              1<<7,           1<<18,          1<<9,           1<<19},
            {1<<21,     1<<15,      1<<5,           (1<<6)+(1<<7),      1<<7,           0,              1<<24,          1<<20,          1<<10},
            {(1<<3)+(1<<8), 1<<26,      (1<<16)+(1<<18),    1<<8,           1<<18,          1<<24,          0,              1<<11,          (1<<12)+(1<<11)},
            {1<<25,     (1<<4)+(1<<9),  1<<28,          1<<17,          1<<9,           1<<20,          1<<11,          0,              1<<12},
            {(1<<13)+(1<<19), 1<<27,     (1<<5)+(1<<10),     1<<23,         1<<19,          1<<10,          (1<<12)+(1<<11),    1<<12,          0}};

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int p = 0; p < n; p++){
            // 生成数组
            int cnt = 0;
            int len = 0;
            ArrayList<Integer> l = new ArrayList<>(9);
            for(int i = 0; i < 3; i++) {
                String s = in.next();
                for(int j = 0; j < 3; j++){
                    if(s.charAt(j) == '.') {
                        l.add(len);
                        cnt++;
                    }
                    len++;
                }
            }
            // 全排列+统计图片
            ArrayList<ArrayList<Integer>> full = new ArrayList<>();
            Set<Integer> pic = new HashSet<>();
            fullDFS(pic, l, 0, full, cnt);
            System.out.println(pic.size());
        }
    }

    public static void fullDFS(Set<Integer> pic, ArrayList<Integer> l, int idx, ArrayList<ArrayList<Integer>> full, int len) {
        if(idx == len) {
            func(pic, l, 1, len, 0);
            return;
        }
        for(int i = idx; i < len; i++) {
            int tmp = l.get(i);
            l.set(i, l.get(idx));
            l.set(idx, tmp);
            fullDFS(pic, l, idx+1, full, len);
            l.set(idx, l.get(i));
            l.set(i, tmp);
        }
    }

    public static void func(Set<Integer> pic, ArrayList<Integer> l, int idx, int len, int value) {
        if(idx >= len) return;
        int edge = edges[l.get(idx-1)][l.get(idx)];
        value = value | edge;
        pic.add(value);
        func(pic, l, idx+1, len, value);
    }
}