全网首发! 2023年4月蓝桥杯B组A到G题解析它来啦！
试题 A: 阶乘求和
【问题描述】
令 S = 1! + 2! + 3! + ... + 202320232023!，求 S 的末尾 9 位数字。
提示：答案首位不为 0。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
思路:暴力计算量会超过10^12,考虑阶乘特点,对于i∈[1,202320232023],当i增大时,i中所含的偶因子{2,5,10...}会越来越多,不妨假设当i超过某个数时i!的末九尾全为0,所以打表看一下Si = 1!+2!+.....+i!,当Si的末九位不变时,就得到了答案.
试题 B: 幸运数字
【问题描述】
哈沙德数是指在某个固定的进位制当中，可以被各位数字之和整除的正整数。例如 126 是十进制下的一个哈沙德数，因为 (126)10 mod (1+2+6) = 0；126也是八进制下的哈沙德数，因为 (126)10 = (176)8，(126)10 mod (1 + 7 + 6) = 0；同时 126 也是 16 进制下的哈沙德数，因为 (126)10 = (7e)16，(126)10 mod (7 +e) = 0。小蓝认为，如果一个整数在二进制、八进制、十进制、十六进制下均为哈沙德数，那么这个数字就是幸运数字，第 1 至第 10 个幸运数字的十进制表示为：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。现在他想知道第 2023 个幸运数字是多少？你只需要告诉小蓝这个整数的十进制表示即可。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
思路:简单模拟
试题 C: 数组分割
时间限制: 1.0s
内存限制: 512.0MB
【问题描述】
小蓝有一个长度为 N 的数组 A = [A0, A1, . . . , AN−1]。现在小蓝想要从 A 对应的数组下标所构成的集合 I = {0, 1, 2, . . . , N − 1} 中找出一个子集 R1，那么 R1在 I 中的补集为 R2。记 S 1 = ∑ r∈R1 Ar，S 2 = ∑r∈R2 Ar，我们要求S 1 和 S 2 均为偶数，请问在这种情况下共有多少种不同的R1。当R1 或 R2 为空集时我们将S1 或 S2 视为 0。
【输入格式】
第一行一个整数 T，表示有 T 组数据。接下来输入 T 组数据，每组数据包含两行：第一行一个整数 N，表示数组A 的长度；第二行输入 N 个整数从左至右依次为 A0, A1, . . . , AN−1，相邻元素之间用空格分隔。
【输出格式】
对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你需要将答案对 1000000007 进行取模后输出。
【样例输入】
2
2
6 6
2
1 6
【样例输出】
4
思路:若A中的元素有奇数个奇数,则无存在的划分,反之若存在n个(n%2=0&&n!=0),则划分为组合数Cn0+Cn2+Cn4+...+Cnn = 2^(n-1)+1,若n=0,则划分为Cn1+Cn2+Cn3+...+Cnn = 2^n。
试题 D: 矩形总面积
时间限制: 1.0s
内存限制: 512.0MB
【问题描述】
平面上有个两个矩形 R1 和 R2，它们各边都与坐标轴平行。设 (x1, y1) 和(x2, y2) 依次是 R1 的左下角和右上角坐标，(x3, y3) 和 (x4, y4) 依次是 R2 的左下角和右上角坐标，请你计算 R1 和 R2 的总面积是多少？
注意：如果 R1 和 R2 有重叠区域，重叠区域的面积只计算一次。
【输入格式】
输入只有一行，包含 8 个整数，依次是：x1，y1，x2，y2，x3，y3，x4 和 y4。
【输出格式】
一个整数，代表答案。
【样例输入】
2 1 7 4 5 3 8 6
【样例输出】
22
思路:得出R1四个角的坐标后看看是否存在某个角落在R2的区域,减去重叠区域的面积。
时间开销O(1)
试题 E: 蜗牛
时间限制: 1.0s
内存限制: 512.0MB
【问题描述】
这天，一只蜗牛来到了二维坐标系的原点。在 x 轴上长有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0，横坐标分别为 x1, x2, ..., xn。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第n 个竹竿的底部也就是坐标 (xn, 0)。它只能在 x 轴上或者竹竿上爬行，在 x 轴上爬行速度为 1 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。为了快速到达目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之间建立了传送门（0 < i < n），如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai)，就可以瞬间到达第 i + 1 根竹竿的高度为 bi+1 的位置 (xi+1, bi+1)，请计算蜗牛最少需要多少秒才能到达目的地。
【输入格式】
输入共 1 + n 行，第一行为一个正整数 n；
第二行为 n 个正整数 x1, x2, . . . , xn；
后面 n − 1 行，每行两个正整数 ai , bi+1。
【输出格式】
输出共一行，一个浮点数表示答案（四舍五入保留两位小数）。
【样例输入】
3
1 10 11
1 1
2 1
思路:dp,设有dp[i][0],dp[i][1]表示到达第i根杆子底部和第i根杆子的传送点的最优解,则有状态转移方程dp[i][0] = min(dp[i-1][0],dp[i-1][1]+从第i-1根下来到第i根的时间),dp[i][1] = min(dp[i-1][1]+两个传送点的时间,dp[i-1][0]+从第i-1根底部到第i根传送点的时间);当到达最后一根杆子时,ans = min(dp[n-1][0],dp[n-1][1]+从第n-1根上下来的时间).
时间开销O(n)
试题 G: 买二赠一
时间限制: 1.0s
内存限制: 512.0MB
【问题描述】
某商场有 N 件商品，其中第 i 件的价格是 Ai。现在该商场正在进行 “买二赠一” 的优惠活动，具体规则是：每购买 2 件商品，假设其中较便宜的价格是 P（如果两件商品价格一样，则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P2的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数，代表 A1, A2, A3, . . . ，AN。
【输出格式】
输出一个整数，代表答案。
【样例输入】
7
1 4 2 8 5 7 1
【样例输出】
25
思路:贪心,首先sort(A,A+n),每次取两个最大的出来然后,用其中小的带来的优惠买一件免费的,用book数组记录被买过的。
时间复杂度O(nlogn);
未来的路上，期待和大家一同进步！感谢大家的支持！扫码关注 计算机理论干货分享 ，有更多好物与你分享！快来和我一起学习啦！
