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

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

F、最长子序列

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


问题描述


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

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


输入格式


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

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


输出格式


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

测试样例1

Input:

ABCDEABCD

AABZ


Output:

3

评测用例规模与约定


对于 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);
  }
}

image.png


G、数正方形

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


问题描述


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

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

(如:图7)所示的正方形都是合法的。

image.png



输入格式


输入包含一个整数 N。


输出格式


输出一个整数代表答案。


测试样例1

Input:

4


Output:

20

评测用例规模与约定


对于所有评测用例,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:

49

评测用例规模与约定


对于所有评测用例,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;
  }
}

image.png


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:

16

评测用例规模与约定


对于 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;
  }
  }
}



image.png

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:

3

评测用例规模与约定


对于所有评测用例,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;
  }
  }
}


image.png

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


相关文章
|
2月前
第十四届蓝桥杯集训——JavaC组第十三篇——for循环
第十四届蓝桥杯集训——JavaC组第十三篇——for循环
43 0
|
2月前
|
算法
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
48 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
31 0
|
2月前
|
Java C语言
第十四届蓝桥杯集训——JavaC组第十四篇——嵌套循环
第十四届蓝桥杯集训——JavaC组第十四篇——嵌套循环
40 0
|
2月前
|
C语言
第十四届蓝桥杯集训——JavaC组第十一篇——switch
第十四届蓝桥杯集训——JavaC组第十一篇——switch
40 0
|
2月前
第十四届蓝桥杯集训——JavaC组第十篇——分支语句
第十四届蓝桥杯集训——JavaC组第十篇——分支语句
38 0
|
2月前
|
算法
第十四届蓝桥杯集训——JavaC组第九篇——三元运算符
第十四届蓝桥杯集训——JavaC组第九篇——三元运算符
35 0
|
2月前
第十四届蓝桥杯集训——JavaC组第九篇——位运算符
第十四届蓝桥杯集训——JavaC组第九篇——位运算符
27 0
|
2月前
第十四届蓝桥杯集训——JavaC组第八篇——进制转换
第十四届蓝桥杯集训——JavaC组第八篇——进制转换
39 0
|
2月前
|
Java 测试技术 C++
第十四届蓝桥杯集训——JavaC组——运算符练习题
第十四届蓝桥杯集训——JavaC组——运算符练习题
50 0