5.16 网易互娱笔试，第三题用常数时间判断全0全1。

第一题题目的范围内是可以直接暴力的，但是也很迷，，太粗心了整了一个小时

package netease;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int st[][] = new int[n][10010];
        for (int i = 0; i < n; i++) {
            int m = in.nextInt();
            int[][] vt = new int[m+1][2];
            for (int j = 0; j < m; j++) {
                vt[j][0] = in.nextInt();
                vt[j][1] = in.nextInt();
            }
            vt[m][0] = 10001;
            int ind = 1;
            for (int k = 1; k < vt.length; k++) {
                int l = vt[k][0] - vt[k-1][0];
                for (int l2 = 0; l2 < l; l2++) {
                    st[i][ind] = st[i][ind-1]+vt[k-1][1];
                    ind++;
                }
            }
        }
        int test = in.nextInt();
        for (int i = 0; i < test; i++) {
            int time = in.nextInt();
            int max = 0;
            int maxlen= st[0][time];
//            System.out.print(maxlen+" ");
            for (int j = 1; j < n; j++) {
//                System.out.print(st[j][time] +" ");
                if(st[j][time]>maxlen) {
                    max = j;
                    maxlen = st[j][time];
                }
            }
//            System.out.println();
            System.out.println(max+1);
        }
    }
}

第二题也是暴力，，，先处理两边靠墙，再处理一边靠墙，就清晰很多了

package netease;

import java.util.Scanner;

public class t2 {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int z = 0; z < n; z++) {
            int X = in.nextInt();
            int Y = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            int d = in.nextInt();
            int t = in.nextInt();
            int [][]dir = {{-1,-1},{-1,1},{1,1},{1,-1}};
            int cnt = 0;
            x-=1;
            y-=1;
            for (int i = 0; i < t; i++) {

                x+=dir[d][0];
                y+=dir[d][1];

                if((x==1&&y==1)||( x==1&&y==Y-2)||(x==X-2&&y==1)||(x==X-2&&y==Y-2)) {
                    if(d==1) {
                        d=3;
                    }else if(d==2) {
                        d = 0;
                    }else if(d==0) {
                        d = 2;
                    }else if(d==3) {
                        d = 1;
                    }
                    cnt+=2;
                }else if(x==1) {
                    if(d== 0) {
                        d=3;
                    }else if(d==1) {
                        d=2;
                    }else {
                        System.out.println("wrong");
                    }
                    cnt ++;
                }else if(x==X-2) {
                    if(d== 2) {
                        d=1;
                    }else if(d==3) {
                        d=0;
                    }else {
                        System.out.println("wrong");
                    }
                    cnt ++;
                }
                else if(y==1) {
                    if(d== 3) {
                        d=2;
                    }else if(d==0) {
                        d=1;
                    }else {
                        System.out.println("wrong");
                    }
                    cnt ++;
                }
                else if(y==Y-2) {
                    if(d== 2) {
                        d=3;
                    }else if(d==1) {
                        d=0;
                    }else {
                        System.out.println("wrong");
                    }
                    cnt ++;
                }else {
                    //走就完事了。。
                }        
            }
            System.out.println(cnt);
        }    
    }
}

第三题，没时间了，暴力算法也没改出来，后面用常数时间判断给定起点和长度的正方形是否全0全1

，我用的是记录一个sum[i][j]，表示从[i,j]到左上所有的1的个数，然后正方形[x,y]到[x+l,y+l]的1的个数等于sum[x+l-1][y+l-1] - sum[x-1][y+l-1] - sum[x+l-1][y-1] + sum[x-1][y-1]，通过判断1的个数为0 或 l*l 得到是否为全1全0。

package netease;

import java.util.Scanner;

public class t3 {
    static int map[][];
    static int sum[][];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int ii = 0; ii < n; ii++) {
            int X = in.nextInt();
            int Y = in.nextInt();
            in.nextLine();
            map = new int[X][Y];
            sum = new int[X][Y];
            for (int i = 0; i < X; i++) {
                String x = in.nextLine(); 
                for (int j = 0; j < Y; j++) {
                    map[i][j] = x.charAt(j)=='1'?1:0;
                }
            }
            sum[0][0] = map[0][0];
            for (int i = 1; i < Y; i++) {
                sum[0][i] =  sum[0][i-1] + map[0][i];
            }
            for (int i = 1; i < X; i++) {
                int sumx = 0;
                for (int j = 0; j < Y; j++) {
                    sumx += map[i][j];
                    sum[i][j]=sumx + sum[i-1][j];
                }
            }    
            int max = Integer.min(X, Y)/3;
            int now = max;
            Boolean ok = false;
            out:
            for(int mow = max; now>=1; now--) {//3个1000 应该不会超时
                for (int i = 0; i <= X - now*3; i++) {
                    for (int j = 0; j <= Y - now*3; j++) {
                        if(check(i, j, now)) {//常数时间
                            i+=1;
                            j+=1;
                            System.out.println(i+" "+j+" "+(i+now*3-1)+" "+(j+now*3-1));
                            ok = true;
                            break out;
                        }

                    }
                }
            }
            if(!ok)
                System.out.println("-1 -1 -1 -1");
        }

    }
    private static boolean check(int x, int y, int now) {
        // TODO Auto-generated method stub
        if(check0(x, y, now)&&check0(x, y+2*now, now)&&
                check0(x+2*now, y, now)&&check0(x+2*now, y+2*now, now)) {
            if(check1(x, y+now, now)&&check1(x+now, y, now)&&check1(x+now, y+now, now)
                    &&check1(x+now, y+2*now, now)&&check1(x+2*now, y+now, now)) {
                return true;
            }

        }
        return false;
    }
    private static boolean check0(int x, int y, int now) {
        return getArea(x, y, now) == 0;
    }

    private static int getArea(int x, int y, int now) {
        int area = sum[x+now-1][y+now-1];
        if(x-1>=0 && y-1>=0) {
            area += sum[x-1][y-1];
        }
        if(x-1>=0) {
            area -= sum[x-1][y+now-1];
        }
        if(y-1>=0) {
            area -= sum[x+now-1][y-1];
        }
        return area;
    }

    private static boolean check1(int x, int y, int now) {
        return getArea(x, y, now) == now * now;
    }

}

/*
3
3 3
111
000
111
6 6
010010
111111
010010
010010
111111
010010
8 8
01000001
11100001
01001100
11001100
00111111
00111111
00001100
00001100

*/

#网易互娱笔试##笔试题目#