赞
踩
有参加蓝桥杯的同学可以给博主点个关注,博主也在准备蓝桥杯,可以跟着博主的博客一起刷题。
按照题目给的操作,用代码依次描述出来即可。
模拟一般都是一些很基础的题目,但不要小看模拟,看似简单的操作,可能会有你想不到的情况。
模拟需谨慎!一定要把所有情况都考虑到。
枚举+模拟
大多数日期问题都可以通过模拟来解决。
本题就是在某一个范围内判断日期是否是回文字符串。
枚举年份的回文数,然后判断月份和日期合不合法就好了。
① 只枚举前四位数
② 判断是否在范围内
③ 再判断后四位数是否合法
时间复杂度
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; } }
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); } }
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)); // 曼哈顿距离公式 } }
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; } }
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; } }
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; } } }
有对代码不理解的地方可以在下方评论
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。