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

## F、最长子序列

Input：

ABCDEABCD

AABZ

Output：

3

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、数正方形

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

Input：

4

Output：

20

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);
}
System.out.println(ans.longValue());
}
}

## H、矩阵计数

Input：

2 3

Output：

49

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、大胖子走迷宫

Input：

9 5

+++++++++

+++++++++

+++++++++

+++++++++

+++++++++

***+*****

+++++++++

+++++++++

+++++++++

Output：

16

package action;
import java.io.IOException;
import java.io.InputStream;
import java.util.Queue;
public class demo {
public static void main(String[] args) {
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;
}
}
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());
}
}
}
InputStream in;
int next, len;
byte[] buff;
this(in, 8192);
}
this.buff = new byte[buffSize];
this.next = this.len = 0;
this.in = in;
}
int getByte() {
if (next >= len)
try {
next = 0;
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、估计人数

Input：

5 5

00100

11111

00100

11111

00100

Output：

3

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) {
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;
}
InputStream in;
int next, len;
byte[] buff;
this(in, 8192);
}
this.buff = new byte[buffSize];
this.next = this.len = 0;
this.in = in;
}
int getByte() {
if (next >= len)
try {
next = 0;
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;
}
}
}

|
2月前

43 0
|
2月前
|

48 0
|
2月前
|

31 0
|
2月前
|
Java C语言

40 0
|
2月前
|
C语言

40 0
|
2月前

38 0
|
2月前
|

35 0
|
2月前

27 0
|
2月前

39 0
|
2月前
|
Java 测试技术 C++

50 0