# 第十五届蓝桥杯大赛软件赛省赛 ## Python大学B组 --- ## 试题A: 穿越时空之门 **本题总分：5分** ### 【问题描述】 随着2024年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。 在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数位之和。 在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示中各数位之和。 穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等同于四进制领域的力量时，他才能够成功地穿越。国王选定了小蓝作为领路人，带领着力量值从1到2024的勇者们踏上了这段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这2024位勇者中，有多少人符合穿越时空之门的条件。 ### 【答案提交】 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。 --- ## 试题B: 数字串个数 **本题总分：5分** ### 【问题描述】 小蓝想要构造出一个长度为10000的数字字符串，有以下要求： 1) 小蓝不喜欢数字0，所以数字字符串中不可以出现0； 2) 小蓝喜欢数字3和7，所以数字字符串中必须要有3和7这两个数字。 请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其对10^9+7取余后的结果。 ### 【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。 --- ## 试题C: 连连看 **时间限制：10.0s** **内存限制：512.0MB** **本题总分：10分** ### 【问题描述】 小蓝正在和朋友们玩一种新的连连看游戏。在一个n×m的矩形网格中，每个格子中都有一个整数，第i行第j列上的整数为A_{i,j}。玩家需要在这个网格中寻找一对格子(a,b)-(c,d)使得这两个格子中的整数A_{a,b}和A_{c,d}相等，且它们的位置满足|a-c|=|b-d|>0。请问在这个n×m的矩形网格中有多少对这样的格子满足条件。 ### 【输入格式】 输入的第一行包含两个正整数n,m，用一个空格分隔。 接下来n行，第i行包含m个正整数A_{i,1},A_{i,2},...,A_{i,m}，相邻整数之间使用一个空格分隔。 ### 【输出格式】 输出一行包含一个整数表示答案。 ### 【样例输入】 ``` 3 2 1 2 2 3 3 2 ``` ### 【样例输出】 ``` 6 ``` ### 【样例说明】 一共有以下6对格子：(1,2)-(2,1)，(2,2)-(3,1)，(2,1)-(3,2)，(2,1)-(1,2)，(3,1)-(2,2)，(3,2)-(2,1)。 ### 【评测用例规模与约定】 对于所有评测用例，1≤n,m≤1000，1≤A_{i,j}≤1000。 --- ## 试题D: 闹钟 **时间限制：10.0s** **内存限制：512.0MB** **本题总分：10分** ### 【问题描述】 小蓝有一个闹钟，闹钟的显示格式为HH:MM，其中HH表示小时（00≤HH≤23），MM表示分钟（00≤MM≤59）。 小蓝发现，如果闹钟显示的时间中，数字之和能被7整除，那么这一天就会有好运。 例如，07:14的数字之和为0+7+1+4=12，不能被7整除；而07:21的数字之和为0+7+2+1=10，也不能被7整除；但07:28的数字之和为0+7+2+8=17，同样不能被7整除。 小蓝想知道，从00:00到23:59，有多少个时刻的数字之和能被7整除。 ### 【输入格式】 无输入。 ### 【输出格式】 输出一个整数，表示从00:00到23:59，有多少个时刻的数字之和能被7整除。 ### 【答案提交】 这是一道结果填空题，你只需要算出结果后提交即可。 --- ## 试题E: 蓝桥村的真相 **时间限制：10.0s** **内存限制：512.0MB** **本题总分：15分** ### 【问题描述】 蓝桥村有n个村民，编号为1到n。每个村民要么说真话，要么说假话。 每个村民都做出了一个相同的断言："在我之后的两个人中，恰好有一个人说真话。" （注意：村民i的"之后的两个人"指的是村民i+1和村民i+2，如果编号超过n则循环到1和2） 已知这n个村民中恰好有m个人说真话，请问有多少种可能的真假分布？ ### 【输入格式】 输入一行包含两个正整数n,m，用一个空格分隔。 ### 【输出格式】 输出一个整数，表示可能的真假分布数量。由于答案可能很大，请输出答案对10^9+7取模的结果。 ### 【样例输入】 ``` 3 1 ``` ### 【样例输出】 ``` 3 ``` ### 【样例说明】 当n=3,m=1时，有3种可能的分布：只有村民1说真话、只有村民2说真话、只有村民3说真话。 ### 【评测用例规模与约定】 对于30%的评测用例，1≤n≤10，0≤m≤n； 对于60%的评测用例，1≤n≤100，0≤m≤n； 对于所有评测用例，1≤n≤1000，0≤m≤n。 --- ## 试题F: 魔法巡游 **时间限制：10.0s** **内存限制：512.0MB** **本题总分：15分** ### 【问题描述】 小蓝是一位魔法师，他正在进行一场魔法巡游。巡游的路线是一个环形，上面均匀地分布着n个魔法节点，编号为0到n-1。 每个魔法节点上都有一个数字。小蓝发现，当他站在某个节点上时，如果该节点上的数字是0、2或4，他就能感受到魔法共鸣。 小蓝想知道，从节点0出发，顺时针走过k个节点后，他会感受到多少次魔法共鸣。 ### 【输入格式】 输入的第一行包含两个正整数n,k，用一个空格分隔。 第二行包含n个整数a_0,a_1,...,a_{n-1}，表示每个节点上的数字。 ### 【输出格式】 输出一个整数，表示小蓝感受到魔法共鸣的次数。 ### 【样例输入】 ``` 5 7 0 1 2 3 4 ``` ### 【样例输出】 ``` 5 ``` ### 【样例说明】 小蓝走过的节点依次为：0→1→2→3→4→0→1→2（共7个节点，包括起点）。 其中节点0、2、4、0、2上的数字为0、2、4、0、2，都能引起魔法共鸣，共5次。 ### 【评测用例规模与约定】 对于30%的评测用例，1≤n≤100，1≤k≤100； 对于60%的评测用例，1≤n≤1000，1≤k≤10^5； 对于所有评测用例，1≤n≤10^5，1≤k≤10^12。 --- ## 试题G: 过路费 **时间限制：10.0s** **内存限制：512.0MB** **本题总分：20分** ### 【问题描述】 蓝国有n个城市，编号为1到n，城市之间通过m条双向道路连接。第i条道路连接城市u_i和v_i，通过这条道路需要支付c_i的过路费。 小蓝想从城市1前往城市n，他希望找到一条总过路费最少的路径。但是，小蓝有一个特殊的通行证，可以使用一次将某条道路的过路费减半（向下取整）。 请问小蓝从城市1到城市n的最小总过路费是多少？ ### 【输入格式】 输入的第一行包含两个正整数n,m，用一个空格分隔。 接下来m行，每行包含三个正整数u_i,v_i,c_i，表示一条连接城市u_i和v_i的道路，过路费为c_i。 ### 【输出格式】 输出一个整数，表示小蓝从城市1到城市n的最小总过路费。 ### 【样例输入】 ``` 3 3 1 2 4 2 3 2 1 3 6 ``` ### 【样例输出】 ``` 5 ``` ### 【评测用例规模与约定】 对于30%的评测用例，2≤n≤100，1≤m≤200； 对于60%的评测用例，2≤n≤1000，1≤m≤2000； 对于所有评测用例，2≤n≤10^5，1≤m≤2×10^5，1≤c_i≤10^6。 --- ## 试题H: 职业 **时间限制：10.0s** **内存限制：512.0MB** **本题总分：25分** ### 【问题描述】 蓝桥公司有n名员工，每名员工有一个能力值a_i。公司要进行一次职业分配，将员工分配到不同的部门。 分配规则如下： 1. 每个部门至少有一名员工； 2. 同一部门内的员工，能力值的最大值与最小值之差不能超过k； 3. 目标是使部门数量尽可能少。 请问最少需要多少个部门？ ### 【输入格式】 输入的第一行包含两个正整数n,k，用一个空格分隔。 第二行包含n个整数a_1,a_2,...,a_n，表示每名员工的能力值。 ### 【输出格式】 输出一个整数，表示最少需要的部门数量。 ### 【样例输入】 ``` 5 2 1 2 3 5 6 ``` ### 【样例输出】 ``` 2 ``` ### 【样例说明】 可以将员工分为两个部门：{1,2,3}和{5,6}。 第一个部门能力值范围为1-3，差值为2≤k； 第二个部门能力值范围为5-6，差值为1≤k。 无法只用一个部门，因为5-1=4>k。 ### 【评测用例规模与约定】 对于30%的评测用例，1≤n≤100； 对于60%的评测用例，1≤n≤1000； 对于所有评测用例，1≤n≤10^5，0≤k≤10^9，1≤a_i≤10^9。 --- **比赛时间：4小时** **祝你好运！**