蓝桥杯是国内著名的计算机比赛，每年吸引了数以万计的学生参加。在比赛中，参赛者需要通过多个难度级别的编程题目，展现他们的算法与编程能力。随着蓝桥杯比赛的不断升温，题目难度和复杂度也在不断提高。因此，对于参赛者来说，熟悉和掌握蓝桥杯题目解法是至关重要的。
在本文中，今天给大家带来四种省赛真题题型，都是很常考的题型，可以多加练习。
动态规划
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int m = s.nextInt();
int [] [] map = new int[n][m];
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < m ; j ++){
map[i][j] = s.nextInt();
}
}
//dp[i][j]：走到i , j位置的最大奖励
int [][] dp = new int[n][m];
//相比传统的dp，增加范围限制。
int [] dx = {-1,-2,-3,0, 0, 0,-1 ,-2, -1};
int [] dy = {0, 0 ,0 ,-1,-2,-3,-2,-1,-1};
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < m ; j ++){
int max = Integer.MIN_VALUE ;
for(int k = 0 ; k < dx.length ; k ++) {
//如果在范围内,找到这个范围能到i，j的最大值
if (i + dx[k] >= 0 && j + dy[k] >= 0) {
max = Math.max(max, dp[i + dx[k]][j + dy[k]]);
}
}
if(i == 0 && j == 0) dp[i][j] = map[0][0]; else dp[i][j] = max + map[i][j];
}
}
System.out.println(dp[n - 1][m - 1]);
}
}
BFS
public class Main {
static int N;
static String target = "ABCDE*";
static Deque <String> q ;
static int step;
static Set<String> visited;
static List<Integer> ans = new ArrayList<>();
static int neighbor [][] = new int [][] {
{1, 3},
{0 , 2, 4},
{1 , 5},
{0 , 4},
{1 , 3, 5},
{2 , 4}
};
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
N = s.nextInt();
List<String> list = new ArrayList<>();
for(int i = 0 ; i < N ; i ++){
list.add(s.next());
}
for(int i = 0 ; i < N ; i ++ ){
step = 0;
q = new LinkedList<>();
visited = new HashSet<>();
String str = list.get(i);
q.offer(str);
visited.add(str);
// System.out.println(bfs(str));
ans.add(bfs(str));
}
for(int i = 0 ; i < ans.size() ; i ++){
System.out.println(ans.get(i) == 0 ? 0 : 1);
}
}
static int bfs(String str){
if(target.equals(str)){
return 1;
}
while(!q.isEmpty()){
int sz = q.size();
for(int i = 0 ; i < sz ; i ++){
String cur = q.poll();
if("ABCDE*".equals(cur)){
return step;
}
//找到*的位置
int idx ;
for(idx = 0 ; cur.charAt(idx) != '*' ; idx ++);
//和附近的字符进行交换
for(int k = 0 ; k < neighbor[idx].length ; k ++){
String new_str = swap(neighbor[idx][k] , idx , cur);
if(!visited.contains(new_str)){
q.offer(new_str);
visited.add(new_str);
}
}
}
step++;
}
return 0;
}
static String swap(int i , int j , String cur){
char [] ch = cur.toCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return new String(ch);
}
}
DFS
DFS：访问完当前节点，首先访问当前节点的第一个邻接节点。
DFS步骤：
- 访问初始节点v，并标记已访问。
- 查找邻接节点w。
- 如果w存在，则执行4 。如果w不存在，继续执行v的下一个节点。
- 如果w未被访问，对w进行DFS（把w当作另一个v，继续进行步骤123）
- 查找节点v的w邻接节点的下一个邻接节点，转到3。
-
使用dfs算法，要明确dfs算法的作用。本质有些类似于回溯算法。
public class Demo {
static int N , M , K , T;
static int [] time , maxTime , visited , owns , minTime;
static int [] [] path;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
N = s.nextInt(); //作物种类
M = s.nextInt(); //初始拥有的作物类型数量
K = s.nextInt(); //杂交方案
T = s.nextInt(); //目标作物编号
minTime = new int [N + 1]; // 保存dfs返回值，每种作物的最小时间
time = new int [N + 1]; //每种作物种植时间
visited = new int [N + 1]; //判断作物是否已经合成
owns = new int [M]; //拥有的种子类型
maxTime = new int [K]; //杂交出的作物最大时间
path = new int [K][3]; //使用拥有的方案来进行杂交的杂交路径。
for(int i = 1 ; i <= N ; i ++){
time[i] = s.nextInt();
}
for(int i = 0 ; i < M ; i ++){
owns[i] = s.nextInt();
visited[owns[i]] = 1;
}
for(int i = 0 ; i < K ; i ++){
path[i][0] = s.nextInt();
path[i][1] = s.nextInt();
path[i][2] = s.nextInt();
//杂交方案的最大时间。
maxTime[i] = Math.max(time[path[i][0]] , time[path[i][1]]);
}
System.out.println(dfs(T));
}
//dfs的定义：返回杂交得到tar的最小时间。
static int dfs(int tar){
if(visited[tar] == 0){
int min = Integer.MAX_VALUE;
//遍历每一种杂交方案
for(int i = 0 ; i < K ; i ++){
//找到了要合成的种子
if(path[i][2] == tar){
//杂交方案的时间 + 当前情况方案的最大时间。
min = Math.min(min ,
(maxTime[i] + Math.max(dfs(path[i][0]) , dfs(path[i][1]) )));
}
}
visited[tar] = 1;
minTime[tar] = min;
return min;
}else{
return minTime[tar];
}
}
}
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int N;
static char [][] land;
static boolean[][] visited; //记录该点是否访问过
static int count; //消亡陆地数
static int sum; //sum = 1，说明四周都是
static int[][] path = new int[][]{
{0, 1},
{1, 0},
{-1, 0},
{0, -1}
};
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
N = s.nextInt();
land = new char[N][N];
for (int i = 0; i < N; i++) {
land[i] = s.next().toCharArray();
}
visited = new boolean[N][N];
for (int i = 0; i < land.length; i++) {
for (int j = 0; j < land[0].length; j++) {
//1. 访问初始节点。
if (land[i][j] =='#' && !visited[i][j]) {
//重置参数
sum = 0;
dfs(i, j);
//sum = 0，表明已经消亡
if (sum == 0) {
count++;
}
}
}
}
System.out.println(count);
}
static void dfs(int i, int j) {
//标记初始节点已经访问。
visited[i][j] = true;
//四周都是陆地
if (alive(i, j)) {
sum = 1;
}
//查找邻接节点
for (int k = 0; k < path.length; k++) {
//获得邻接节点的下标
int dx = i + path[k][0];
int dy = j + path[k][1];
//陆地四周除了陆地就是海洋，不用判断越界问题。
// if(dx >= 0 && dx < N && dy >=0 && dy < N) {
//邻接节点w
char w = land[dx][dy];
//判断邻接节点是否存在
if (w == '#') {
//如果邻接节点未被访问
if (!visited[dx][dy]) {
dfs(dx, dy);
}
}
// }
}
}
//判断四周是否都是陆地
static boolean alive(int i, int j) {
for (int k = 0; k < path.length; k++) {
int dx = i + path[k][0];
int dy = j + path[k][1];
//同样，这里无需考虑dx,dy是否越界
if (land[dx][dy] == '.') {
return false;
}
}
return true;
}
}
暴力
public class Main {
static int N , K;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
N = s.nextInt(); // 巧克力个数
K = s.nextInt(); // 孩子数
int [][] arr = new int [N][2];
for(int i = 0 ; i < N ; i++){
arr[i][0] = s.nextInt();
arr[i][1] = s.nextInt();
}
boolean flag = true;
int len = 1; //切的长度
long temp = 1; //巧克力数量
while(flag){
int i;
for( i = 0 ; i < N ; i ++){
temp += (long) (arr[i][0] / len) * (arr[i][1] / len); //计算可以切出的块数
if(temp >= K){
break;
}
}
//都切完了但是还不够分，退出循环
if(i == N && temp < K){
flag = false;
}else{
//继续增加变长
len ++;
temp = 0;
}
}
System.out.println(len - 1);
}
}