蓝桥算法国赛真题总结

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.8k | 阅读时长 ≈ 11

🌸记录蓝桥杯javaB组历届决赛真题解题算法总结与对比

🌸解题方法汇总（java B组决赛）

1 2 3 4 5 6 7 8 9 10
第四届 暴力枚举 暴力枚举 快速排序 BFS、双向BFS、八数码问题、康托展开等 动态规划、模拟 -1 - - - -
第五届 暴力枚举 全排列+剪枝（或者直接暴力但是代码剪枝量很大） 读题、细心、逻辑模拟 康托展开式（不会则直接暴力全排，但是分不高，可能一半都没有而且超时）、阶乘 行列式、矩阵乘法、模拟、扩展欧几里得 -1 - - - -
第六届 脑筋转弯+暴力计算 全排列+判断 自己的方法是“猜”“试出来” 深度优先搜索 -1 -1 - - - -
第七届 画图找出规律后使用递归模拟过程 全排列 代码分析，考你能不能读懂代码 回溯+剪枝 暴力搜索（超时）；DFS+剪枝回溯（60）；动态规划（80）；数据结构（100） -1 - - - -
第八届 直接暴力循环 使用另一个数组进行模拟细胞增殖的过程或者使用深度优先模拟 读代码找规律（看自己的细心程度吧） 直接模拟计算的过程，注意使用数据范围较大的Long，而且需要熟练使用Long、Integer等类的API 博弈问题、深度优先、剪枝，回溯、模拟 -1 - - - -
第九届 海伦公式 全排列、剪枝判断 全排列、回溯 并查集、连通分量、递归 构造树或者递归优化 -1 - - - -
第十届模拟 暴力+熟悉除模运算的实质 暴力或者深搜求子串 暴力（时间长）、找规律分析题，将除模转换成次方 暴力深搜（耗时加分低）、找规律理解最大公约数的含义 并查集、联通分量找环 -1（暴力只能30） - - - -
第十届 暴力 素数筛、记忆化深搜或者dp 找规律 素因子分解、找规律 深搜+判重 dp+贪心 暴力或者dp -1（找规律） 线段树、主席树、树状数组 -1

🌸康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

通俗简介：

康托展开可以求解一个排列的序号，比如：12345 序号为 1 ，12354序号为2，按字典序增加编号递增，依次类推。
康托逆展开可以求解一个序号它对应的排列是什么。

先给出康托展开的公式：

$X = a_n(n - 1)!+ a_{n-1}(n-2)!+….+a_1\cdot0!$

先对这个公式里变量进行解释，大家不理解这个公式没关系，慢慢往后看，很简单的。
img 的意思是从右往左数第 i 位这个数是这个数前未出现的数，第img 大。举个例子就明白这个公式了：

注意：计算的时候 12345 序列应视为第0个序列，后面会解释为什么。

1
2
3
4
5
6
7
8
9
10
百度百科的例子
在（1,2,3，4，5）5个数的排列组合中，计算 34152的康托展开值。
首位是3，则小于3的数有两个，为1和2，，则首位小于3的所有排列组合为
第二位是4，由于第一位小于4，1、2、3中一定会有1个充当第一位，所以排在4之下的只剩2个，所以其实计算的是在第二位之后小于4的个数。因此。
第三位是1，则在其之后小于1的数有0个，所以。
第四位是5，则在其之后小于5的数有1个，为2，所以。
最后一位就不用计算啦，因为在它之后已经没有数了，所以固定为0
根据公式：
X = 2 x 4! + 2 x 3! + 0 x 2! + 1 x 1! + 0 x 0！
　　所以比34152小的组合有61个，即34152是排第62。

拿52413举例子：

1、首先看第一个数 5，不管第一位是什么数，后面都有四位数，那么这四位数全排列的方式有 4！种，而如果第一位是 1 或 2 或 3 或 4 都会比5开头的字典序要小，所以可以令1，2，3，4分别作为开头，这样的话就会有 4 * 4！种排法要比 52413这种排法的字典序要小。

那么第一个数是1，2，3，4时候的字典序的个数数完了是 4 * 4！ 种，且这些字典序都要比52413的字典序要小。

还有其他的排列方式比52413的字典序要小的吗？

2、那么就可以固定第一位5，找下一位2，这时5已经用过了，所以从剩下的 1，2，3，4 里挑选比2小的数，一共1个，后面还剩三位，也就是3！种排列方式，那么这时候比 52413 字典序要小的又有 1 * 3！种，也就是当5在第一位，1在第二位的时候。

3、再看第三位4，这时5，2都用了，所以从剩下的 1，3，4三个数中找比4小的数的个数，有两个比4小原理同上，所以这时候也可以有 2 * 2!种排列方式的字典序小于 52413

4、再看第四位1，这时候会有 0 * 1！种

5、再看第五位3，这时候会有0 * 0！种

综上所述：
对于序列： 52413 该序列展开后为： 4 * 4! + 1 * 3! + 2 * 2! + 0 * 1! + 0 * 0! ，计算结果是： 106
由于是从0开始计数的，所以最后 52413 的编号为 107

为什么从0开始计数？
可以这样看：我现在让你求12345的康托展开值，也就是：04！+ 03！+ 02！+ 01！+0*0！ = 0 所以明白了吧~~
康托公式最小字典序的编号就是0。

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
36
37
38
39
40
41
/***** 这里以字符串进行展示  字符串可泛化性好 ******/
 
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
/*******打出1-n的阶乘表*******/
int f[20];
void jie_cheng(int n)
{
    f[0] = f[1] = 1; // 0的阶乘为1
    for(int i = 2; i <= n; i++) f[i] = f[i - 1] * i;
}
 
/**************康托展开****************/
string str;
int kangtuo()
{
    int ans = 1;  //注意，因为 12345 是算作0开始计算的，最后结果要把12345看作是第一个
    int len = str.length();
    for(int i = 0; i < len; i++){
        int tmp = 0;//用来计数的
 
        for(int j = i + 1; j < len; j++){
            if(str[i] > str[j]) tmp++;
            //计算str[i]是第几大的数，或者说计算有几个比他小的数
        }
 
        ans += tmp * f[len - i - 1];
    }
    return ans;
}
 
int main()
{
    jie_cheng(10);
    string str = "52413";
    cout<<kangtuo()<<endl;
}

🌸康托逆展开

直接开栗子：

如果初始序列是12345（第一个），让你求第107个序列是什么。（按字典序递增）

这样计算：

先把107减1，因为康托展开里的初始序列编号为0
然后计算下后缀积：
1 2 3 4 5
5！ 4！ 3！ 2！1！ 0！
120 24 6 2 1 1

106 / 4! = 4 ······ 10 有4个比它小的所以因该是5 从（1，2，3，4，5）里选
10 / 3! = 1 ······ 4 有1个比它小的所以因该是2 从（1， 2， 3， 4）里选
4 / 2! = 2 ······ 0 有2个比它小的所以因该是4 从（1， 3， 4）里选
0 / 1! = 0 ······ 0 有0个比它小的所以因该是1 从（1，3）里选
0 / 0! = 0 ······ 0 有0个比它小的所以因该是3 从（3）里选

所以编号107的是 52413

康托逆展开代码：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/***** 这里以字符串进行展示  字符串可泛化性好 ******/
 
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
/*******打出1-n的阶乘表*******/
int f[20];
int x, num;
 
void jie_cheng(int n)
{
    f[0] = f[1] = 1; // 0的阶乘为1
    for(int i = 2; i <= n; i++) f[i] = f[i - 1] * i;
}
 
/**************康托逆展开**************/
 
vector<char> vec; //存需要排列的字符
void rev_kangtuo(int k) //输出序号为 k 的字符序列
{
    int n = vec.size(), len = 0;
    string ans = "";
    k--; // 算的时候是按 12345 是第0位
    for(int i = 1; i <= n; i++){
        int t = k / f[n - i]; // 第 i 位需要 第 t + 1 大的数
        k %= f[n - i];        //剩下的几位需要提供的排列数
        ans += vec[t] ; //  vec[t] 就是第 t + 1 大的数
        vec.erase(vec.begin() + t); 
//用过就删了，不用vector用暴力也可以，就是说枚举，然后一个一个的比较大小，并记录有几个没用过的字符且字典序比它小
    }
    cout << ans << '\n';
}
 
/***************************************/
// 假设展开后不超过10位
int main()
{
    jie_cheng(10); // 预处里好阶乘
    scanf("%d", &x); // 输入需要逆展开的数字
    /************康托逆展开***********/
    for(int i = 1; i <= 10; i++)
    {
    	if(x / f[i] == 0) // 求出 x 逆展开所需的最小的位数，方便下面的初始化
    	{
    		num = i;
    		break;
    	}
    }
    for(int i = 1; i <= num; i++) vec.push_back(i + '0'); //输入的位数只要不小于num就可以
    rev_kangtuo(x);
}

🌸吉姆拉尔森公式

1
2
3
4
5
6
7
8
9
10
11
private static int whatday(int y, int m, int d) {
	if(m == 1) {
		y--;
		m = 13;
	}
	if(m == 2) {
		y--;
		m = 14;
	}
	return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;
}

🌸海伦公式

1
2
3
4
三角形三边长a, b, c
p = (a + b + c) / 2

area = Math.sqrt(p * (p - a) * (p - b) * (p - c))

🌸素数

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * 利用API
 * @param n
 */
private static void n_prime(int n) {
	BigInteger in = new BigInteger("2");
	
	for(int i = 2; i <= n; i++) {
		in = in.nextProbablePrime();
	}
	System.out.println(in);
}
/**
 * 常规方法
 * @param n
 */
private static void n_prime1(int n) {
	List<Long> list = new ArrayList<>();
	
	for(long i = 2; list.size() < n; i++) {
		if(prime(i)) {
			list.add(i);
		}
	}
	System.out.println(list.get(n - 1));
}
private static boolean prime(long n) {
	if(n < 2) {
		return false;
	}
	if(n == 2) {
		return true;
	}
	if(n % 2 == 0) {
		return false;
	}
	for(int i = 3; i * i <= n;i += 2) {
		if(n % i == 0) {
			return false;
		}
	}
	return true;
}
private static void n_prime2(int n) {
	int arr[] = new int[n + 1];
	for(int i = 2; i <= n; i++) {
		arr[i] = 1;
	}
	for(int i = 2; i * i <= n; i++) {//可以只用根号n之前的数字去筛选
		if(arr[i] == 1) { //不加判断也是可以的，增加复杂度了，我们只需要在我们所认为的“素数”中筛选就可以了， 每个合数必有质因子
			for(int j = i * i; j <= n; j += i) { //比如j = i * k(k < i),那么j肯定被k筛掉了
				arr[j] = 0;
			}
		}
	}
	int k = 1;
	for(int i = 2; i <= n; i++) {
		if(arr[i] == 1) {
			if(k == 100002) {
				System.out.println("->"+i);
				return;
			}
			k++;
		}
	}
}

🌸日期类（SimpleDateFormat +Date)

1
2
3
4
5
6
7
8
public static class Main{
    public static void main(){
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd");
        Date date1 = format.parse("1921-7-23");
        Date date2 = format.parse("2020- 7-1");
        int a = (int)((date2.getTime() - date1.getTime()) / 1000 * 60);//相隔多少分钟
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//直接使用 Date
public static class Main{
    public static void main(){
        long sum = 36138 * 24 * 60L;
        System.out.println(sum);
        System.out.println(36138 * 24 * 60);
        // long型变量在定义的时候，如果不加“L”,则默认为int型变量
        Date date1 = new Date(21, 7, 23, 12, 0, 0); // 1921
        Date date2 = new Date(120, 7, 1, 12, 0, 0); // 2020
        long time = date2.getTime() - date1.getTime();
        System.out.println(time / (60000));
    }
}

🍁

🍂

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%