有参加蓝桥杯的同学可以给博主点个关注，博主也在准备蓝桥杯，可以跟着博主的博客一起刷题。
蓝桥杯
模拟
按照题目给的操作，用代码依次描述出来即可。
模拟一般都是一些很基础的题目，但不要小看模拟，看似简单的操作，可能会有你想不到的情况。
模拟需谨慎！一定要把所有情况都考虑到。
例题
AcWing 466. 回文日期
枚举+模拟
大多数日期问题都可以通过模拟来解决。
本题就是在某一个范围内判断日期是否是回文字符串。
枚举年份的回文数，然后判断月份和日期合不合法就好了。
① 只枚举前四位数
② 判断是否在范围内
③ 再判断后四位数是否合法
时间复杂度
O
(
1
0
4
)
O(10^4)
O(104) 一共枚举
1
0
4
10^4
104个数，判断每个数是否合法的计算量是常数级别的，因此总计算量是
O
(
1
0
4
)
O(10^4)
O(104)
import java.util.Scanner;
public class Main {
static int[] days = new int[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 平年每个月的天数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int date1 = sc.nextInt();
int date2 = sc.nextInt();
int res = 0;
for (int i = 1000; i < 10000; i++) {
int date = i, x = i; // data和x存的是前四位
for (int j = 0; j < 4; j++) { // 将data翻转后放在data后面
date = date * 10 + x % 10;
x /= 10;
}
// 此时已经把年份的回文串模拟好了 接下来只要满足该日期是否在范围内 以及判断月份和日期是否合法
if (date1 <= date && date <= date2 && check_valid(date)) res++;
}
System.out.println(res);
}
private static boolean check_valid(int date) {
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if (month == 0 || month > 12) return false;
// 判断平年
if (day == 0 || month != 2 && day > days[month]) return false;
// 判断闰年
if (month == 2) {
int leap = 0; // 0表示平年 1表示闰年
if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) leap = 1;
if (day > 28 + leap) return false;
}
return true;
}
}
第四届2013年蓝桥杯真题
AcWing 1204. 错误票据
JavaA/B组第7题
本题需要处理的是输入，它只给我们行数，并没有给我们每行的元素是多少，我们不能只用Scanner类来进行读入，可以用BufferedReader进行读入，当读入数据较多时也可以用这个类来优化读入，具体看代码。
模拟
时间复杂度
O
(
N
)
O(N)
O(N)
开一个布尔数组st[]记录数字是否出现过，如果出现过标记为true；遍历时如果该数的状态已经被标记为true了，说明该数是重号；我们可以在第一次遍历时找到最大值和最小值，如果从小到大遍历时该数的状态为false，说明该数是断号。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100010;
static boolean[] st = new boolean[N]; // 标记状态 默认为false
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int res1 = 0; // 断号
int res2 = 0; // 重号
while (n-- > 0) {
String[] nums = in.readLine().split(" ");
for(int i = 0; i < nums.length; i++) {
int t = Integer.parseInt(nums[i]);
max = Math.max(max, t); // 找到最大值
min = Math.min(min, t); // 找到最小值
if (st[t]) res2 = t; // 如果之前有值为true 则找到重号
st[t] = true;
}
}
for (int i = min ; i <= max ; i ++) {
if (!st[i]) res1 = i; // 如果状态为false 则找到断号
}
System.out.println(res1 + " " + res2);
}
}
排序
时间复杂度
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)
将所有编号进行排序，根据数组的下标即可判断重号元素和断号元素。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static final int N = 100010;
static int[] a = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
int index = 0;
while (n-- > 0) {
String[] nums = in.readLine().split(" ");
for (int i = 0; i < nums.length; i++) {
a[index++] = Integer.parseInt(nums[i]);
}
}
Arrays.sort(a, 0, index);
int res1 = 0; // 断号
int res2 = 0; // 重号
for(int i = 1; i < index; i++) {
if (a[i] == a[i - 1]) res2 = a[i]; // 重号
else if (a[i] == a[i - 1] + 2) res1 = a[i] - 1; // 断号
}
System.out.println(res1 + " " + res2);
}
}
第六届2015年蓝桥杯真题
AcWing 1219. 移动距离
JavaA/C组第8题
曼哈顿距离
d
(
i
,
j
)
=
∣
x
i
?
x
j
∣
+
∣
y
i
?
y
j
∣
d(i,j)=|x_{i}-x_{j}|+|y_{i}-y_{j}|
d(i,j)=∣xi??xj?∣+∣yi??yj?∣
矩阵中的数字是蛇形排列，难点是求出数字的坐标，我们可以借鉴二维数组，将矩阵中的所有数-1，便于求我们的行号：
原来1的坐标是(1, 1)，现在是(0, 1)，1的行号：1 / 6 = 0，设这个两数为n和m，w是行的宽度，行号 ：n / w, m / w
列号怎么求呢？我们看一下排序正常的二维数组：
列号：n % w, m % w
但题目是蛇形排列的，也就是所有的奇数行我们应该把坐标翻转一下，这里特判一下就可以。
模拟
时间复杂度
O
(
1
)
O(1)
O(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int w = sc.nextInt();
int m = sc.nextInt() - 1;
int n = sc.nextInt() - 1; // 起始位置从0开始 便于计算行列坐标
int x1 = m / w, x2 = n / w; // 行号
int y1 = m % w, y2 = n % w; // 列号
if (x1 % 2 != 0) y1 = w - 1 - y1; // 对奇数列进行特判 翻转y坐标
if (x2 % 2 != 0) y2 = w - 1 - y2;
System.out.print(Math.abs(x1 - x2) + Math.abs(y1 - y2)); // 曼哈顿距离公式
}
}
第八届2017年蓝桥杯真题
AcWing 1229. 日期问题
JavaB组第7题
枚举+模拟
我们枚举 19600101~20591231 之间的所有数：① 判断是否合法 ② 判断是否可能是给定的表示
import java.util.Scanner;
public class Main {
static int[] days = new int[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 平年每个月的天数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
String[] data = str.split("/");
int a = Integer.parseInt(data[0]);
int b = Integer.parseInt(data[1]);
int c = Integer.parseInt(data[2]);
for (int date = 19600101; date <= 20591231; date++) {
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if (check_valid(year, month, day)) {
if (year % 100 == a && month == b && day == c || // 年/月/日
month == a && day == b && year % 100 == c || // 月/日/年
day == a && month == b && year % 100 == c) { // 日/月/年
System.out.printf("%d-%02d-%02d\n", year, month, day); // 格式化输出 记得加上'-'
}
}
}
}
private static boolean check_valid(int year, int month, int day) {
if (month == 0 || month > 12) return false;
if (day == 0 || month != 2 && day > days[month]) return false;
if (month == 2) {
int leap = 0;
if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) leap = 1;
if (day > 28 + leap) return false;
}
return true;
}
}
第九届2018年蓝桥杯真题
AcWing 1231. 航班时间
JavaA组第6题
从北京飞到中东，我们不知道与中东的时差，但我们先整理飞行时间的公式：首先，飞机从北京飞到中东，降落时间减去起飞时间还需要加上时差：end1 - start1 + time，飞机从中东飞回北京，降落时间减去起飞时间还需要减去时差：end2 - start2 - time，我们求的是飞机一趟的飞行时间，因为飞机来回的飞行时间相同，我们可以将来回的飞行时间相加：得到end1 - start1 + end2 - start2，我们发现时差time被抵消掉了，所以本题跟时差没有关系，飞机的飞行时间：
t
=
(
e
n
d
1
?
s
t
a
r
t
1
+
e
n
d
2
?
s
t
a
r
t
2
)
/
2
t = (end1 - start1 + end2 - start2) / 2
t=(end1?start1+end2?start2)/2
公式我们已经推出，接下来要处理的就是字符串的输入输出问题了。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] input = in.readLine().split(" ");
int n = Integer.parseInt(input[0]);
while (n-- > 0) {
int time = (get_time() + get_time()) / 2;
int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
System.out.printf("%02d:%02d:%02d\n", hour, minute, second);
}
}
private static int get_time() throws IOException {
String[] line = in.readLine().split(":| "); // 分隔:和空格
int d = 0;
if (line.length == 7) d = line[6].charAt(2) - '0'; // 如果长度为7说明字符串后面有(+n) 记得转为int
int h1 = Integer.parseInt(line[0]);
int m1 = Integer.parseInt(line[1]);
int s1 = Integer.parseInt(line[2]);
int h2 = Integer.parseInt(line[3]);
int m2 = Integer.parseInt(line[4]);
int s2 = Integer.parseInt(line[5]);
return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
}
// 将所有时间转化成距离当天00:00:00的秒数
private static int get_seconds(int h, int m, int s) {
return h * 3600 + m * 60 + s;
}
}
第十届2019年蓝桥杯真题
AcWing 1241. 外卖店优先级
JavaB组第7题
分析第一个样例：
最终在6时刻时，只有外卖2在优先缓存中，答案输出1。
暴力枚举（内存超限）
时间复杂度
O
(
N
2
)
O(N^2)
O(N2)
枚举每一个时刻的外卖订单
AcWingMLE，10个数据过了7个，蓝桥杯满分100分拿到了90分，最后一个数据内存超限，但也是很可观的分数了。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), t = sc.nextInt();
// 数组定义在全局变量 节省内存
int[][] a = new int[t + 1][n + 1]; // 订单 i为时刻 j为外卖编号
int[] p = new int[n + 1]; // 优先级
for (int i = 0; i < m; i++) a[sc.nextInt()][sc.nextInt()]++;
for (int i = 1; i < t + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (a[i][j] > 0) {
a[i][j] = a[i - 1][j] + a[i][j] * 2; // 加上此订单的优先级
if (a[i][j] > 5)
p[j] = 1; // 将此时刻的外卖置入优先级
} else {
if (a[i - 1][j] > 0) {
a[i][j] = a[i - 1][j] - 1;
if (a[i][j] <= 3)
p[j] = 0;
}
}
}
}
int res = 0;
for (int i = 0; i < p.length; i++) res += p[i];
System.out.println(res);
}
}
优化
我们每个外卖获取到订单的时刻都是离散的，中间可能过了好久才有第二个订单，其实可以把中间这一部分压缩掉，把连续的没有订单的这一段时间统一到下一次有订单的时刻来处理，或者是放在T时刻来处理：
这样做的好处是我们在去做每一个时刻的时候，只需要考虑有订单的店即可，没有订单的店就可以不用考虑了。
此时我们可以不用枚举时刻，将所有订单按时间顺序排序，每次处理一批相同的订单，只要订单的时间点和店铺id相同，我们就把它看成一个。
score[i]表示第i个店铺当前的优先级
last[i]表示第i个店铺上一次有订单的时刻
st[i]表示第i个店铺当前是否处于优先缓存中
伪代码
处理t时刻前的内容：
这样就可以把中间没有订单的时刻压缩：
score[id] -= t - last[id] - 1; // 假如第3和第6时刻都有订单 没卖东西的时间应该是4和5 所以需要减一 6-3-1=2
还要加两个判断：
if (score[id] < 0) score[id] = 0;
if (score[id] <= 3) st[id] = false; // 移出优先缓存
更新一下last：last[id] = t
处理t时刻的内容：
score[id] += cnt * 2; // 加上优先级
if (score[id] > 5) st[id] = true; // 置于优先缓存
每一个店铺最后一段时间可能都没有订单，我们还要算一下最后一段时间，last[id] ~ T之间有多长时间没有卖东西：
for (int i = 1; i <= n; i++) {
if (last[i] < T) {
score[i] -= T - last[i]; // 此时不用-1，因为T时刻没有订单
if (score[i] <= 3) st[i] = false;
}
}
求得结果：
int res = 0;
for (int i = 1; i <= n; i++) {
if (st[i]) res++;
}
sout(res);
完整代码
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static final int N = 100010;
static int[] score = new int[N]; // 店铺的优先级
static int[] last = new int[N]; // 上一次有订单的时刻
static boolean[] st = new boolean[N]; // 表示店铺是否处于优先缓存中
static PII[] order = new PII[N]; // 订单
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), T = sc.nextInt();
for (int i = 0; i < m; i++) order[i] = new PII(sc.nextInt(), sc.nextInt());
Arrays.sort(order, 0, m);
for (int i = 0; i < m;) { // 循环为了找到相同订单
int j = i;
while (j < m && order[j].ts == order[i].ts && order[j].id == order[i].id) j++;
int t = order[i].ts, id = order[i].id;
int cnt = j - i; // 同批订单的数量
i = j;
// 处理t时刻之前的信息
score[id] -= t - last[id] - 1; // 中间没有订单的数量
if (score[id] < 0) score[id] = 0;
if (score[id] <= 3) st[id] = false; // 移出优先缓存
// 处理t时刻的信息
score[id] += cnt * 2; // 加上优先级
if (score[id] > 5) st[id] = true; // 置于优先缓存
last[id] = t;
}
for (int i = 1; i <= n; i++) {
if (last[i] < T) {
score[i] -= T - last[i]; // 此时不用-1，因为T时刻没有订单
if (score[i] <= 3) st[i] = false;
}
}
int res = 0;
for (int i = 1; i <= n; i++) if (st[i]) res++;
System.out.println(res);
}
static class PII implements Comparable<PII> {
int ts;
int id;
public PII(int ts, int id) {
this.ts = ts;
this.id = id;
}
@Override
public int compareTo(PII o) {
if(this.ts > o.ts) return 1;
if(this.ts == o.ts) {
if (this.id > o.id) return 1;
return -1;
}
return -1;
}
}
}
有对代码不理解的地方可以在下方评论