题 A

最大化网格图中正方形空洞的面积

给你一个网格图，由 n + 2 条 横线段 和 m + 2 条 竖线段 组成，一开始所有区域均为 1 x 1 的单元格。
所有线段的编号从 1 开始。给你两个整数 n 和 m 。

同时给你两个整数数组 hBars 和 vBars 。

hBars 包含区间 [2, n + 1] 内 互不相同 的横线段编号。
vBars 包含 [2, m + 1] 内 互不相同的 竖线段编号。
如果满足以下条件之一，你可以 移除 两个数组中的部分线段：

如果移除的是横线段，它必须是 hBars 中的值。
如果移除的是竖线段，它必须是 vBars 中的值。

输入描述:

两个正整数 1 ≤ n ≤ 10^9 ,1 ≤ m ≤ 10^9 。
接下来两个数组
1 <= hBars.length <= 100
2 <= hBars[i] <= n + 1
1 <= vBars.length <= 100
2 <= vBars[i] <= m + 1

输出描述:

请你输出移除一些线段后（可能不移除任何线段），剩余网格图中 最大正方形 空洞的面积，正方形空洞的意思是正方形 内部 不含有任何线段。

  • 案例
    1
    2
    输入：n = 2, m = 1, hBars = [2,3], vBars = [2]
    输出：4

思路：统计横竖的最宽间隔, 然后取小后平方;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;

public class Main {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        int row = 0;
        int temp = 1;
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        for (int i = 0; i < hBars.length - 1; i++) {
            if(hBars[i + 1] - hBars[i] == 1) temp++;
            else {
                row = Math.max(row,temp);
                temp = 1;
            }
        }
        row = Math.max(row,temp);
        temp = 1;
        int col = 0;
        for (int i = 0; i < vBars.length - 1; i++) {
            if(vBars[i + 1] - vBars[i] == 1) temp++;
            else  {
                col = Math.max(col,temp);
                temp = 1;
            }
        }
        col = Math.max(col,temp);
        return (int)Math.pow(Math.min(col,row) + 1,2);
    }
}

题 B

所有路径

给定一个 n * m 矩阵 ，角色只能往下或者往右
从左上角走到右下角的所有路径

输入描述:

两个正整数 n 和 m 分别表示 矩阵的行和列
2 <= n <= 1000
2 <= n <= 1000

输出描述:

返回到达右下角的所有路径

  • 案例
    1
    2
    3
    4
    输入
      2 8
    输出
      45

思路：本题在新生赛中数据量非常小，所有下面三种方法都可以解答
1.DFS 2.组合数 3. dp
就给出2的解法，
当数据量在 10^9时 只有2的解法可以


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = in.nextInt();
            }
        }
        System.out.println(solve2(matrix));
    }
    // 组合数求解
    public static long solve2(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        //System.out.println("n:" + n + "  ==m:" + m);
        return factorial(n + m, m);
    }

    // 求阶乘
    public static long factorial(int n, int m) {
        long result = 1;
        // (40!)/(20!)
        for (int i = m + 1; i <= n; i++) {
            result *= i;
            result /= (i - m);
        }
        return result;
    }
}

题 C

小红的01连续段

小红定义一个01串的“连续段”为：连续相同字符的极大长度。例如：”110001111”有一个长度为2的连续段，有一个长度为3的连续段，有一个长度为4的连续段。
小红拿到了一个01串，但其中有一些字符不可见了（用’?’表示）。小红想知道，这个01串的连续段长度的最大值最多能达到多少？

输入描述:

一个仅由’0’、’1’、’?’组成的字符串，长度不超过200000。

输出描述:

一个正整数，代表连续段长度的最大长度。

  • 案例
    1
    2
    3
    4
    5
    6
    输入
      1?0?1?
    输出
      3
    说明
      该字符串可以是"100011"，最大的连续段长度为3。

思路：可以想到，当最长连续段是 0 时 把所有的？变成0为最优解 ，1同理


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
 
        char[] c = s.replaceAll("\\?","0").toCharArray();
        // 将 ？ 看成 0
        int t = process(c);
        // 将 ？ 看成 1
        c = s.replaceAll("\\?","1").toCharArray();
        System.out.println(Math.max(t,process(c)));
    }
     
    public static int process(char[] c){
        int res = Integer.MIN_VALUE;
        int l = 0, r = 1;
        //1?0?1?
        while (r < c.length) {
            if (c[l] != c[r]) {
                res = Math.max(res, r - l);
                l = r;
            }
            r++;
        }
        res = Math.max(res, r - l);
        return res;
    }
}

题 D

小红的01串构造

小红希望你构造一个长度为n的01串，其中恰好有
k个1，且恰好有t对相邻字符都是1。你能帮帮她吗?

输入描述:

三个正整数n,k,t，用空格隔开。
1 ≤ n ≤ 10^5
0 ≤ k,t ≤ n

输出描述:

如果无法完成构造，请输出-1。否则输出任意一个满足条件01串即可。

  • 案例
    1
    2
    3
    4
    5
    6
    7
    输入
      3 2 1
    输出
      110
    说明
      "110"为长度为3的01串，恰好有2个1，恰好有1对相邻数字是1。满足要求。
      输出"011"也是可以通过本样例的。

思路：依照思路构造即可


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int t = in.nextInt();
        
        // 在有 k 个 1的情况下构造t对1相邻至少需要 t+1 个1 
        if(k < t + 1 || n < t + 1){
            System.out.println(-1);
            return;
        }
        
        // 后续只能拼接 01 不破换构造 剩下 (k - t - 1) 个 1 还有 (n -t - 1) 个坑位
        int y = k - t - 1;
        int s =  n - t - 1;
        
        if(s < 2*y){
            System.out.println(-1);
            return;
        }
        
        // 构造字符串
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i <= t; i++) {
            ans.append("1");
        }
        for (int i = 0; i < y; i++) {
            ans.append("01");
        }
        for (int i = 0; i < n - t - 1 - 2 * y; i++) {
            ans.append("0");
        }
        System.out.println(ans.toString());
    }
}