第十届蓝桥杯决赛JavaC组真题——详细答案对照(完整版)-2-阿里云开发者社区

F、最长子序列

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

问题描述

我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。

给定两个字符串 S 和 T，请问 T 中从第一个字符开始最长连续多少个字符被 S 包含？

输入格式

输入两行，每行一个字符串。第一行的字符串为 S，第二行的字符串为 T。

两个字符串均非空而且只包含大写英文字母。

输出格式

输出一个整数，表示答案。

测试样例1

Input：

ABCDEABCD

AABZ

Output：

评测用例规模与约定

对于 20% 的评测用例，1 ≤ |T| ≤ |S | ≤ 20；

对于 40% 的评测用例，1 ≤ |T| ≤ |S | ≤ 100；

对于所有评测用例，1 ≤ |T| ≤ |S | ≤ 1000。

package action;
import java.util.Scanner;
public class demo {
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  String s1 = sc.next();
  String s2 = sc.next();
  sc.close();
  int n1 = 0;
  int n2 = 0;
  int sum = 0;
  for (; n1 < s1.length(); n1++) {
    if (s1.charAt(n1) == s2.charAt(n2)) {
    sum++;
    n2++;
    }
  }
  System.out.println(sum);
  }
}

G、数正方形

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

问题描述

在一个 N × N 的点阵上，取其中 4 个点恰好组成一个正方形的 4 个顶点，一共有多少种不同的取法？

由于结果可能非常大，你只需要输出模 109 + 7 的余数。

（如：图7）所示的正方形都是合法的。

输入格式

输入包含一个整数 N。

输出格式

输出一个整数代表答案。

测试样例1

Input：

Output：

评测用例规模与约定

对于所有评测用例，2 ≤ N ≤ 1000000。

package action;
import java.math.BigInteger;
import java.util.Scanner;
public class demo {
  final static BigInteger mod = BigInteger.valueOf(1000_000_007);
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  sc.close();
  BigInteger ans = BigInteger.ZERO;
  for (int i = 1; i <= n; i++) {
    BigInteger x = BigInteger.valueOf(n - i);
    ans = ans.add(BigInteger.valueOf(i).multiply(x.pow(2))).mod(mod);
  }
  System.out.println(ans.longValue());
  }
}

H、矩阵计数

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

问题描述

一个 N × M 的方格矩阵，每一个方格中包含一个字符 O 或者字符 X。

要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。

问这样的矩阵一共有多少种？

输入格式

输入一行包含两个整数 N 和 M。

输出格式

输出一个整数代表答案。

测试样例1

Input：

2 3

Output：

评测用例规模与约定

对于所有评测用例，1 ≤ N, M ≤ 5。

package action;
import java.util.Scanner;
public class demo {
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n1 = sc.nextInt();
  int n2 = sc.nextInt();
  sc.close();
  int a[][] = new int[n1][n2];
  int sum = 0;
  for (int t = 0; t < Math.pow(2, n1 * n2); t++) {
    int x = 0;
    // 将数组赋值
    for (int i = 0; i < n1; i++) {
    for (int j = 0; j < n2; j++) {
      if ((t >> x & 1) == 1) {
      a[i][j] = 1;
      }
      x++;
    }
    }
    if (check(a)) {// 检查数组
    } else {
    sum++;
    }
    // 数组清空
    for (int i = 0; i < n1; i++) {
    for (int j = 0; j < n2; j++) {
      a[i][j] = 0;
    }
    }
  }
  System.out.println(sum);
  }
  private static boolean check(int[][] a) {
  int x = 0;
  for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < a[0].length; j++) {
    if (a.length - i > 2 & a[i][j] == 1) {
      if (a[i + 1][j] == 1 & a[i + 2][j] == 1) {
      x = 1;
      return true;
      }
    }
    if (a[0].length - j > 2 & a[i][j] == 1) {
      if (a[i][j + 1] == 1 & a[i][j + 2] == 1) {
      x = 1;
      return true;
      }
    }
    }
  }
  if (x == 1) {
    return true;
  }
  return false;
  }
}

I、大胖子走迷宫

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

问题描述

小明是个大胖子，或者说是个大大胖子，如果说正常人占用 1 × 1 的面积，小明要占用 5 × 5 的面积。由于小明太胖了，所以他行动起来很不方便。当玩一些游戏时，小明相比小伙伴就吃亏很多。

小明的朋友们制定了一个计划，帮助小明减肥。计划的主要内容是带小明玩一些游戏，让小明在游戏中运动消耗脂肪。走迷宫是计划中的重要环节。

朋友们设计了一个迷宫，迷宫可以看成是一个由 n × n 个方阵组成的方阵，正常人每次占用方阵中 1 × 1 的区域，而小明要占用 5 × 5 的区域。小明的位置定义为小明最正中的一个方格。迷宫四周都有障碍物。

为了方便小明，朋友们把迷宫的起点设置在了第 3 行第 3 列，终点设置在了第 n-2 行第 n-2 列。

小明在时刻 0 出发，每单位时间可以向当前位置的上、下、左、右移动单位 1 的距离，也可以停留在原地不动。小明走迷宫走得很辛苦，如果他在迷宫里面待的时间很长，则由于消耗了很多脂肪，他会在时刻 k 变成一个胖子，只占用 3 × 3 的区域。如果待的时间更长，他会在时刻 2k 变成一个正常人，只占用 1 × 1 的区域。注意，当小明变瘦时迷宫的起点和终点不变。

请问，小明最少多长时间能走到迷宫的终点。注意，小明走到终点时可能变瘦了也可能没有变瘦。

输入格式

输入的第一行包含两个整数 n, k。

接下来 n 行，每行一个由 n 个字符组成的字符串，字符为 + 表示为空地，

字符为 * 表示为阻碍物。

输出格式

输出一个整数，表示答案。

测试样例1

Input：

9 5

+++++++++

***+*****

+++++++++

Output：

评测用例规模与约定

对于 30% 的评测用例，1 ≤ n ≤ 50。

对于 60% 的评测用例，1 ≤ n ≤ 100。

对于所有评测用例，1 ≤ n ≤ 300，1 ≤ k ≤ 1000。

package action;
import java.io.IOException;
import java.io.InputStream;
import java.util.LinkedList;
import java.util.Queue;
public class demo {
  public static void main(String[] args) {
  InputReader in = new InputReader(System.in);
  int n = in.nextInt(), k = in.nextInt();
  if (n <= 5)
    System.out.print('0');
  else {
    int map[][] = new int[n][n], INF = 0x3F3F3F3F;
    boolean[][] visit = new boolean[n][n];
    for (int i = 0, hi = n - 1; i <= hi; i++) {
    if (i < hi)
      map[1][i] = map[hi - 1][i] = map[i][1] = map[i][hi - 1] = 1;
    map[0][i] = map[hi][i] = map[i][0] = map[i][hi] = 2;
    }
    int[] os2i = { -1, -1, 0, 1, 1, 1, 0, -1 };
    int[] os2j = { 0, 1, 1, 1, 0, -1, -1, -1 };
    int[] os1i = { -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2 };
    int[] os1j = { 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1 };
    for (int i = 0, x, y; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (in.split() == '*') {
      map[i][j] = INF;
      for (int l = 0; l < 8; l++) {
        x = i + os2i[l];
        y = j + os2j[l];
        if (x < 0 || x >= n || y < 0 || y >= n || map[x][y] > 2)
        continue;
        map[x][y] = 2;
      }
      for (int l = 0; l < 16; l++) {
        x = i + os1i[l];
        y = j + os1j[l];
        if (x < 0 || x >= n || y < 0 || y >= n || map[x][y] > 1)
        continue;
        map[x][y] = 1;
      }
      }
    }
    class Step {
    int x, y, time;
    Step(int x, int y, int time) {
      this.x = x;
      this.y = y;
      this.time = time;
    }
    Step relax() {
      this.time++;
      return this;
    }
    }
    Queue<Step> queue = new LinkedList();
    int[] offsetX = { -1, 0, 1, 0 };
    int[] offsetY = { 0, 1, 0, -1 };
    int endX = n - 3, endY = n - 3;
    queue.offer(new Step(2, 2, 0));
    while (queue.size() > 0) {
    Step now = queue.poll();
    if (now.x == endX && now.y == endY) {
      System.out.print(now.time);
      break;
    }
    for (int i = 0, x, y, s; i < 4; i++) {
      x = now.x + offsetX[i];
      y = now.y + offsetY[i];
      s = now.time / k;
      if (x < 0 || x >= n || y < 0 || y >= n || visit[x][y] || map[x][y] > s)
      continue;
      visit[x][y] = true;
      queue.offer(new Step(x, y, now.time + 1));
    }
    queue.offer(now.relax());
    }
  }
  }
  static class InputReader {
  InputStream in;
  int next, len;
  byte[] buff;
  InputReader(InputStream in) {
    this(in, 8192);
  }
  InputReader(InputStream in, int buffSize) {
    this.buff = new byte[buffSize];
    this.next = this.len = 0;
    this.in = in;
  }
  int getByte() {
    if (next >= len)
    try {
      next = 0;
      len = in.read(buff);
      if (len == -1)
      return -1;
    } catch (IOException e) {
      e.fillInStackTrace();
    }
    return buff[next++];
  }
  int split() {
    int c = getByte();
    while (c <= 32 || c == 127)
    c = getByte();
    return c;
  }
  int nextInt() {
    int n = 0, c = split();
    boolean flag = true;
    if (c == '-') {
    c = getByte();
    flag = false;
    }
    while (c >= '0' && c <= '9') {
    n = n * 10 + (c & 0xf);
    c = getByte();
    }
    return flag ? n : -n;
  }
  }
}

J、估计人数

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

问题描述

给定一个 N × M 的方格矩阵，矩阵中每个方格标记 0 或者 1 代表这个方格是不是有人踩过。

已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。

走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。

请你计算至少有多少人在矩阵上走过。

输入格式

输入第一行包含两个整数 N、M。

以下 N 行每行包含 M 个整数 (0/1)，代表方格矩阵。

输出格式

输出一个整数代表答案。

测试样例1

Input：

5 5

00100

11111

00100

11111

00100

Output：

评测用例规模与约定

对于所有评测用例，1 ≤ N, M ≤ 20，标记为 1 的方格不超过 200 个。

package action;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
public class demo {
  static int V = 1;
  static int source[];
  static boolean graph[][], marked[];
  public static void main(String[] args) {
  InputReader in = new InputReader(System.in);
  int n = in.nextInt(), m = in.nextInt();
  int idx[][] = new int[n + 1][m + 1];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    if (in.split() == '1')
      idx[i][j] = V++;
  graph = new boolean[V][V];
  marked = new boolean[V];
  source = new int[V];
  for (int i = 0, v; i < n; i++)
    for (int j = 0; j < m; j++)
    if (idx[i][j] > 0) {
      v = idx[i][j];
      if (idx[i + 1][j] > 0)
      graph[v][idx[i + 1][j]] = true;
      if (idx[i][j + 1] > 0)
      graph[v][idx[i][j + 1]] = true;
    }
  for (int k = 1; k < V; k++)
    for (int i = 1; i < V; i++)
    for (int j = 1; j < V; j++)
      graph[i][j] |= graph[i][k] & graph[k][j];
  int cnt = 0;
  for (int i = 1; i < V; i++) {
    Arrays.fill(marked, false);
    cnt += dfs(i) ? 1 : 0;
  }
  System.out.print(V - cnt - 1);
  }
  static boolean dfs(int v) {
  for (int i = 1; i < V; i++) {
    if (graph[v][i]) {
    if (marked[i])
      continue;
    marked[i] = true;
    if (source[i] == 0 || dfs(source[i])) {
      source[i] = v;
      return true;
    }
    }
  }
  return false;
  }
  static class InputReader {
  InputStream in;
  int next, len;
  byte[] buff;
  InputReader(InputStream in) {
    this(in, 8192);
  }
  InputReader(InputStream in, int buffSize) {
    this.buff = new byte[buffSize];
    this.next = this.len = 0;
    this.in = in;
  }
  int getByte() {
    if (next >= len)
    try {
      next = 0;
      len = in.read(buff);
      if (len == -1)
      return -1;
    } catch (IOException e) {
      e.fillInStackTrace();
    }
    return buff[next++];
  }
  int split() {
    int c = getByte();
    while (c <= 32 || c == 127)
    c = getByte();
    return c;
  }
  int nextInt() {
    int n = 0, c = split();
    boolean flag = true;
    if (c == '-') {
    c = getByte();
    flag = false;
    }
    while (c >= '0' && c <= '9') {
    n = n * 10 + (c & 0xf);
    c = getByte();
    }
    return flag ? n : -n;
  }
  }
}

这套题有几个题应该是给本科的，专门刁难了一下大专的孩子们，不道义啊。

第十届蓝桥杯决赛JavaC组真题——详细答案对照(完整版)-2

F、最长子序列

G、数正方形

H、矩阵计数

I、大胖子走迷宫

J、估计人数

热门文章

最新文章

相关课程

相关电子书

相关实验场景