type
status
date
slug
summary
tags
category
icon
password
Last edited time
May 3, 2024 03:57 AM
第十五届蓝桥杯省赛Python研究生组题解
📝 主旨内容
试题 A: 劲舞团(填空题)
【问题描述】
小蓝最近迷上了一款名为“劲舞团”的游戏，具体来说，只要按照游戏中给出的键位提示依次按出对应的键位，游戏人物便可以跟随节奏跳舞。对于连
续的 K 次正确敲击，如果任意连续的两次敲击间间隔时间都小于等于 1s，那么我们称这是一次 K 连击。现在给出一局小蓝的游戏记录文件，log.txt 中记录了 N 条记录，每条记录有三个字段，依次为正确的敲击字符、小蓝打出的字符、打出字符的时间对应的毫秒时间戳。现在请你计算下最长的 K 连击是多少，你只需要输出 K 的值。
模拟题，需要读文件，忘记怎么读了，场上看文档copy了一个，多读了回车
提交答案：9
试题 B: 召唤数学精灵(填空题)
【问题描述】
数学家们发现了两种用于召唤强大的数学精灵的仪式，这两种仪式分别被称为累加法仪式 A(n) 和累乘法仪式 B(n)。
累加法仪式 A(n) 是将从 1 到 n 的所有数字进行累加求和，即：A(n) = 1 + 2 + · · · + n 。
累乘法仪式 B(n) 则是将从 1 到 n 的所有数字进行累乘求积，即：B(n) = 1 × 2 × · · · × n 。
据说，当某个数字 i 满足 A(i) − B(i) 能被 100 整除时，数学精灵就会被召唤出来。
现在，请你寻找在 1 到 2024041331404202 之间有多少个数字 i，能够成功召唤出强大的数学精灵。
16位数，暴力是不可能暴力的，python一秒最多执行10^8次。一开始以为是数学题分解质因数什么的，可以显然发现，阶乘会大得很快而且因为有足够多的2和5存在，阶乘这边就不需要考虑100整除了，只需要考虑累加这边，n*(n-1)/2这个式子需要分解出2^3和5^2，这样才能凑到200，但是这样也是很难计算的(看到这里，你会发现我上面说的都没用)
打印符合条件的数字，发现除了1和3之外形成了四个等差数列，然后就可以O(1)算了，最后答案记得加2
提交结果：40480826628086
试题 C: 封闭图形个数
【问题描述】
在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。
封闭图形是指数字中完全封闭的空间，例如数字 1、2、3、5、7 都没有形成封闭图形，而数字 0、4、6、9 分别形成了 1 个封闭图形，数字 8 则形成了 2 个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字68，由于 6 形成了 1 个封闭图形，而 8 形成了 2 个，所以 68 形成的封闭图形的个数总共为 3。
在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 41 和数字 18，它们对应的封闭图形的个数分别
为 1 和 2，因此数字 41 小于数组 18。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 14 和数字 41，它们的封闭图形的个数都是 1，但 14 < 41，所以数字 14 小于数字 41。如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。
小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 n 个数 a1, a2, . . . , an，请你按照蓝桥王国的数字大小规则，将这 n 数从小到大排序，并输出排序后结果。
【输入格式】
输入的第一行包含一个整数 n ，表示给定的数字个数。
第二行包含 n 个整数 a1, a2, . . . , an ，相邻整数之间使用一个空格分隔，表
示待排序的数字。
【输出格式】
输出一行包含 n 个整数，相邻整数之间使用一个空格分隔，表示按照蓝桥
王国的数字大小规则从小到大排序后的结果。
【样例输入】
【样例输出】
【样例说明】
对于给定的数字序列 [18, 29, 6]，数字 18 的封闭图形个数为 2，数字 29 的封闭图形个数为 1，数字 6 的封闭图形个数为 1。按照封闭图形个数从小到大排序后，得到 [29, 6, 18]。
由于数字 29 和数字 6 的封闭图形个数相同，因此需要进一步按照数值大小对它们进行排序，最终得到 [6, 29, 18]。
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ n ≤ 2 × 10^3，1 ≤ ai ≤ 10^5。
对于所有评测用例，1 ≤ n ≤ 2 × 10^5，1 ≤ ai ≤ 10^9。
模拟题，看了眼数据范围没卡0这个数，复杂度O(nlogn)
试题 D: 商品库存管理
【问题描述】
在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n。初始时，每种商品的库存量均为 0。
为了高效地监控和调整库存量，小蓝的管理团队设计了 m 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L, R]）。执行这些操作时，区间内每种商品的库存量都将增加 1。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。
现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，对于每个操作，如果不执行该操作而执行其它操作，库存量为 0 的商品的种类数。
【输入格式】
输入的第一行包含两个整数 n 和 m，分别表示商品的种类数和操作的个数。
接下来的 m 行，每行包含两个整数 L 和 R，表示一个操作涉及的商品区间。
【输出格式】
输出 m 行，每行一个整数，第 i 行的整数表示如果不执行第 i 个操作，则最终库存量为 0 的商品种类数。
【样例输入】
【样例输出】
【样例说明】
考虑不执行每个操作时，其余操作对商品库存的综合影响：
- 不执行操作 1：剩余的操作是操作 2（影响区间 [2, 4]）和操作 3（影响区间 [3, 5]）。执行这两个操作后，商品库存序列变为 [0, 1, 2, 2, 1]。在这种情况下，只有编号为 1 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。
- 不执行操作 2：剩余的操作是操作 1（影响区间 [1, 2]）和操作 3（影响区间 [3, 5]）。执行这两个操作后，商品库存序列变为 [1, 1, 1, 1, 1]。在这种情况下，所有商品的库存量都不为 0。因此，库存量为 0 的商品种类数为 0。
- 不执行操作 3：剩余的操作是操作 1（影响区间 [1, 2]）和操作 2（影响区间 [2, 4]）。执行这两个操作后，商品库存序列变为 [1, 2, 1, 1, 0]。在这种情况下，只有编号为 5 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n, m ≤ 5 × 10^3，1 ≤ L ≤ R ≤ n。
对于所有评测用例，1 ≤ n, m ≤ 3 × 10^5，1 ≤ L ≤ R ≤ n。
开局一看就是差分，嘴都笑裂了。但是一看不对劲啊，需要排除一个操作在看剩下的操作，就在想那我不是每次都得恢复一下原数组O(n)再统计零的个数。那不就是O(n^2)的了？？第二道编程题就开始暴力了？？强度这么大的？？
做完后面的题回过头来看，我下一道都做的来，这道做不来？仔细想一下，只有原来是1的地方，在区间取消后才会变成0，那么我是不是可以直接前缀和来统计1的出现次数，然后每次查询(移除一个区间)的复杂度就是O(1)的
试题 E: 砍柴
【问题描述】
小蓝和小乔正在森林里砍柴，它们有 T 根长度分别为 n1, n2, · · · , nT 的木头。对于每个初始长度为 n 的木头，小蓝和小乔准备进行交替砍柴，小蓝先出手。每次砍柴时，若当前木头长度为 x ，需要砍下一截长度为 p 的木头，然后换另一个人继续砍，其中 2 ≤ p ≤ x 且 p 必须为质数。当轮到某一方时 x = 1 或 x = 0 ，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每根木头判断是小蓝赢还是小乔赢，如果小蓝赢请输出 1 （数字 1），如果小乔赢请输出 0 （数字 0）。
【输入格式】
输入的第一行包含一个正整数 T，
接下来 T 行，每行包含一个正整数，其中第 i 的整数为 ni 。
【输出格式】
输出 T 行，每行包含一个整数，依次表示对于每一根木头的答案。
【样例输入】
【样例输出】
【样例说明】
对于 n1 = 1 ，由于当前长度 x = 1 ，小蓝直接输掉，小乔赢；
对于 n2 = 2 ，小蓝选择 p = 2 ，轮到小乔时当前长度 x = 2 − 2 = 0 ，小乔输掉，小蓝赢；
对于 n3 = 6 ，小蓝选择 p = 5 ，轮到小乔时 x = 6 − 5 = 1 ，小乔输掉，小蓝赢。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ ni ≤ 10^3；
对于所有评测用例，1 ≤ ni ≤ 10^5 ，1 ≤ T ≤ 10^4。
这算是一道简单DP吧，True代表1也就是小蓝赢，False代表0表示小乔赢
有两个思路，枚举质数，看能否转移到原本是False的地方(你必输我就必胜了)。第二种就是枚举False，看差值是否是质数，好像都行。二者的数量级是差不多的都是10^4，考场用的第二种。但是我发现好像会超时10^5*10^4？？？好不容易方程都想出来了只拿个20%灰溜溜地走？？？必不可能好吧，最后选择了打表哈哈哈，离线处理好答案，O(logn)查询。然后直接复制上下代码大小超过100K了不让我交，那我只好删掉最后几行勉强符合要求，但是回过头来越想越气，我明明都想出来了为什么还要删掉我的答案，灵机一动把代码里的空格全删了就好了hhh
试题 F: 智力测试
【问题描述】
【输入格式】
【输出格式】
输出 T 行，每行包含一个整数，依次表示每个问题的答案。
【样例输入】
【样例输出】
【样例说明】
询问 1：
(4, 4) → (2, 4) → (3, 4) → (1, 4) → (1, 1);
(4, 4) → (2, 4) → (3, 4) → (3, 1) → (1, 1);
(4, 4) → (2, 4) → (2, 1) → (3, 1) → (1, 1);
(4, 4) → (4, 1) → (2, 1) → (3, 1) → (1, 1)。
询问 2：
不存在方案可以从 (2, 2) 走到 (2, 4) 。
【评测用例规模与约定】
都到这里了，赛事的精髓就要体现了，n和m都是10^5，我连dp都不想的，能拿20%就行，直接DFS(差点没看懂题出现了一个没见过的符号，一开始还以为印错了，仔细想才知道是不存在的意思)
题目大意就是说，每次只能竖着走或者横着走，而且要确保每次移动都要刚好稍微大一丝丝才行
试题 G: 最大异或结点
【问题描述】
小蓝有一棵树，树中包含 N 个结点，编号为 0, 1, 2, · · · , N − 1 ，其中每个
结点上都有一个整数 Xi 。他可以从树中任意选择两个不直接相连的结点 a 、b
并获得分数 Xa ⊕ Xb ，其中 ⊕ 表示按位异或操作。
请问小蓝可以获得的最大分数是多少？
【输入格式】
输入的第一行包含一个整数 N ，表示有 N 个结点。
第二行包含 N 个整数 X1, X2, · · · , XN ，相邻整数之间使用一个空格分隔。
第三行包含 N 个整数 F1, F2, · · · , FN ，相邻整数之间使用一个空格分隔，
其中第 i 个整数表示 i 的父结点编号，Fi = −1 表示结点 i 没有父结点。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
【样例输出】
【样例说明】
选择编号为 3 和 4 的结点，x3 = 3 ，x4 = 4 ，他们的值异或后的结果为 3 ⊕ 4 = 7 。
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N ≤ 1000 ；
对于所有评测用例，1 ≤ N ≤ 10^5, 0 ≤ Xi ≤ 2^31 − 1 ，−1 ≤ Fi ≤ N ，Fi 不等于 0 。
明着送是吧，直接送一半？？给的数据这么好我连图都不用建，直接暴力是吧，可以，这就是懂出题的(正解可能需要用到位运算)
试题 H: 植物生命力
【问题描述】
小蓝是一位资深的植物学家，他专注于研究植物的相互关系和生命力。在他所照料的森林中，每个品种的植物都拥有独特的生命力，彼此之间互不相同。
植物的生命力会影响其下级品种的生长。具体地，如果下级品种的生命力数值无法被上级品种的生命力数值整除，或者下级品种的生命力数值大于上级品种的生命力数值时，它们便会受到压制，无法茁壮成长。
为了深入研究和定量分析这一现象，小蓝构建了一种模型。他将森林中的植物品种关系抽象成了一棵包含 n 个结点的树，结点的编号从 1 到 n，代表不同的植物品种。其中，树的根结点编号为 s，结点 i（1 ≤ i ≤ n）的生命力表示为 ai。
现在，小蓝想要对于每个结点 i，统计其子树（以 i 为根的子树）中同时满足以下两个条件的子结点的数量：
1. 子结点的生命力小于结点 i 的生命力 ai。
2. 子结点的生命力无法被结点 i 的生命力 ai 整除。
请你帮助小蓝计算出所有子树中满足条件的结点个数的总和。
【输入格式】
输入的第一行包含两个整数 n 和 s，分别表示结点的数量和根结点的编号。
第二行包含 n 个互不相同的整数 a1, a2, · · · , an，相邻整数之间使用一个空格分隔，其中 ai 表示编号为 i 的结点的生命力。
接下来的 n − 1 行，每行包含两个整数 u 和 v ，用一个空格分隔，表示编号为 u 和 v 的结点之间存在一条边。
【输出格式】
输出一行包含一个整数，表示所有子树中满足条件的结点个数的总和。
【样例输入】
【样例输出】
【样例说明】
在给定的样例中，树的结构如下：
在以 1 为根的子树中，满足条件的结点有 2, 5，个数为 2。
在以 2 为根的子树中，满足条件的结点有 4, 5，个数为 2。
在以 3 ∼ 6 为根的子树中，没有满足条件的结点，个数均为 0。
因此答案为 2 + 2 = 4。
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ n ≤ 2 × 10^3，1 ≤ s, u, v, ai ≤ n，a1, a2, . . . , an 互不相同。
对于所有评测用例，1 ≤ n ≤ 10^5，1 ≤ s, u, v, ai ≤ n，a1, a2, . . . , an 互不相同。
把DFS打在公屏上！什么？一个DFS解决不了，那就两个
🤗 总结归纳
自我感觉良好，没空题，提前半小时下机吃饭，就是不知道结果会不会给我开玩笑
2024-04-29更新
省赛出成绩了
小小省一，拿下拿下
全省第二，可惜可惜
📎 参考文章
- 作者:ziuch
- 链接:https://ziuch.com/article/15th-lanqiao-region-python-postgraduate-solution
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。