![[蓝桥杯]赛事介绍](/images/banner7.webp)
蓝桥杯介绍
蓝桥杯赛制
IO赛制
赛制特点： 个人赛：每个选手独立参赛。 比赛时长：4小时。 题目数量：通常8-10道题。 答题方式：选手每题可提交多次，但==仅保留最后一次提交结果，比赛期间无法看到评测结果==。 题目类型：单结果题+编程题。单结果题：只需要输出题目问题的答案。编程题：有多个测试点，每个测试点有一个正确答案。 评分规则：每道题包含多个测试点，根据通过的测试点数量得分，部分数据通过也能获得部分分数。最终得分在赛后公布。
OI赛制最大的特点在于考试的时候看不到评测结果，不像ACM赛制可以立马看到结果，知道自己对不对，但是好处是有部分分，过了几个点也有分拿。
图例[19728 拼十字]
官网题库练习界面，有调试和提交检测按钮。调试按钮使用第一个节点的测试数据测试程序能不能得到正确结果，提交检测会检测所有测试数据，最后给出完整的结果。
怎样的答案才算是正确答案？ 1.程序逻辑正确 2.满足时间复杂度和空间复杂度的要求
根据选择使用的算法不同，复杂度不同，通过率会有差别。20个检测点，使用回溯算法，通过6个，得6分。
==在正式比赛中，需要在指定位置上传自己的程序代码。看不到提交后的结果，不能进行调试。检测方法就是根据题目要求，自己想例子手动测试。==
蓝桥杯常用数据结构
列表(数组)
- 特点：
- 连续存储，支持随机访问，索引复杂度为 \(O(1)\)。
- 插入、删除复杂度为 \(O(n)\)。
- 应用场景：
- 简单的序列存储（如题目输入输出）。
- 作为动态数组的基础结构。
- 蓝桥杯常见题型：
- 前缀和：求连续子数组的和。
- 双指针：查找满足条件的子数组或子序列。
- 例题：
- 给定一个数组，找到和为目标值的连续子数组。
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2 示例 2：
输入：nums = [1,2,3], k = 3 输出：2
解题思路：前缀和
class Solution {
public int subarraySum(int[] nums, int k) {
int[] pre = new int[nums.length+1];//注意这里要+1
//得到前缀和数组
for(int i = 0; i < nums.length ; i++) {
pre[i+1] = nums[i]+pre[i];
}
int count = 0;
//通过 i 和 j 得到 所有子数组区间，如果符合答案就+1
for(int i = 0 ; i < nums.length ; i++) {
for(int j = i ; j < nums.length ; j++) {
if(pre[j+1] - pre[i] == k) {
count++;
}
}
}
return count;
}
}
这种方法时间在遇到大量数据时，复杂度较高。有没有更优的解法？
栈，堆
栈：
- 特点：后进先出（LIFO）。
- 应用：括号匹配、单调栈求解最大矩形、最近较小元素问题。
- 蓝桥杯常见题型：
- 有效括号判断。
- 模拟递归
堆：
- 特点：支持快速找到最小值或最大值，常用优先队列实现。
- 应用：堆排序、动态维护最大或最小值（如合并 \(k\) 个有序数组）。
- 蓝桥杯常见题型：
- 求第 \(k\) 小（大）值。
- 任务调度中的优先级问题。
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] 示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0] 示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
解题思路：单调栈
单调栈：
- 及时去掉无用数据，保持栈中元素有序
- 使用Deque模拟栈 ， 效率比stack高的多(优化)
- 使用数组模拟，效率比Deque更高(优化)
- 使用一个索引代表当前栈顶元素
- 使用 index– , ++index ，实现元素的出入栈
- 就像山峰一样，得到结果的被更大的抹去了
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// 单调栈 ： 从左往右，栈中存储还没找到下一个最大值的数
int[] res = new int[temperatures.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
res[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
return res;
}
}
集合
- 特点：
- 不允许重复元素，查找、插入复杂度为 \(O(1)\)（基于哈希实现）。
- 应用场景：
- 统计不同元素个数。
- 判断集合关系（如子集或交集）。
- 蓝桥杯常见题型：
- 查找数组中重复的数字。
- 求多个数组的交集或并集。
一般不会单独作为考点出现，会和哈希等结合出现，另外常用于去重操作等。
哈希表
- 特点：
- 提供快速查找，时间复杂度为 \(O(1)\)。
- 通过哈希函数将键映射到值。
- 应用场景：
- 字符串处理（如统计字符频率）。
- 数组问题（如两数之和）。
- 蓝桥杯常见题型：
- 找到和为目标值的两个数。
- 判断是否存在重复元素。
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2 示例 2：
输入：nums = [1,2,3], k = 3 输出：2
解题思路：哈希+前缀和
class Solution {
public int subarraySum(int[] nums, int k) {
//map : key : 前缀和 value : 出现的次数
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);//初始默认值
int presum = 0;
int count = 0;
for(int i = 0 ; i < nums.length ; i++) {
presum += nums[i];//得到当前前缀和
if(map.containsKey(presum - k)) {
count += map.get(presum - k);
}
map.put(presum, map.getOrDefault(presum, 0)+1);
}
return count;
}
}
这种写法，优化了时间复杂度，是更优写法。
蓝桥杯常用算法
数学
- 内容：
- 质数筛选（埃氏筛）。
- 模运算性质（快速幂、取模分配律）。
- 最大公约数与最小公倍数（辗转相除法）。
- 蓝桥杯常见题型：
- 求解多项式系数取模问题。
- 数列递推与模运算结合。
- 典型题目：
- 求 \(a^b mod p\) 的结果。
问题描述： 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可 如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。 例如3/4,1/8,7/1, 都是既约分数。 请问，有多少个既约分数，分子和分母都是1到2020 之间的整数(包括 1和2020)?
评测用例规模与约定 最大运行时间:2s 最大运行内存: 128M
解题思路：辗转相除法
public class 既约分数 {
public static void main(String[] args) {
int ans = 0;
for (int i = 1; i < 2021; i++) {
for (int j = 1; j < 2021; j++) {
if (gcd(i, j) == 1) {
ans++;
}
}
}
System.out.println(ans);
}
//greatest common divisor
//这里使用了递归的方式计算
public static int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
}
回溯算法
- 特点：
- 用于穷举所有可能的解，递归实现。
- 可通过剪枝优化。
- 应用场景：
- 组合问题：如全排列、子集划分。
- 图的搜索：如迷宫问题、八皇后问题。
- 蓝桥杯常见题型：
- 求数组的所有排列。
- 从矩阵的左上角到右下角的路径数。
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
解题思路：回溯算法，确定参数和返回值，终止条件，单层递归逻辑
List<List<Integer>> result= new ArrayList<>();
//注意此时的路径是LinkedList，方便取出元素
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums){
boolean[] used = new boolean[nums.length];
backtracking(0,nums,used);
return result;
}
public void backtracking(int depth, int[] nums, boolean[]used) {
//终止条件，如果此时path的元素个数和nums数组中相等，说明找到一个答案
if(path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length ; i++) {
if(used[i]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtracking(depth + 1, nums , used);
path.removeLast();
used[i] = false;
}
}
动态规划
- 特点：
- 通过分治思想将问题拆分为子问题。
- 利用状态转移方程记录中间结果。
- 常用模型：
- 背包问题（01 背包、多重背包）。
- 序列问题（最长递增子序列、最长公共子序列）。
- 蓝桥杯常见题型：
- 最大子数组和问题。
- 硬币找零问题。
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
解题思路：可以看做0-1背包，使用二维dp数组或一维dp数组解决。
class Solution {
public boolean canPartition(int[] nums) {
//分割两个子集，使得两个子集元素相等 --> 能在数组里找到元素相加等于所有元素和的一半
//所以可以看作背包问题
//判断数组里的元素能否填满所有元素和的一半
int sum = 0;
for(int i = 0 ; i < nums.length ; i++) {
sum += nums[i];
}
if(sum % 2 != 0) {
return false;
}
int target = sum / 2;
// //背包能填满target就够了
// int[] dp = new int[target + 1];
// dp[0] = 0;
// for(int i = 0 ; i < nums.length ; i++) {
// for(int j = target ; j >= nums[i] ; j--) {
// dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
// }
// }
// return dp[target] == target;
int[][] dp = new int[nums.length][target + 1];
for(int i = 0 ; i < target + 1; i++) {
if(i >= nums[0]) {
dp[0][i] = nums[0];
}
}
for(int i = 1 ; i < nums.length ; i++) {
for(int j = 0 ; j < target + 1 ; j++) {
if(j < nums[i]) {
dp[i][j] = dp[i-1][j];
}else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i]);
}
}
}
return dp[nums.length -1][target] == target;
}
}
贪心算法
- 特点：
- 局部最优解推导全局最优解。
- 通常需要证明贪心选择性质和最优子结构。
- 应用场景：
- 区间覆盖问题（如会议室安排）。
- 字符串处理（如霍夫曼编码）。
- 蓝桥杯常见题型：
- 活动选择问题。
- 路径权重最小问题。
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。
解题思路：需要尽可能满足多的孩子，也就是说大饼干尽量分给胃口大的孩子/小饼干尽量分给胃口小的孩子，此时的局部最优能推出全局最优
public int findContentChildren(int[] g, int[] s) {
boolean[] used = new boolean[g.length];
int result = 0;
Arrays.sort(s);
Arrays.sort(g);
//g: 胃口值
//s: 饼干尺寸
for(int i = 0 ; i < g.length ; i++) {
for(int j = 0 ; j < s.length ; j++) {
if(s[j] >= g[i] && !used[i]) {
s[j] = 0;
used[i] = true;
result++;
continue;
}
}
}
return result;
}
小饼干尽量满足小胃口
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(s);
Arrays.sort(g);
// int result = 0;
int index = 0;
//g: 胃口值
//s: 饼干尺寸
//小饼干尽量符合小胃口
//单层循环，需要注意饼干和胃口的循环位置，防止出现index不移动从而出错的情况
for(int i = 0 ; i < s.length && index < g.length ; i++) {
if(s[i] >= g[index]) {
index++;
}
}
return index;
}
图论
- 常用算法：
- 图的表示（邻接矩阵、邻接表）。
- 最短路径算法（Dijkstra、Floyd、Bellman-Ford）。
- 最小生成树（Kruskal、Prim）。
- 蓝桥杯常见题型：
- 判断连通性（深度优先搜索、广度优先搜索）。
- 计算图中最短路径和最小生成树。
- 典型题目：
- 求多点之间的最短路径。
- 寻找关键路径（拓扑排序）。
问题描述 ： 小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是0或1。 如果从一个标为1的位置可以通过上下左右走到另一个标为1的位置，则称两个位置连通。与某一个标为1的位置连通的所有位置(包括自己)组成一个连通分块。 请问矩阵中最大的连通分块有多大?(矩阵太长了，直接放程序里了)
解题思路 ： 先把矩阵构建成一个二维数组，然后使用dfs，寻找最大连通分块。 递归的策略找的方向可以随意：比如先左再下再右再上（这里应该不能用贪心算法进一步优化，比如说先判断那边连通的1比较多） 注意递归需要限制的条件，以及为了防止递归之后，该点还是1，又把该点当作新点也算入连通，每次找到一个连通点，把该点的值设置为2 线性递归，不用考虑回溯条件
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int[][] map = getMap();
public static void main(String[] args) {
int res = 0;
// int x = dfs(map, 0, 0);
for(int i = 0;i < 30;i++) {
for(int j = 0; j < 60;j++) {
if(map[i][j] == 1) {//如果是0，就不用找通路了
int count = dfs(map, i, j);//寻找每个点能连通的最大通路
res = Math.max(res, count);//比较，保存最大的那一个
}
}
}
System.out.println(res);
}
private static int[][] getMap() {
int[][] arr = new int[30][60];
String str = "\r\n" +
"110010000011111110101001001001101010111011011011101001111110\r\n" +
"\r\n" +
"010000000001010001101100000010010110001111100010101100011110 \r\n" +
"\r\n" +
"001011101000100011111111111010000010010101010111001000010100 \r\n" +
"\r\n" +
"101100001101011101101011011001000110111111010000000110110000 \r\n" +
"\r\n" +
"010101100100010000111000100111100110001110111101010011001011 \r\n" +
"\r\n" +
"010011011010011110111101111001001001010111110001101000100011 \r\n" +
"\r\n" +
"101001011000110100001101011000000110110110100100110111101011 \r\n" +
"\r\n" +
"101111000000101000111001100010110000100110001001000101011001 \r\n" +
"\r\n" +
"001110111010001011110000001111100001010101001110011010101110 \r\n" +
"\r\n" +
"001010101000110001011111001010111111100110000011011111101010 \r\n" +
"\r\n" +
"011111100011001110100101001011110011000101011000100111001011 \r\n" +
"\r\n" +
"011010001101011110011011111010111110010100101000110111010110 \r\n" +
"\r\n" +
"001110000111100100101110001011101010001100010111110111011011 \r\n" +
"\r\n" +
"111100001000001100010110101100111001001111100100110000001101 \r\n" +
"\r\n" +
"001110010000000111011110000011000010101000111000000110101101 \r\n" +
"\r\n" +
"100100011101011111001101001010011111110010111101000010000111 \r\n" +
"\r\n" +
"110010100110101100001101111101010011000110101100000110001010 \r\n" +
"\r\n" +
"110101101100001110000100010001001010100010110100100001000011 \r\n" +
"\r\n" +
"100100000100001101010101001101000101101000000101111110001010 \r\n" +
"\r\n" +
"101101011010101000111110110000110100000010011111111100110010 \r\n" +
"\r\n" +
"101111000100000100011000010001011111001010010001010110001010 \r\n" +
"\r\n" +
"001010001110101010000100010011101001010101101101010111100101 \r\n" +
"\r\n" +
"001111110000101100010111111100000100101010000001011101100001 \r\n" +
"\r\n" +
"101011110010000010010110000100001010011111100011011000110010 \r\n" +
"\r\n" +
"011110010100011101100101111101000001011100001011010001110011 \r\n" +
"\r\n" +
"000101000101000010010010110111000010101111001101100110011100 \r\n" +
"\r\n" +
"100011100110011111000110011001111100001110110111001001000111 \r\n" +
"\r\n" +
"111011000110001000110111011001011110010010010110101000011111 \r\n" +
"\r\n" +
"011110011110110110011011001011010000100100101010110000010011 \r\n" +
"\r\n" +
"010011110011100101010101111010001001001111101111101110011101";
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < str.length();i ++) {
if(str.substring(i,i+1).equals("\r") || str.substring(i,i+1).equals("\n")||str.substring(i,i+1).equals(" ")) {
continue;
}
sb.append(str.substring(i,i+1));
}
int index = 0;
for(int i = 0 ; i < 30;i++) {
for(int j = 0;j < 60;j++) {
arr[i][j] = (sb.charAt(index) - '0');
index++;
}
}
return arr;
}
private static int dfs(int[][] map,int x,int y) {
int count = 1;//默认是1，这样递归时才会加
if(x < 0 || y < 0 || x >= 30 || y >= 60 || map[x][y]!= 1) {
return 0;
}
map[x][y] = 2;//设置为2，防止出现重复找到某点的情况
count += dfs(map, x, y + 1) + dfs(map,x + 1,y) + dfs(map , x, y - 1) + dfs(map, x - 1,y);
return count;
}
}
==算法是解决问题的工具，各有优劣；同一个问题可以使用不同的算法来解决。算法竞赛本身难度较大，需要长期的练习，尽可能的熟悉各种不同的算法与题型。需要恒心和毅力==
图为当前codeforces积分排名第一的选手。
资源推荐
Leetcode（力扣） 世界知名的学习社区，算法题量广，用户基数大，社区氛围好，资源内容较完善，使用友好界面简洁。
代码随想录 包含了完整的算法学习路线，题目从易较难设置较合理，题目讲解细致。有全套的B站视频讲解，对于初学者十分友好。
洛谷 国内知名刷题网站，题库大，定期举行比赛。
ACM/LeetCode算法竞赛路线图，最全的算法学习地图！ 使用树的形式，整理了大量算法题。
算法竞赛模板库 by 灵茶山艾府 LeetCode竞赛前10选手做的竞赛算法目录，b站有对应的讲解。
说些什么吧！