有参加蓝桥杯的同学可以给博主点个关注，博主也在准备蓝桥杯，可以跟着博主的博客一起刷题。
蓝桥杯
数学
蓝桥杯中的数学更像是脑筋急转弯，它基本不会考察系统的数学知识，但是会考察一些数学模型。
AcWing今天的日历也是很符合本文的内容😂
第四届2013年蓝桥杯真题
AcWing 1205. 买不到的数目
C++A组第8题
JavaC组第9题
给两个包装糖果的数量，求出最大不能买到的糖数
特别经典的题，小学奥数，NOIP，算法进阶指南都有这样的题。
了解过这个题的都应该知道这道题有一个数学公式，但咱们首先抽象一下这个问题：
两个数n和m，通过加法xn + ym，x和y都大于等于0的整数，由这样一个组合不能凑出来的最大的数是多少，假设我们不知道公式，我们尽力分析一下，是不是一定有解呢，d为n和m的最大公约数，当d大于1的时候，所有不是d的倍数一定凑不出来，比方6和2，它们都是2的倍数，不管6和2怎么拼凑那一定是2的倍数，因此只要一个数不是2的倍数它就一定凑不出来，所以并不是所有的组合都一定有解，只要gcd(n, m) > 1就一定无解，但是本题保证数据一定有解，所以我们不需要考虑这种情况；
在考试的时候实在没法分析的时候，我们可以打表找规律，在我们上面分析的时候，已经分析出了无解的情况，那如果n和m互质，即gcd(n, m) = 1，是否一定有解呢？有一定的数学知识基础其实很容易发现只要n和m互质的话一定能凑出来一个最大的数，这里有一个定理：
裴蜀定理
若 a , b a,b a,b 是整数,且 g c d ( a , b ) = d gcd(a,b)=d gcd(a,b)=d，那么对于任意的整数 x , y x,y x,y， a x + b y ax+by ax+by 都一定是 d d d 的倍数，特别地，一定存在整数 x , y x,y x,y，使 a x + b y = d ax+by=d ax+by=d 成立。——引自百度百科
从直觉上讲，只要n和m互质就一定有解。
暴力枚举（超时）
时间复杂度
O
(
N
)
O(N)
O(N)
AcWingTLE，只过了5/10个数据，蓝桥杯只过了1/3个数据，满分100只拿到了33分
我们枚举一个较大的数，超过这个数的所有数一定可以凑出来，dfs暴搜一下所有答案：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int res = 0;
for (int i = 1; i <= 1000; i++) { // 假设超过1000的数一定可以凑出来
if (!dfs(i, n, m)) res = i; // dfs暴搜这个数能不能被凑出来
}
System.out.print(res);
}
private static boolean dfs(int i, int n, int m) {
if (i == 0) return true;
if (i >= n && dfs(i - n, n, m)) return true;
if (i >= m && dfs(i - m, n, m)) return true;
return false;
}
}
我们打表，更换输入输出数据：
输入 输出
3 2 1
3 4 5
3 5 7
3 7 11
3 8 13
n m res
为什么不考虑3 3和3 6呢？因为这两个数不满足互质。
我们可以看出：res = (3 - 1)m - 3
输入 输出
4 3 5
4 5 11
4 7 17
4 9 23
4 11 29
n m res
res = (4 - 1)m - 4
输入 输出
5 2 3
5 3 7
5 4 11
5 6 19
5 7 23
n m res
res = (5 - 1)m - 5
输入 输出
111 394 43229
111 395 43339
111 397 43559
111 398 43669
111 400 43889
res = (111 - 1)m - 111
综上，得出公式由n和m凑不出来的最大数为： r e s = ( n ? 1 ) m ? n res = (n - 1)m - n res=(n?1)m?n
公式跟y总讲的有一点区别，但也是衍变过来的，我觉得这个公式更好理解一点。
y总的公式：res = (n - 1)(m - 1) - 1。
打表找规律（AC）
时间复杂度
O
(
1
)
O(1)
O(1)
AcWingAC，蓝桥杯满分
直接输出公式
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
System.out.print((n - 1) * m - n);
}
}
数学公式（AC）
时间复杂度
O
(
N
)
O(N)
O(N)
AcWingAC，蓝桥杯满分
最小公倍数减去这两个数
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int lcm = 0;
int max = (n > m)? n : m;
for(int i = max; i <= n * m; i++) {
if((i % n == 0)&&(i % m == 0)) {
lcm = i;
break;
}
}
System.out.print(lcm - n - m);
}
}
在考试中，如果我们一开始不知道这个公式的话，就只能先暴力，然后再由暴力试试能不能打表找出来本题的规律。
第五届2014年蓝桥杯真题
AcWing 1211. 蚂蚁感冒
C++A/B组第7/8题
脑筋急转弯
第一个问题，是否所有蚂蚁都会爬离杆子呢？
我们分析第一个样例：
输入样例1：
3
5 -2 8
只有5是感冒蚂蚁，它们永远都不会碰面，所以输出1。
我们在考虑蚂蚁不能爬离杆子的情况，是因为题中描述：当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行；但是，我们可以看成两个蚂蚁没有调头，互相穿过了对方，因为速度都一样，所以调头与不调头是一样的，碰撞改变方向就是蛊惑人的，关键看出来这点就简单了。
最关键的性质：调头等价于穿过
第二个问题，如何求被感染的个数？
我们在感冒蚂蚁上画一个分界线，分析出所有右边向左走的蚂蚁都会被感染，右边所有向右走的一定不会被感染；左边向左走的一定不会被感染，左边向右走的要分两种情况讨论一下，如果右边有蚂蚁向左走，那么左边向右走的蚂蚁都会感冒；如果右边没有向左走的蚂蚁，那么左边向右走的蚂蚁就不会被感染。
总结
第一个蚂蚁向右走的情况：
右边向左走，必然被感染
右边向右走，必然不会被感染
左边向左走，必然不会被感染
左边向右走：
(1) 右边存在向左走，则必然被感染
(2) 右边不存在向左走，则不然不会被感染
但别忘了还有第一个蚂蚁向左走的情况。
import java.util.Scanner;
public class Main {
static final int N = 55;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] x = new int[N];
for (int i = 0; i < n; i++) x[i] = sc.nextInt();
int left = 0, right = 0; // 分别表示左边向右走的蚂蚁数量，和右边向左走的蚂蚁数量
for (int i = 1; i < n; i++) {
if (Math.abs(x[i]) < Math.abs(x[0]) && x[i] > 0) left++;
else if (Math.abs(x[i]) > Math.abs(x[0]) && x[i] < 0) right++;
}
if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) System.out.print(1);
else System.out.print(left + right + 1);
}
}
第六届2015年蓝桥杯真题
AcWing 1216. 饮料换购
JavaB组第8题
经典小学题目，大家肯定见过这道题😂
我们分析一下样例：
用代码简单模拟：
int res = n; // n为最开始的瓶数
while (n >= 3) { // 此时n为瓶盖的个数
瓶 = n / 3
盖 = n % 3
res += n / 3
n = n / 3 + n % 3
}
sout(res);
完整代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int res = n; // n为最开始的瓶数
while (n >= 3) { // 此时n为瓶盖的个数
res += n / 3;
n = n / 3 + n % 3;
}
System.out.print(res);
}
}
用队列实现
逢3插1
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
q.offer(i); // 不管什么数直接存进去 我们需要的只是队列的size
}
int ans = n; // n为最开始的瓶盖数
while (!q.isEmpty()) {
if (q.size() < 3) break;
for (int i = 1; i <= 3; i++) { // 凑满三个瓶盖 pop队首三个元素
q.poll();
}
q.offer(1); // 凑满的三个瓶盖可以换一瓶
ans++; // 喝的瓶数+1
}
System.out.println(ans);
}
}
队列文章可以参考我之前写的这篇：数据结构学习笔记 1-2队列概述及LeetCode真题图解（Java)
有对代码不理解的地方可以在下方评论