蓝桥杯【第15届省赛】Python B组 32.60 分

荷碧TongZJ 2024-06-14 14:35:02 阅读 78

F 题列表越界访问了……省一但没什么好名次

测评链接:https://www.dotcpp.com/oj/train/1120/

C 语言网真是 ** 测评,时间限制和考试的不一样,E 题给我整时间超限?

A:穿越时空之门  100🏆

【问题描述】

        随着 2024 年的钟声回荡,传说中的时空之门再次敞开。这扇门是一条神秘的通道,它连接着二进制和四进制两个不同的数码领域,等待着勇者们的探索。

        在二进制的领域里,勇者的力量被转换成了力量数值的二进制表示中各数位之和。

        在四进制的领域里,力量的转换规则相似,变成了力量数值的四进制表示中各数位之和。

        穿越这扇时空之门的条件是严苛的:当且仅当勇者在二进制领域的力量等同于四进制领域的力量时,他才能够成功地穿越。

        国王选定了小蓝作为领路人,带领着力量值从 1 到 2024 的勇者们踏上了这段探索未知的旅程。作为小蓝的助手,你的任务是帮助小蓝计算出,在这 2024 位勇者中,有多少人符合穿越时空之门的条件。

【解析及代码】

省流:数字转成二进制、四进制,数位之和相等的数

答案:63

cnt = 0for i in range(1, 2025): # 二进制 bins = bin(i)[2:].count("1") # 四进制 four = 0 while i: four += i % 4 i //= 4 # 累加 cnt += bins == fourprint(cnt)

B:数字串个数  100🏆

【问题描述】

        小蓝想要构造出一个长度为 10000 的数字字符串,有以下要求:

        1) 小蓝不喜欢数字 0 ,所以数字字符串中不可以出现 0 ;

        2) 小蓝喜欢数字 3 和 7 ,所以数字字符串中必须要有 3 和 7 这两个数字。

        请问满足题意的数字字符串有多少个?这个数字会很大,你只需要输出其 对

10^9 + 7

取余后的结果。

【解析及代码】

容斥原理秒杀

答案:157509472

mod = int(1e9 + 7)n = 10000cnt = pow(9, n, mod)# 去除 no(3) + no(7) 的情况cnt -= 2 * pow(8, n, mod)# 补上 no(3 and 7) 的情况cnt += pow(7, n, mod)print(cnt % mod)

C:连连看  45🏆

【问题描述】

        小蓝正在和朋友们玩一种新的连连看游戏。在一个 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}, \cdots, 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) 。

【评测用例规模与约定

20%

1 \leq n, m \leq 50

100%

1 \leq n, m \leq 1000, 1 \leq A_{i,j} \leq 1000

【解析及代码】

根据题意可知,(a, b) - (c, d) 中的两个元素位于同一斜线上

(1, 2) - (2, 1) 和 (2, 1) - (1, 2) 算不同的两对,优化一下比较流程计算结果即可

n, m = map(int, input().split())A = [list(map(int, input().split())) for _ in range(n)]# A[a][b] = A[c][d], 处于同一斜线上cnt = 0for i in range(n): for j in range(m): # 只跟当前行以下的行比较 # 向左下角 for p in range(1, min(n - i, j + 1)): cnt += A[i][j] == A[i + p][j - p] # 向右下角 for p in range(1, min(n - i, m - j)): cnt += A[i][j] == A[i + p][j + p]print(cnt * 2)

D:神奇闹钟  100🏆

【问题描述】

        小蓝发现了一个神奇的闹钟,从纪元时间(1970 年 1 月 1 日 00:00:00 )开 始,每经过 x 分钟,这个闹钟便会触发一次闹铃(纪元时间也会响铃)。这引起 了小蓝的兴趣,他想要好好研究下这个闹钟。

        对于给出的任意一个格式为 yyyy-MM-dd HH:mm:ss 的时间,小蓝想要 知道在这个时间点之前(包含这个时间点)的最近的一次闹铃时间是哪个时间?

        注意,你不必考虑时区问题。

输入格式】

        输入的第一行包含一个整数 T,表示每次输入包含 T 组数据。

        接下来依次描述 T 组数据。

        每组数据一行,包含一个时间(格式为 yyyy-MM-dd HH:mm:ss)和一 个整数 x ,其中 x 表示闹铃时间间隔(单位为分钟)。

【输出格式】

        输出 T 行,每行包含一个时间(格式为 yyyy-MM-dd HH:mm:ss),依次表示每组数据的答案。

【样例】

输入 输出

2

2016-09-07 18:24:33 10

2037-01-05 01:40:43 30

2016-09-07 18:20:00

2037-01-05 01:30:00

【评测用例规模与约定

100%

1 \leq T \leq 10, 1 \leq x \leq 1000

【解析及代码】

 What can I say?

import timefmt = "%Y-%m-%d %H:%M:%S"for _ in range(int(input())): datetime, x = input().rsplit(maxsplit=1) x = int(x) * 60 t = round(time.mktime(time.strptime(datetime, fmt))) print(time.strftime(fmt, time.localtime(t - t % x)))

E:蓝桥村的真相  45🏆

【问题描述】

        在风景如画的蓝桥村,n 名村民围坐在一张古老的圆桌旁,参与一场思想 的较量。这些村民,每一位都有着鲜明的身份:要么是誉满乡野的诚实者,要 么是无可救药的说谎者。

        当会议的钟声敲响,一场关于真理与谬误的辩论随之展开。每位村民轮流 发言,编号为 i 的村民提出了这样的断言:坐在他之后的两位村民——也就是 编号 i + 1 和 i + 2(注意,编号是环形的,所以如果 i 是最后一个,则 i + 1 是 第一个,以此类推)之中,一个说的是真话,而另一个说的是假话。

        在所有摇曳不定的陈述中,有多少真言隐藏在谎言的面纱之后?

        请你探索每一种可能的真假排列组合,并计算在所有可能的真假组合中, 说谎者的总数。

输入格式】

        输入的第一行包含一个整数 T,表示每次输入包含 T 组数据。

        接下来依次描述 T 组数据。

        每个数据一行包含一个整数 n,表示村落的人数。

【输出格式】

        输出 T 行,每行包含一个整数,依次表示每组数据的答案。

【样例】

输入 输出 说明

2

3

3

6

6

可能的组合有

「假,假,假」「真,真,假」

「真,假,真」「假, 真,真」

说谎者的总数为 3 + 1 + 1 + 1 = 6。

【评测用例规模与约定

10%

T=1, 3 \leq n \leq 10

40%

1 \leq T \leq 10^2, 3 \leq n \leq 3 \times 10^3

100%

1 \leq T \leq 10^5, 3 \leq n \leq 10^{18}

【解析及代码】

1 表谎言,0 表真言,每 3 个人可能的组合有:010, 001, 100, 111

前三种情况:100 是一个循环 (第三人是前两人的“同或”),如果 n 能被 3 整除,这三种情况就贡献了 n 个说谎的

第四种情况:全都是 111,贡献了 n 个说谎的

for _ in range(int(input())): n = int(input()) print(n * (1 + (n % 3 == 0)))

F:魔法巡游  9🏆

【问题描述】

        在蓝桥王国中,两位魔法使者,小蓝与小桥,肩负着维护时空秩序的使命。 他们每人分别持有 N 个符文石,这些石头被赋予了强大的力量,每一块上都刻 有一个介于 1 到

10^9

之间的数字符号。小蓝的符文石集合标记为

s_1, s_2, \cdots, s_N

, 小桥的则为

t_1, t_2, \cdots, t_N

        两位魔法使者的任务是通过使用符文石,在各个时空结点间巡游。每次巡游遵循这样一条法则:当小蓝使用了符文石

s_i

到达新的结点后,小桥必须选用 一个序号更大的符文石(即某个

t_j

满足 j > i)前往下一个结点。同理,小桥抵 达之后,小蓝需要选择一个序号 k > j 的符文石

s_k

继续他们的巡游。

        为了成功地穿梭时空,两个连续使用的符文石上的数字符号必须有共鸣, 这种共鸣只有当数字符号中至少包含一个特定的元素——星火(数字 0)、水波 (数字 2)或者风语(数字 4)时,才会发生。例如,符号序列 126, 552, 24, 4 中 的每对连续符文都包含了至少一个共鸣元素,则它们是一系列成功的巡游;而 如果是 15, 51, 5,则不成立,因为它们之间的共鸣元素不包含星火、水波或风语 中的任意一个。

        小蓝总是先启程,使用他的符文石开启巡游。

        你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样 的序列形式为

s_{i_i}, t_{i_2}, s_{i_3}, t_{i_4}, \cdots

,其中序列索引满足

i_1 < i_2 < i_3 < i_4 < \cdots

,并且序列中每一对相邻的符文石都至少包含一个共鸣元素。

输入格式】

        输入的第一行包含一个整数 N,表示每位魔法使者持有的符文石数量。

        第二行包含 N 个整数

s_1, s_2, \cdots, s_N

,相邻整数之间使用一个空格分隔,表示小蓝的符文石上刻有的数字符号。

        第三行包含 N 个整数

t_1, t_2, \cdots, t_N

,相邻整数之间使用一个空格分隔,表示小桥的符文石上刻有的数字符号。

【输出格式】

        输出一行包含一个整数,表示小蓝和小桥在遵守所有规则的情况下,最多能进行多少次时空巡游。

【样例】

输入 输出 说明

5

126 393 581 42 44

204 990 240 46 52

4

小蓝和小桥可以选择以下符文石序列进行巡游:

s_1

(126) →

t_3

(240) →

s_4

(42) →

t_5

(52)

这里,数字 2 作为共鸣元素连接了

s_1

t_3

s_4

和 t

t_5

,数字 2、4 作为共鸣元素 连接了

t_3

s_4

【评测用例规模与约定

30%

1 \leq N \leq 10^3, 1 \leq s_i, t_i \leq 10^5

100%

1 \leq N \leq 10^5, 1 \leq s_i, t_i \leq 10^9

【解析及代码】

编写类 Element,重写 __init__ 方法以搜集符文石的特定元素,存储到 set 中

存储非空的 Element 的索引,结合 bisect 的二分查找加速枚举,直接动态规划

测评结果“答案错误”,不知道哪里错了

import bisectclass Element(set): base = {"0", "2", "4"} def __init__(self, s): super().__init__(set(s) & self.base)n = int(input())e_lan = list(map(Element, input().split()))e_qiao = list(map(Element, input().split()))# 编制非空元素的索引i_lan = [i for i in range(n) if e_lan[i]]i_qiao = [i for i in range(n) if e_qiao[i]]if not (i_lan and i_qiao): print(1)# 两者都非空else: # 小蓝先出发 dp = [[0, 0] for _ in range(n)] for i in i_lan: dp[i][0] = 1 res = 0 for i in sorted(set(i_lan + i_qiao)): j_lan = bisect.bisect_left(i_lan, i) j_qiao = bisect.bisect_left(i_qiao, i) # 小蓝出发 if j_lan < len(i_lan) and i_lan[j_lan] == i: for src in i_qiao[:j_qiao]: if e_qiao[src] & e_lan[i]: dp[i][0] = max(dp[i][0], dp[src][1] + 1) # 小桥出发 if j_qiao < len(i_qiao) and i_qiao[j_qiao] == i: for src in i_lan[:j_lan]: if e_lan[src] & e_qiao[i]: dp[i][1] = max(dp[i][1], dp[src][0] + 1) res = max(res, max(dp[i])) print(res)

G:缴纳过路费

【问题描述】

        在繁华的商业王国中,N 座城市被 M 条商路巧妙地连接在一起,形成了一 个错综复杂的无向图网络。每条商路是双向通行的,并且任意两座城市之间最 多只有一条直接的商路。每条商路都有它的规则,其中最引人注目的就是穿过商路,需要缴纳过路费。因此,商人们在选择商路时必须格外认真。

        有一位名叫小蓝的商人,他对于商路的花费有着自己独到的见解。在小蓝 眼中,一条路线包含一条或多条商路,但路线的成本并不是沿途累积的过路费总和,而是这条路线上最贵的那一次收费。这个标准简单而直接,让他能迅速 评估出一条路线是否划算。

        于是,他设立了一个目标,即找出所有城市对,这些城市之间的最低路线 成本介于他心中预设的两个数 L 和 R 之间。他相信,这样的路线既不会太廉 价,以至于路况糟糕;也不会过于昂贵,伤害他精打细算的荷包。

        作为小蓝的助手,请你帮助小蓝统计出所有满足条件的城市对数量。

输入格式】

        输入的第一行包含四个整数 N, M, L, R,表示有 N 座城市和 M 条双向通行 的商路,以及小蓝心中预设的最高过路费的下限 L 和上限 R。

        接下来 M 行,每行包含三个整数 u, v, w,表示城市 u 和城市 v 之间有一条 双向通行的商路,过路费为 w。保证每对城市之间最多只有一条直接的商路。

【输出格式】

        输出一行包含一个整数,表示满足条件的城市对数量。

【样例】

输入 输出 说明
5 5 1 2 1 2 2 1 3 5 1 4 1 2 4 5 2 5 4 3

满足条件的城市对有

(1, 2),(1, 4),(2, 4)

【评测用例规模与约定

30%

1 \leq N \leq 10^3, 1 \leq M \leq \min(2 \times 10^3, \frac{N \times (N-1)}{2}),

1\leq L \leq R \leq 10^5, 1 \leq u, v \leq N, u \neq v, 1 \leq w \leq 10^5

100%

1 \leq N \leq 10^5, 1 \leq M \leq \min(2 \times 10^5, \frac{N \times (N-1)}{2}),

1\leq L \leq R \leq 10^9, 1 \leq u, v \leq N, u \neq v, 1 \leq w \leq 10^9

【解析及代码】

注:经大佬提醒,发现该题做法错误,应该是 Kruskal + 并查集 (正确的做法有空再研究)。如果将题目条件中“过路费最贵的一次∈[L, R]”改为“过路费∈[L, R]”,则是以下做法

边权不在 [L, R] 范围内的边都可以忽略

对每个结点,使用列表 dset 记录所连接的、序号比其小的结点 (也就是并查集所说的“前驱”),从而使 dset 描述若干棵结点树

例如对于 dset = [0, 0, 1, 3, 2],结点 0,1,2,4 处于同一棵树内,结点 3 则独自构成一棵树。而结点 0,1,2,4 两两之间连通,所以这棵树贡献了 

\frac{v(v+1)}{2}|_{v=4}

 个城市对,而第二颗树无贡献

对 dset 中的结点扫描一次,即可找到每个结点所对应的“祖先结点”:

dset[0] == 0:跳过dset[1] != 1:dset[1] = dset[dset[1]] = dset[0] = 0dset[2] != 2:dset[2] = dset[dset[2]] = dset[1] = 0dset[3] == 3:跳过dset[4] != 4:dset[4] = dset[dset[4]] = dset[2] = 0

从而使得 dset 转变为 [0, 0, 0, 3, 0],使用 Counter 统计每棵树的结点数量 (筛除只有 1 个结点的),根据结点数 v 累加 

\frac{v(v+1)}{2}

 即可

from collections import Countern, m, l, r = map(int, input().split())class DisjointSet(list): def __init__(self): # s.j.: self[i] < i super().__init__(range(n)) def find_ancestor(self): # 按顺序找到所有结点的祖先结点 for i in range(n): self[i] = self[self[i]] def export(self): # 统计每个祖先结点的族群规模, 筛选出族群规模 > 1 的族群 return sum(v * (v + 1) // 2 for v in filter((1).__lt__, Counter(self).values()))dset = DisjointSet()for _ in range(m): u, v, w = map(int, input().split()) # 只存储符合条件的边 if l <= w <= r: u, v = sorted(map((-1).__add__, (u, v))) # 存储序号最大的 dset[v] = max(u, 0 if dset[v] == v else dset[v])dset.find_ancestor()print(dset.export())

H:纯职业小组

【问题描述】

        在蓝桥王国,国王统治着一支由 n 个小队组成的强大军队。每个小队都由相同职业的士兵组成。具体地,第 i 个小队包含了

b_i

名职业为

a_i

的士兵。

        近日,国王计划在王宫广场举行一场盛大的士兵检阅仪式,以庆祝王国的繁荣昌盛。然而,在士兵们入场的过程中,一场突如其来的风暴打乱了他们的 行列,使得不同小队的士兵混杂在一起,次序乱成一团,

        尽管国王无法知道每个士兵的具体职业,但为了确保仪式能顺利进行,国王打算从这些混乱的士兵中选出一部分,组成 k 个“纯职业小组”进行检阅。 一个“纯职业小组”定义为由 3 名同职业的士兵组成的队伍。

        请问,国王至少需要选择多少名士兵,才能确保这些士兵可以组成 k 个 “纯职业小组”。

输入格式】

        输入的第一行包含一个整数 T,表示每次输入包含 T 组数据。

        接下来依次描述 T 组数据。

        每组数据的第一行包含两个整数

n_t

和 k ,用一个空格分隔,表示小队的数量和要组成的纯职业小组的数量。

        接下来的

n_t

行,每行包含两个整数

a_i

b_i

,用一个空格分隔,表示第 i 个小队中士兵的职业和数量。

【输出格式】

        输出 T 行,每行包含一个整数,依次表示每组数据的答案,即为了组成 k 个“纯职业小组”,国王至少需要选择的士兵数量。如果无论如何也无法组成 k 个“纯职业小组”,则输出 −1。

【样例】

输入 输出 说明

2

3 2

1 3

2 3

3 3

3 5

1 3

2 3

3 3

8

-1

在第一个样例中,要想组成 2 个“纯职业小组”,

国王至少需要选择 8 名士兵。若只选择了 7 名士兵,

则这 7 名士兵的职业可能为 1, 1, 1, 2, 2, 3, 3,

无法组成 2 个“纯职业小组”。

在第二个样例中,即使选择了所有士兵,

也无法组成 5 个“纯职业小组”, 因此输出 −1。

【评测用例规模与约定

50%

1 \leq T \leq 10, 1 \leq \sum^T_{t=1}n_t \leq 2 \times 10^3, 1\leq a_i, b_i \leq 10^5, 1\leq k \leq 10^7

100%

1 \leq T \leq 100, 1 \leq \sum^T_{t=1}n_t \leq 2 \times 10^5, 1\leq a_i, b_i \leq 10^9, 1\leq k \leq 10^{13}

【解析及代码】

三种职业为 3 6 9,需选定 3 组时,最坏的情况是选 2 5 5 (再任意 + 1)

需选定 4 组时,最坏的情况是选 2 5 8 (再任意 + 1)

难办啊,那就不办了 (有空再说)



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。