Shuwen's blog

生活 & 学习

0%

蓝桥杯真题解析

发表于 更新于 分类于

一些记录：看视频【蓝桥杯】2013年-2018年蓝桥杯历年省赛真题 Java C++ A组 B组 C组

emmm，参加完校赛，被完虐，，，感觉蓝桥杯的题太简单，，，，接下来换地方去学leetcode一段时间

2013-java-A

视频的总结

image-20210304145315375

1 日历

Calendar API的使用

1
2
3
4
5
6
7
8
Calendar calendar = Calendar.getInstance();//创建实例

//设置年月日
calendar.set(Calendar.YEAR, year);
calendar.set(Calendar.MONTH, 11);//从0开始，11代表12月
calendar.set(Calendar.DAY_OF_MONTH, 31);//从1开始，代表该月第31天

Calendar.DAY_OF_WEEK//代表这天是一周里的星期几

2 从我做起振兴中华

递归的思路，学习

image-20210215133419619

观察可得，走法要么走右，要么走下

1
2
3
4
public static int f(int i,int j) {
	if(i == 4 || j == 3) return 1;//走到，成功
	return f(i+1,j) + f(i,j+1);//下或右
}

3 BigInteger

BigInteger API的使用，主要解决大数问题

1
BigInteger x = BigInteger.valueOf(2).pow(11213).subtract(BigInteger.ONE);//创建

上面的式子等价于：2^11213-1

创建数都要用BigInteger.valueOf(2)创建一个对象，幂次的话，可以直接用数(幂不是大数)

1
String s = x.toString();//可以转字符串

4 颠倒数字

根据题目意思，一步步编程即可

循环，有调转，可以再来一个循环变量j

1
2
3
4
5
6
for (int i = s.length()-1,j=0; i>=0; i--,j++) {
	char c = s.charAt(i);
	if(c=='6')ans[j] = '9';
	else if(c=='9') ans[j]='6';
	else ans[j] = c;
}

5 希尔排序

希尔排序的变种

填空题tip

  1. 将给定的代码复制过来
  2. 将___注释，运行
  3. 自己写main函数
  4. 根据特殊情况验证

6 逆波兰序

没什么说的，，，

7 断号和连号

每行数据长度不等的输入

image-20210218145738807

1
2
3
4
5
6
7
8
9
10
ArrayList<Integer> list = new ArrayList<>();
int N = scan.nextInt();
scan.nextLine();//去掉'\n'
for (int i = 0; i < N; i++) {
String line = scan.nextLine();
String [] split = line.split(" ");
	for (int j = 0; j < split.length; j++) {
		list.add(Integer.parseInt(split[j]));
	}
}

8 全排列

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void f(int[] arr,int k) {//k:确认某一个排列的第k位
		if(k==9) {//全部确认
			check(arr);
			return;
		}
		//选定第k位
		for (int i = k; i < arr.length; i++) {
			//将第i位和第k位交换
			int t = arr[i];
			arr[i] = arr[k];
			arr[k] = t;
			
			//移交下一层去确认k+1位
			f(arr,k+1);
			
			//回溯(换回来)
			t = arr[i];
			arr[i] = arr[k];
			arr[k] = t;
		}	
	}

9 深搜索

dfs，参数根据变化的量来确定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void dfs(int i, int j, int steps, int sum) {
	if (i < 0 || i == n || j < 0 || j == m||vis[i][j] ==1) {
		return;
	}
	if(sum == total /2) {
		ans = Math.min(steps, ans);
		return;
	}
	if(sum > total /2) {
		return;
	}
	vis[i][j]=1;
	dfs(i + 1, j, steps + 1, sum + g[i][j]);
	dfs(i - 1, j, steps + 1, sum + g[i][j]);
	dfs(i, j + 1, steps + 1, sum + g[i][j]);
	dfs(i, j - 1, steps + 1, sum + g[i][j]);
	vis[i][j]=0;
}

10 邻接图 + 深搜索 + 树的直径

树的直径

找到树上距离最大的点方法：

  1. 任意选一点，找到距离最大的点
  2. 用距离最大的点作为一个端点，再找另外一个端点即可。

邻接图

创建
1
private static List<Node>[] g;// 图的领接表
初始化
1
2
3
4
g = new List[n + 1];//list还需要初始化
for (int i = 0; i <= n; i++) {
	g[i] = new ArrayList<Node>();
}
赋值
1
2
3
4
for (int i = 0; i < n - 1; i++) {
	g[a].add(new Node(b, c));
	g[b].add(new Node(a, c));
}
Node
1
2
3
4
5
6
7
8
9
10
static class Node {
	int num;
	long dis;

	public Node(int num, long dis) {
		super();
		this.num = num;
		this.dis = dis;
	}
}

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void dfs(int from, int num, long dis) {
	boolean isLeaf = true;
	List<Node> neighbors = g[num];// 所有的子节点
	for (int i = 0; i < neighbors.size(); i++) {
		Node neighbor = neighbors.get(i);
		if (neighbor.num == from)
			continue;// 如果父亲又变成了儿子不合理，，，故排除
		isLeaf = false;// 只要有邻居，肯定不是叶子节点
		dfs(num, neighbor.num, dis+neighbor.dis);
	}
	// 是叶子节点
	if (isLeaf && dis> max) {
		max = dis;
		pnt = num;
	}
}

2014-java-A

1 根据内容、常识编程

由于年轻女孩，，，可以简单的默认年龄是1-20进行尝试

2 递归，深搜

边界要判定好

1
2
3
4
5
6
7
8
static void dfs(int dian,int hua,int jiu) {
	if(dian ==0 && hua ==0 && jiu == 1) {
		ans++;
		return;
	}
	if(dian > 0) dfs(dian-1,hua,jiu*2);
	if(hua > 0) dfs(dian,hua-1,jiu-1);
}

3 对数字的每一位排序

数字转字符串

1
String.valueOf(src);

对字符串里的每一位排序

1
2
3
4
char [] char1 = s1.toCharArray();
char[] char2 = s2.toCharArray();
Arrays.sort(char1);
Arrays.sort(char2);

判断两字符数组是否相等

1
new String(char1).equals(new String(char2))
1
2
3
4
5
6
7
8
9
static boolean check(int src, int des) {
	String s1 = String.valueOf(src);// 数字转字符串
	String s2 = String.valueOf(des);
	char [] char1 = s1.toCharArray();
	char[] char2 = s2.toCharArray();
	Arrays.sort(char1);
	Arrays.sort(char2);
	return new String(char1).equals(new String(char2));
}

4 一句话123循环

n的变化1 2 3 循环。。。

1
n = n%3+1

注意：static方法必须在static类里面

5 堆排序

emmm，填空题不能单靠简单的上下文，，，，保险起见，要学会自己构造例子看结果。

6 全排列

image-20210304185430180

给每个边和顶点编号。

全排列+然后计算每个编的值

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void f(int k) {
	if(k==arr.length) {
		check();
		return;
	}
	//已经确定k-1个了，所以从k开始
	for(int i=k;i<arr.length;i++) {
		int t = arr[i];
		arr[i] = arr[k];
		arr[k] = t;
		
		f(k+1);
		
		t = arr[i];
		arr[i] = arr[k];
		arr[k] = t;
	}
}

顶点编号+计算边的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void check() {
	int a = 8+arr[0]+arr[1]+arr[2];
	int b = 3+arr[2]+arr[4]+arr[7];
	int c = 11+arr[3]+arr[6];
	int d = 1+arr[1]+arr[4]+arr[8];
	int e = arr[5]+arr[6]+arr[7]+arr[8];
	int f = 1+arr[0]+arr[3]+arr[5];
	
	if(a == b && b==c&& c==d&&d == e&&e==f) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
}

7 概率题

涉及概率论的知识，主要用概率论得出公式，然后用计算机计算计算具体的值。。。

有点点麻烦，吐血

数学归纳法

  1. 只有一个圈，概率为1
  2. 如果n根绳子组成一个圈，那么必定是n-1根绳子组成一个圈然后加入新的绳子
  3. 如果n根绳子组成m个圈，可以是n-1根绳子组成m-1个圈，然后新绳自成一圈；也可以是n-1根绳子组成m个圈，然后最后一个新绳加入这个圈。

这里面加入一个圈的公式是：

f[sheng][1] = f[sheng - 1][1] * (sheng - 1) * 2 / (2 * sheng - 1);

看视频吧，，，，总之需要推演的能力

8 递归 / 循环

都可以用，我使用了递归，老师用的循环（更简单，，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void dfs(int i,int j,int s,int k) {
//		if(vis == 1) {
//			return;
//		}
		if(steps == k ) {
			x = i;
			y = j;
//			vis = 1;
			return;
		}
		
	//11 12 22 21 11	
		if(g[i][j] == 0) {//white
			g[i][j] = 1;
			if(s==1)
				dfs(i,j-1,4,k+1);
			else if(s==2) 
				dfs(i-1,j,s-1,k+1);
			else if(s ==3)
				dfs(i,j+1,s-1,k+1);
			else if(s == 4)
				dfs(i+1,j,s-1,k+1);
		}else if(g[i][j] == 1) {//black
			g[i][j] = 0;
			if(s==1)
				dfs(i,j+1,s+1,k+1);
			else if(s==2) 
				dfs(i+1,j,s+1,k+1);
			else if(s ==3)
				dfs(i,j-1,s+1,k+1);
			else if(s == 4)
				dfs(i-1,j,1,k+1);
		}
		
	}

字符变数字

简化操作

1
2
3
4
5
6
7
8
9
10
11
static int s2i(String s) {
		if (s.equals("U"))
			return 1;
		if (s.equals("R"))
			return 2;
		if (s.equals("D"))
			return 3;
		if (s.equals("L"))
			return 4;
		return 0;
	}

9 斐波那契

  1. mod运算不能交换
  2. 斐波那契数列 比赛中 用迭代形式来做，不要用递归来做

迭代形式

image-20210304212011899

余数的性质

(A+B)%mod = (A%mod + B%mod)%mod

(A*B)%mod = (A%mod * B%mod)%mod

2015-java-A

easy，循环和递归都能做

可以调试着看过程，确保答案正确

1 easy循环/递归 偶数

  1. i&1==0 ==> 偶数
  2. i mod 2 == 0

2 日历

calendar获取时间

1
calendar.getTime()//月份是英文

中文

函数：toLocaleString()

1
2
c.getTime();
c.getTime().toLocaleString();

结果

1
2
Sat Aug 05 10:23:12 CST 2017
2017年8月5日 上午10:23:12

设置calendar的年月日

重点注意month是月份减1。

设置的时候要月份减1，得出结论的时候要月份+1

1
2
3
4
5
6
7
//分别设置
calendar.set(Calendar.YEAR,2014);
calendar.set(Calendar.MONTH, 10);
calendar.set(Calendar.DAY_OF_MONTH, 9);

//一起设置
calendar.set(2014,10,9);

增加天数

  • 方法一：c.add(Calendar.DATE, 1000);
  • 方法二：calendar.add(Calendar.DAY_OF_YEAR, 1000);
Q：如果阅读本文需要付费，你是否愿意为此支付1元？