Java 大学A组
- 试题 A: 三升序列
- 试题 B: 切割
- 试题 C: 最优旅行
- 试题 D: 骰子制造
- 试题 E: 无方集合
- 试题 F: 大胖子走迷宫
- 背会单词睡觉，不然四级无了
蓝桥杯个人赛软件类历届真题及其解析
更新中；
试题 A: 三升序列
本题总分： 5 5 5 分
【问题描述】
对于一个字母矩阵，我们称矩阵中的一个三升序列是指在矩阵中找到三个字母，它们在同一行，同一列，或者在同一 45 45 45 度的斜线上，这三个字母从左向右看、或者从上向下看是递增的。
例如，如下矩阵中
YQPD BKEZ AFYV
有 B K Z mathrm{BKZ} BKZ、 B E Z mathrm{BEZ} BEZ、 A F Y mathrm{AFY} AFY、 A F V mathrm{AFV} AFV、 A K P mathrm{AKP} AKP、 D E F mathrm{DEF} DEF 等 6 6 6 个三升序列。注意当三个字母是从左下到右上排列时，从左向右看和从上向下看是不同的顺序。
对于下面的 30 30 30 行 50 50 50 列的矩阵，请问总共有多少个三升序列？（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
180414
这里程序做的是，枚举三升序列的中间元素，以统计出全部的三升序列，
为了增加代码的重用性，我们使用统计某段连续的元素构成的子序列，从左向右看递增的三升序列程序来统计从上向下看递增的三升序列。
矩阵中的元素可以朝 8 8 8 个方向连续，按行号的增量 x x x 与列号的增量 y y y 构成的二元组 ( x , y ) (x,y) (x,y)，分别记为： ( 0 , 1 ) (0,1) (0,1)、 ( − 1 , 1 ) (-1,1) (−1,1)、 ( − 1 , 0 ) (-1,0) (−1,0)、 ( − 1 , − 1 ) (-1,-1) (−1,−1)、 ( 0 , − 1 ) (0,-1) (0,−1)、 ( 1 , − 1 ) (1,-1) (1,−1)、 ( 1 , 0 ) (1,0) (1,0)、 ( 1 , 1 ) (1,1) (1,1)。
其中 ( 0 , 1 ) (0,1) (0,1)、 ( − 1 , 1 ) (-1,1) (−1,1)、 ( 1 , 0 ) (1,0) (1,0)、 ( 1 , 1 ) (1,1) (1,1) 与其余 4 4 4 个方向相逆且均能使用统计 ( 0 , 1 ) (0,1) (0,1) 方向三升序列程序来统计，但我们还能发现 ( − 1 , 1 ) (-1,1) (−1,1) 从上往下看为三升序列时，从左向右恰反，故而再统计一遍其逆方向 ( 1 , − 1 ) (1,-1) (1,−1)。
import java.io.FileInputStream;
public class Test {
static int N = 30, M = 50, K = 5;
int[][] matrix = new int[N][M], offset = {{1, 0}, {0, 1}, {-1, 1}, {1, -1}, {1, 1}};
public static void main(String[] args) { new Test().run(); }
void run() {
try(FileInputStream in = new FileInputStream("inc.txt")) {
int ans = 0, less, more, x, y;
for (int i = 0, bt; i < N; ++i)
for (int j = 0; j < M; ++j) {
do bt = in.read();
while (bt <= 0x20 || bt == 0x7f);
matrix[i][j] = bt;
}
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
for (int k = 0; k < K; ++k) {
less = more = 0;
for (x = i, y = j; x >= 0 && y >= 0 && x < N && y < M; x -= offset[k][0], y -= offset[k][1])
if (matrix[x][y] < matrix[i][j]) ++less;
for (x = i, y = j; x >= 0 && y >= 0 && x < N && y < M; x += offset[k][0], y += offset[k][1])
if (matrix[x][y] > matrix[i][j]) ++more;
ans += less * more;
}
System.out.println(ans);
} catch (Exception e) {
e.printStackTrace();
}
}
}
试题 B: 切割
本题总分： 5 5 5 分
【问题描述】
在 4 × 4 4times4 4×4 的方格矩阵中画一条直线。则直线穿过的方格集合有多少种不同的可能？
这个里直线穿过一个方格当且仅当直线将该方格分割成面积都大于 0 0 0 的两部分。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
267
据说是 267 267 267，但我编的程序计算不出来，先挂着吧。
public class Test {
public static void main(String[] args) { new Test().run(); }
double accuracy = 0.01;
int N = 4, M = 4, ans = 0;
int[][] index = new int[N][M];
boolean[][] zero = new boolean[N + 1][M + 1];
boolean[][] positive = new boolean[N + 1][M + 1];
boolean[] map = new boolean[1 << N * M];
void run() {
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
index[i][j] = 1 << i * M + j;
for (double x = 0; x <= N; x += accuracy) {
for (double y = 0; y <= M; y += accuracy) {
total(y / -x, y); // (x1:x, y1:0) (x2:0, y2:y)
total(y / (N - x), -x * y / (N - x)); // (x1:x, y1:0) (x2:N, y2:y)
}
for (double x2 = 0; x2 <= N; x2 += accuracy)
total(M / (x2 - x), -x * M / (x2 - x)); // (x1:x, y1:0) (x2:x2, y2:M)
}
for (double y = 0; y <= M; y += accuracy) {
for (double x = 0; x <= N; x += accuracy)
total((M - y) / x, y); // (x1:0, y1:y) (x2:x, y2:M)
for (double y2 = 0; y2 <= M; y2 += accuracy)
total((y2 - y) / N, y); // (x1:0, y1:y) (x2:N, y2:y2)
}
for (boolean mark : map) if (mark) ++ans;
System.out.println(ans);
}
void total(double k, double b) {
for (int x = 0; x <= N; ++x)
for (int y = 0; y <= M; ++y) {
double tmp = k * x + b - y;
zero[x][y] = abs(tmp) <= 1e-10;
positive[x][y] = tmp > 1e-10;
}
int tot = 0;
for (int x = 0; x < N; ++x)
for (int y = 0; y < M; ++y) {
if (positive[x][y] == positive[x + 1][y] &&
positive[x][y] == positive[x][y + 1] &&
positive[x][y] == positive[x + 1][y + 1]) continue;
if (zero[x][y] && zero[x + 1][y] && zero[x][y + 1] && zero[x + 1][y + 1]) continue;
tot |= index[x][y];
}
map[tot] = true;
}
double abs(double a) { return a > 0 ? a : -a; }
}
试题 C: 最优旅行
本题总分： 10 10 10 分
【问题描述】
中国的高铁四通八达，乘坐方便，小明经常乘坐高铁在城市间旅游。
现在，小明又有了一个长假，他打算继续乘坐高铁旅游。这次，他打算到下面的城市旅游。
上海、广州、长沙、西安、杭州、济南、成都、南京、昆明、郑州、天津、太原、武汉、重庆、南昌、长春、沈阳、贵阳、福州。
小明打算从北京出发，游览以上每个城市正好一次，最终回到北京。在每个城市（除北京外），小明都至少停留 24 24 24 小时。而当小明决定从一个城市去往另一个城市时，他只会选择有直接高铁连接的城市，不会在中途换乘转车。
在试题目录下有一个文件 t r i p . t x t mathrm{trip.txt} trip.txt 保存了小明可以选择的车次，小明不会选择其他车次。
小明出发的时间是第 1 1 1 天的中午 12 12 12: 00 00 00。请问，小明游览完以上城市正好一次，最终回到北京，最快需要多少分钟（请注意单位为分钟，请注意除北京外的城市需要至少停留 24 24 24 小时，即最少停留 1440 1440 1440 分钟）。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
41613
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.time.LocalTime;
import java.util.*;
public class Test {
public static void main(String[] args) { new Test().run(); }
Map> graph = new HashMap();
Map visited = new HashMap();
int depth = 0, ans = 0x3f3f3f3f;
void run() {
try(BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("trip.txt"), "GBK"))) {
String line = in.readLine();
while ((line = in.readLine()) != null) {
StringTokenizer token = new StringTokenizer(line);
token.nextToken();
String u = token.nextToken();
String v = token.nextToken();
int start = LocalTime.parse(token.nextToken()).toSecondOfDay() / 60;
int end = LocalTime.parse(token.nextToken()).toSecondOfDay() / 60;
if (!graph.containsKey(u)) {
graph.put(u, new ArrayList());
visited.put(u, false);
}
graph.get(u).add(new Train(v, start, end));
}
dfs("北京", (visited.size() - 1) * 1440 + 720);
System.out.println(ans - 720);
} catch (Exception e) {
e.fillInStackTrace();
}
}
void dfs(String start, int time) {
if (time > ans) return;
if (depth == visited.size() && start.equals("北京")) ans = min(ans, time);
for (Train train : graph.get(start)) {
if (visited.get(train.to)) continue;
visited.put(train.to, true);
++depth;
if (time % 1440 > train.start)
dfs(train.to, time + 1440 - time % 1440 + train.end);
else
dfs(train.to, time - time % 1440 + train.end);
visited.put(train.to, false);
--depth;
}
}
int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }
class Train {
String to;
int start, end;
Train(String to, int start, int end) {
this.to = to;
this.start = start;
this.end = end;
}
}
}
很莫名其妙的一道搜索题，这里没做字符串到整型的映射是因为，你编写完这部分程序，你写的暴力早把结果跑出来了。
想自己跑一遍这个程序的，等上半分钟吧。
试题 D: 骰子制造
本题总分： 10 10 10 分
【问题描述】
骰子是游戏中常用的一个工具，骰子是一个正六面体，六个面分别是 1 1 1 到 6 6 6 点，每种一个，通常情况下， 1 1 1 到 6 6 6 点的样子如下图所示。
其中
1
1
1、
4
4
4、
5
5
5 点旋转
90
90
90、
180
180
180、
270
270
270 度后形状不变，而
2
2
2、
3
3
3、
6
6
6 点旋转
180
180
180 度后形状不变。
小明要制造一批骰子，他希望制造出来后有意思一点，他希望他制造出来的骰子任何两个旋转后都是不相同的。请问，他最多能造出多少个？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
240
伯恩赛德引理
Burnside’s lemma
设 G G G 是一个有限群，作用在集合 X X X 上。对每个 g g g 属于 G G G 令 X g X^g Xg 表示 X X X 中在 g g g 作用下的不动元素。伯恩赛德引理断言轨道数（记作 ∣ X / G ∣ |X/G| ∣X/G∣）由如下公式给出： ∣ X / G ∣ = 1 ∣ G ∣ ∑ g ∈ G ∣ X g ∣ . |X/G|=frac 1{left|Gright|}sum_{gin G}|X^g|. ∣X/G∣=∣G∣1g∈G∑∣Xg∣. 从而轨道数（是一个自然数或无穷）等于被 G G G 中一个元素保持不动的点个数的平均值（故同样是自然数或无穷）。
—— 摘自 Wiki
更具体地说， X X X 为不考虑旋转后都是否相同的骰子方案集合，显然 ∣ X ∣ = 6 ! × 2 3 |X| = 6!times2^3 ∣X∣=6!×23， G G G 为骰子上的置换群，容易得知 ∣ G ∣ = 24 |G| = 24 ∣G∣=24（因为阐述 B u r n s i d e ′ s l e m m a mathrm{Burnside's lemma} Burnside′s lemma 的文章中，绝大多数都会以立方体染色为例，经过一系列自然语言描述后，可以得到 ∣ G ∣ = 1 + 6 + 3 + 6 + 8 = 24 |G| = 1 + 6 + 3 + 6 + 8 = 24 ∣G∣=1+6+3+6+8=24）， X g X^g Xg 只当 g = e g = e g=e 时不为零，因为骰子六个面都不相同。
所以，最终答案为 1 24 6 ! × 2 3 = 240 displaystyle{frac 1{24}6!times2^3 = 240} 2416!×23=240。
或者可以从组合的方向来思考，设骰子的六个面分别为：顶、底、前、后、左、右，由于某个面必然会出现在骰子上，故我们将 1 1 1 确定到顶而不计入方案数，此时底有 5 5 5 种取法，同样的，我们取某个未取的数作为前，则后有 3 3 3 种取法，左右此时已经确定，但还是有 2 2 2 种排列法，
故，只考虑点数，不考虑花纹，能造出的不相同的骰子至多有 5 × 3 × 2 = 30 5 times 3 times 2 = 30 5×3×2=30 个，同时 2 2 2、 3 3 3、 6 6 6 点有两种不同的花纹，故答案为 30 × 2 3 = 240 30 times 2^3 = 240 30×23=240。
试题 E: 无方集合
本题总分： 15 15 15 分
【问题描述】
小明不是很喜欢完全平方数，他甚至不喜欢加起来是完全平方数的两个数。
今天，他想从 1 1 1 到 100 100 100 中选择一些数组成一个集合，要求不选择任何一个完全平方数，集合中任意两个数相加也不能是完全平方数。请问，小明最多能选出多少个数。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
36
最大独立集
一般图上的最大独立集，容易考虑到 B r o n mathrm{Bron} Bron– K e r b o s c h mathrm{Kerbosch} Kerbosch 算法，但朴素的 B K mathrm{BK} BK 复杂度上界在 O ( 3 n 3 ) O(3^{frac n3}) O(33n)，通常我们难以达到这个上界，
所以我去碰瓷了，莫约跑了 24 24 24 分钟，
N P mathrm{NP} NP 问题就是恶心，下面给出一种概率性算法，设一般图 G = ( V , E ) G=(V,E) G=(V,E)， n = ∣ V ∣ n = |V| n=∣V∣， G G G 的顶点分别为 1 ∼ n 1 sim n 1∼n，容易在 O ( n 2 ) O(n^2) O(n2) 的复杂度内确定一个 n n n 级排列的元素代表的顶点构成的显然团的大小，跟进一步地说。
设 G G G 的最大团的某个排序为 G ′ = v 1 , v 2 , ⋯ , v m G'=v_1,v_2,cdots,v_m G′=v1,v2,⋯,vm，我们随机的给出 n n n 级排列 S S S，其中 S S S 存在一个子序列 S ′ = G ′ S' = G' S′=G′(顺序不对就重排 G ′ G' G′)， v i v_i vi 在 S S S 中的位置为 w i w_i wi，当 ∀ i forall i ∀i， s i ∉ G i s_i notin G_i si∈Gi，都 ∃ j exists j ∃j， w j < i ∧ w j ↮ s i w_j
细节和“显然团”就看我代码吧，
能力有限就不计算复杂度了。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Test {
public static void main(String[] args) { new Test().run(); }
int N = 100, times = 100000, ans = 0, m;
boolean[] square = new boolean[2 * N];
List G = new ArrayList();
int[] T = new int[N];
void run() {
for (int i = 1; i * i < 2 * N; ++i) square[i * i] = true;
for (int i = 1; i <= N; ++i)
if (!square[i]) G.add(i);
while (times-- > 0) {
Collections.shuffle(G);
m = 0; flag: for (int u : G) {
for (int v = 0; v < m; ++v)
if (square[u + T[v]]) continue flag;;
T[m++] = u;
}
ans = Math.max(ans, m);
}
System.out.println(ans);
}
}
答案不对可以重复运行几次，或调整times增加ans逼近最大团的概率，如是在比赛现场，我会给times再加两个 0 0 0。
试题 F: 大胖子走迷宫
时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 15 15 15 分
【问题描述】
小明是个大胖子，或者说是个大大胖子，如果说正常人占用 1 × 1 1 × 1 1×1 的面积，小明要占用 5 × 5 5 × 5 5×5 的面积。
由于小明太胖了，所以他行动起来很不方便。当玩一些游戏时，小明相比小伙伴就吃亏很多。
小明的朋友们制定了一个计划，帮助小明减肥。计划的主要内容是带小明玩一些游戏，让小明在游戏中运动消耗脂肪。走迷宫是计划中的重要环节。
朋友们设计了一个迷宫，迷宫可以看成是一个由 n × n n × n n×n 个方阵组成的方阵，正常人每次占用方阵中 1 × 1 1 × 1 1×1 的区域，而小明要占用 5 × 5 5 × 5 5×5 的区域。小明的位置定义为小明最正中的一个方格。迷宫四周都有障碍物。
为了方便小明，朋友们把迷宫的起点设置在了第 3 3 3 行第 3 3 3 列，终点设置在了第 n − 2 n − 2 n−2 行第 n − 2 n − 2 n−2 列。
小明在时刻 0 0 0 出发，每单位时间可以向当前位置的上、下、左、右移动单位 1 1 1 的距离，也可以停留在原地不动。小明走迷宫走得很辛苦，如果他在迷宫里面待的时间很长，则由于消耗了很多脂肪，他会在时刻 k k k 变成一个胖子，只占用 3 × 3 3 × 3 3×3 的区域。如果待的时间更长，他会在时刻 2 k 2k 2k 变成一个正常人，只占用 1 × 1 1 × 1 1×1 的区域。注意，当小明变瘦时迷宫的起点和终点不变。
请问，小明最少多长时间能走到迷宫的终点。注意，小明走到终点时可能变瘦了也可能没有变瘦。
【输入格式】
输入的第一行包含两个整数 n , k n, k n,k。
接下来 n n n 行，每行一个由 n n n 个字符组成的字符串，字符为 + + + 表示为空地，字符为 ∗ * ∗ 表示为阻碍物。
【输出格式】
输出一个整数，表示答案。
【样例输入】
9 5 +++++++++ +++++++++ +++++++++ +++++++++ +++++++++ ***+***** +++++++++ +++++++++ +++++++++
【样例输出】
16
【评测用例规模与约定】
对于
30
%
30%
30% 的评测用例，
1
≤
n
≤
50
1 ≤ n ≤ 50
1≤n≤50。
对于
60
%
60%
60% 的评测用例，
1
≤
n
≤
100
1 ≤ n ≤ 100
1≤n≤100。
对于所有评测用例，
1
≤
n
≤
300
，
1
≤
k
≤
1000
1 ≤ n ≤ 300，1 ≤ k ≤ 1000
1≤n≤300，1≤k≤1000。
背会单词睡觉，不然四级无了
