首页 > 分享 > 第八届蓝桥杯全国总决赛真题解析

第八届蓝桥杯全国总决赛真题解析

萌宠菠菠乐园
2024-10-16 07:36

36进制

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

对于 16 进制，我们使用字母 A−F 来表示 10 及以上的数字。

如法炮制，一直用到字母 Z，就可以表示 36 进制。

36 进制中，A 表示 10，Z表示 35，AA 表示370。

你能算出 MANY 表示的数字用 10 进制表示是多少吗?

答案：1040254

解析：标准的无语题

代码：

package 蓝桥杯全国总决赛真题; import java.util.Scanner; public class 三十六进制 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); int a = 'M'-'A'+10; int b = 'A'-'A'+10; int c = 'N'-'A'+10; int d = 'Y'-'A'+10; System.out.println((int)(d*Math.pow(36, 0)+c*Math.pow(36, 1)+b*Math.pow(36, 2)+a*Math.pow(36, 3))); } }

12345678910111213141516

瓷砖样式

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小明家的一面装饰墙原来是 3×10 的小方格。现在手头有一批刚好能盖住 22 个小方格的长方形瓷砖。瓷砖只有两种颜色：黄色和橙色。

小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。小明有个小小的强迫症：忍受不了任何 2×2 的小格子是同一种颜色。（瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝）显然，对于2×3 个小格子来说，口算都可以知道：一共 10种贴法，如下图所示：

但对于3×10 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。

答案：101466

解析：

本题数据量很小，我们采用递归和递推做法都可以，我们这里只介绍递归的做法。

递归的时候分四种情况：2 * 2 = 4，注意边界条件。

放置方向：（1）横向放置

（2）纵向放置

颜色：（1）黄色

（2）橙色

每一种情况可能会出现处重复，我们需要用字符串进行存储，然后存入set去重即可，最后的答案即为set的尺寸。

代码：

package 蓝桥杯全国总决赛真题; import java.util.Arrays; import java.util.HashSet; public class 瓷砖样式 { static HashSet<String>s = new HashSet<>(); static int m[][] = new int[1000][1000]; //-1空，1黄，0橙 static boolean check() { for(int i=1;i<=2;i++) { for(int j=1;j<=9;j++) { if((m[i][j] + m[i+1][j+1] +m[i+1][j] + m[i][j+1])%4==0)return false; } } return true; } static String a =""; static void dfs(int x, int y) { if(x>3) { a = ""; for(int i=1;i<=3;i++) { for(int j=1;j<=10;j++) { a += (char)(m[i][j] +'0'); } } // System.out.println(a); if(check()) { s.add(a); } return ; } if(m[x][y] == -1){ if(y < 10 && m[x][y+1] == -1){ //横向放置 for(int i = 0; i <= 1; ++i){ //选择颜色 m[x][y] = m[x][y+1] = i; if(y + 2 <= 10)dfs(x, y + 2); else dfs(x + 1, 1); m[x][y] = m[x][y+1] = -1; } } if(x < 3 && m[x+1][y] == -1){ //纵向放置 for(int i = 0; i <= 1; ++i){ //选择颜色 m[x][y] = m[x+1][y] = i; if(y + 1 <= 10)dfs(x, y + 1); else dfs(x + 1, 1); m[x][y] = m[x+1][y] = -1; } } } else if(y == 10) dfs(x + 1, 1); else dfs(x, y + 1); } public static void main(String[] args) { // TODO Auto-generated method stub for(int i=0;i<=5;i++) { for(int j=0;j<=15;j++) { m[i][j] = -1; } } dfs(1,1); System.out.println(s.size()); } }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465

希尔伯特曲线

本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。

希尔伯特曲线是以下一系列分形曲线 Hn 的极限。我们可以把 Hn 看作一条覆盖 2^n × 2^n 方格矩阵的曲线，曲线上一共有 2^n × 2^n 个顶点(包括左下角起点和右下角终点)，恰好覆盖每个方格一次。

Hn(n > 1)可以通过如下方法构造：

将 Hn-1 顺时针旋转90度放在左下角
将 Hn-1 逆时针旋转90度放在右下角
将2个 Hn-1 分别放在左上角和右上角
用3条单位线段把4部分连接起来
对于 Hn 上每一个顶点 p ，我们定义 p 的坐标是它覆盖的小方格在矩阵中的坐标(左下角是(1, 1)，右上角是(2^n, 2^n)，从左到右是X轴正方向，从下到上是Y轴正方向)，
定义 p 的序号是它在曲线上从起点开始数第几个顶点(从1开始计数)。

以下程序对于给定的n(n <= 30)和p点坐标(x, y)，输出p点的序号。请仔细阅读分析源码，填写划线部分缺失的内容。

代码：

import java.util.Scanner; public class Main { public static long f(int n, int x, int y) { if (n == 0) return 1; int m = 1 << (n - 1); if (x <= m && y <= m) { return f(n - 1, y, x); } if (x > m && y <= m) { return 3L * m * m + f(n - 1, ________________ , m * 2 - x + 1); //填空 } if (x <= m && y > m) { return 1L * m * m + f(n - 1, x, y - m); } if (x > m && y > m) { return 2L * m * m + f(n - 1, x - m, y - m); } return -1; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int x = in.nextInt(); int y = in.nextInt(); System.out.println(f(n, x, y)); } }

1234567891011121314151617181920212223242526272829

答案：

m + 1 - y 1

解析：理清坐标的对应关系。

发现环

小明的实验室有 NN 台电脑，编号 N1⋯N。原本这 N 台电脑之间有 N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。

不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了 BUG。

为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？

输入描述

输入范围：

第一行包含一个整数 N 。

以下 NN 行每行两个整数 a,b，表示 a 和 b 之间有一条数据链接相连。

其中， 1<= N <= 10^5， 1 <= a, b<= N, 1≤N≤105，1≤a,b≤N。

输入保证合法。

输出描述

按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。

输入输出样例

输入

5 1 2 3 1 2 4 2 5 5 3 123456

输出

1 2 3 5 1

解析：判断一个图是否有环，依次删除度为 1 的点以及与其相连的边，这样可以把所有不成环的链上点依次删除，最后也无法被删除的点集就是题目要求的答案，按照编号从小到大输出即可。

统计所有点的入度；创建一个队列维护所有入度为 1 的点，将所有度等于 1 的节点加入队列。（本题中没有独立的节点，所以不用考虑度为 0 的情况）；当队列不为空时，弹出队首元素，把与队首元素相邻的节点入度减 1，如果相邻节点度数变为 1，则将相邻节点加入队列；循环结束后，从小到大判断每个结点的入度，若入度大于 1，则说明该节点在环内，输出该节点。

代码：

// package 蓝桥杯全国总决赛真题; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Vector; public class Main { static Vector<Integer>g[] = new Vector[100050]; static int n; static Queue<Integer>q = new LinkedList<>(); static int d[] = new int[100050]; public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); n = in.nextInt(); for(int i=0;i<10050;i++)g[i] = new Vector<Integer>(); for(int i= 1;i<=n;i++) { int a, b; a = in.nextInt(); b = in.nextInt(); g[a].add(b); g[b].add(a); d[a]++; d[b]++; } for(int i=1;i<=n;i++) { if(d[i]==1)q.add(i); } while(!q.isEmpty()) { int now = q.peek(); q.remove(); for(int i=0;i<g[now].size();i++) { int v = g[now].get(i); d[v]--; if(d[v] == 1) q.add(v); } } for(int i=1 ;i<=n; i++) { if(d[i]>1) { if(i!=n) System.out.print( i + " " ); else System.out.println( i ); } } } }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

对局匹配

小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。

小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是 K 的两名用户匹配在一起。如果两人分差小于或大于 KK，系统都不会将他们匹配。

现在小明知道这个网站总共有 N 名用户，以及他们的积分分别是 A1,A2,⋯AN。

小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于 K)？

输入描述

第一行包含两个个整数 N,K。

第二行包含 NN 个整数 A1,A2,⋯AN。

其中 1≤N≤105,0≤Ai≤105,0≤K≤105。

输出描述

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

输入输出样例

示例

输入

10 0 1 4 2 8 5 7 1 4 2 8 12

输出

6 1

解析：

如果 k = 0，那么只用考虑总过出现了多少不同积分的用户数，因为相同积分的用户只能上线一个。

如果 k > 0，假设当前积分为 x，则他能影响到的积分为 x + k 和 x - k，又会因为积分为 x + k 用户在线与否间接地影响到 x + 2k…可以发现积分对 k 求余相同的用户会互相影响,所以可以采用dp做法。因此我们可以根据每个用户积分对 k 求余的结果分成余数为 0 ~ k - 1 的组，共 k 组。此时我们只要解决每一组的最多在线人数最后求和即可。

设计动态规划状态：dp[i] 表示在当前分组内，积分从 0 到 i 的范围内最多有多少用户可以同时上线。num[i] 代表积分为 i 的用户有多少个。

那么对于 dp[i]，只有两种方法转移而来：

1.积分为 i 的用户上线，所以积分为 i - k 的用户不能上线，但是对积分为 i - 2 * k 及以下的没有影响，dp[i] = num[i] + dp[i - 2 * k];

2.积分为 i 的用户没有上线，所以积分为 i - k 的用户可以上线，直接等于积分为 i - k 及以下的答案即可，dp[i] = dp[i- k];

转移方程： dp[i] = max(dp[i - 2 * k] + num[i], dp[i - k]);

事实上 num 数组可以直接初始化到 dp 数组中，并将转移方程改为 dp[i] = max(dp[i - 2 * k] + dp[i], dp[i - k]);

代码：

package 蓝桥杯全国总决赛真题; import java.util.HashSet; import java.util.Scanner; public class 对局匹配 { static int num[] = new int[10000]; static int dp[] = new int[10000]; public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); if(k==0) { HashSet<Integer>s = new HashSet<>(); for(int i=1;i<=n;i++) { s.add(in.nextInt()); } System.out.println(s.size()); } else { for(int i=1;i<=n;i++) { int x = in.nextInt(); num[x]++; } for(int i=1;i<=10050;i++) { if(i>=2*k) { dp[i] = Math.max(num[i]+dp[i-2*k], dp[i-k]); } else if(i>=k) { dp[i] = Math.max(dp[i-k], dp[i]); } } int ans = 0; for(int i=10050;i>=10050-k;i--) { ans+=dp[i]; } System.out.println(ans); } } }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849