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

05-14 阅读 0评论

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

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

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

A：穿越时空之门 100🏆

【问题描述】

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

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

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

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

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

【解析及代码】

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

答案：63

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

B：数字串个数 100🏆

【问题描述】

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

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

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

请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其对 $蓝桥杯【第15届省赛】Python B组 32.60 分,10^9 + 7,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第2张$ 取余后的结果。

【解析及代码】

容斥原理秒杀

答案：157509472

mod = int(1e9 + 7)
n = 10000
cnt = 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 列上的整数为 $蓝桥杯【第15届省赛】Python B组 32.60 分,A_{i,j},词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第3张$ 。玩家需要在这个网格中寻找一对格子 $蓝桥杯【第15届省赛】Python B组 32.60 分,(a, b) - (c, d),词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第4张$ 使得这两个格子中的整数 $蓝桥杯【第15届省赛】Python B组 32.60 分,A_{a,b},词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第5张$ 和 $蓝桥杯【第15届省赛】Python B组 32.60 分,A_{c,d},词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第6张$ 相等，且它们的位置满足 $蓝桥杯【第15届省赛】Python B组 32.60 分,|a-c|=|b-d|0,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第7张$ 。请问在这个 n × m 的矩形网格中有多少对这样的格子满足条件。

【输入格式】

输入的第一行包含两个正整数 n, m ，用一个空格分隔。

接下来 n 行，第 i 行包含 m 个正整数 $蓝桥杯【第15届省赛】Python B组 32.60 分,A_{i,1}, A_{i,2}, \cdots, A_{i,m},词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第8张$ ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例】

输入

输出

说明

3 2

1 2

2 3

3 2

一共有以下 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%	$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq n, m \leq 50,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第9张$
100%	$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq n, m \leq 1000, 1 \leq A_{i,j} \leq 1000,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第10张$

【解析及代码】

根据题意可知，(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 = 0
for 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），依次表示每组数据的答案。

【样例】

输入

输出

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%	$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq T \leq 10, 1 \leq x \leq 1000,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第11张$

【解析及代码】

What can I say?

import time
fmt = "%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 行，每行包含一个整数，依次表示每组数据的答案。

【样例】

输入

输出

说明

可能的组合有

「假，假，假」「真，真，假」

「真，假，真」「假，真，真」

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

【评测用例规模与约定】

10%	$蓝桥杯【第15届省赛】Python B组 32.60 分,T=1, 3 \leq n \leq 10,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第12张$
40%	$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq T \leq 10^2, 3 \leq n \leq 3 \times 10^3,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第13张$
100%	$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq T \leq 10^5, 3 \leq n \leq 10^{18},词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第14张$

【解析及代码】

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 到 $蓝桥杯【第15届省赛】Python B组 32.60 分,10^9,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第15张$ 之间的数字符号。小蓝的符文石集合标记为 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_1, s_2, \cdots, s_N,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第16张$ ，小桥的则为 $蓝桥杯【第15届省赛】Python B组 32.60 分,t_1, t_2, \cdots, t_N,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第17张$ 。

两位魔法使者的任务是通过使用符文石，在各个时空结点间巡游。每次巡游遵循这样一条法则：当小蓝使用了符文石 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_i,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第18张$ 到达新的结点后，小桥必须选用一个序号更大的符文石（即某个 $蓝桥杯【第15届省赛】Python B组 32.60 分,t_j,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第19张$ 满足 j > i）前往下一个结点。同理，小桥抵达之后，小蓝需要选择一个序号 k > j 的符文石 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_k,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第20张$ 继续他们的巡游。

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

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

你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样的序列形式为 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_{i_i}, t_{i_2}, s_{i_3}, t_{i_4}, \cdots,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第21张$ ，其中序列索引满足 $蓝桥杯【第15届省赛】Python B组 32.60 分,i_1 i_2 i_3 i_4 \cdots,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第22张$ ，并且序列中每一对相邻的符文石都至少包含一个共鸣元素。

【输入格式】

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

第二行包含 N 个整数 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_1, s_2, \cdots, s_N,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第16张$ ，相邻整数之间使用一个空格分隔，表示小蓝的符文石上刻有的数字符号。

第三行包含 N 个整数 $蓝桥杯【第15届省赛】Python B组 32.60 分,t_1, t_2, \cdots, t_N,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第17张$ ，相邻整数之间使用一个空格分隔，表示小桥的符文石上刻有的数字符号。

【输出格式】

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

【样例】

输入

输出

说明

126 393 581 42 44

204 990 240 46 52

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

$蓝桥杯【第15届省赛】Python B组 32.60 分,s_1,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第25张$ (126) → $蓝桥杯【第15届省赛】Python B组 32.60 分,t_3,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第26张$ (240) → $蓝桥杯【第15届省赛】Python B组 32.60 分,s_4,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第27张$ (42) → $蓝桥杯【第15届省赛】Python B组 32.60 分,t_5,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第28张$ (52)

这里，数字 2 作为共鸣元素连接了 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_1,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第25张$ 和 $蓝桥杯【第15届省赛】Python B组 32.60 分,t_3,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第26张$ 、 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_4,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第27张$ 和 t $蓝桥杯【第15届省赛】Python B组 32.60 分,t_5,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第28张$ ，数字 2、4 作为共鸣元素连接了 $蓝桥杯【第15届省赛】Python B组 32.60 分,t_3,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第26张$ 和 $蓝桥杯【第15届省赛】Python B组 32.60 分,s_4,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第27张$ 。

【评测用例规模与约定】

30%	$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq N \leq 10^3, 1 \leq s_i, t_i \leq 10^5,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第35张$
100%	$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq N \leq 10^5, 1 \leq s_i, t_i \leq 10^9,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第36张$

【解析及代码】

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

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

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

import bisect
class 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  
 
 
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

满足条件的城市对有

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

【评测用例规模与约定】

30%

$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq N \leq 10^3, 1 \leq M \leq \min(2 \times 10^3, \frac{N \times (N-1)}{2}),,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第37张$

$蓝桥杯【第15届省赛】Python B组 32.60 分,1\leq L \leq R \leq 10^5, 1 \leq u, v \leq N, u \neq v, 1 \leq w \leq 10^5,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第38张$

100%

$蓝桥杯【第15届省赛】Python B组 32.60 分,1 \leq N \leq 10^5, 1 \leq M \leq \min(2 \times 10^5, \frac{N \times (N-1)}{2}),,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第39张$

$蓝桥杯【第15届省赛】Python B组 32.60 分,1\leq L \leq R \leq 10^9, 1 \leq u, v \leq N, u \neq v, 1 \leq w \leq 10^9,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第40张$

【解析及代码】

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

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

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

例如对于 dset = [0, 0, 1, 3, 2]，结点 0,1,2,4 处于同一棵树内，结点 3 则独自构成一棵树。而结点 0,1,2,4 两两之间连通，所以这棵树贡献了 $蓝桥杯【第15届省赛】Python B组 32.60 分,\frac{v(v+1)}{2}|_{v=4},词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第41张$ 个城市对，而第二颗树无贡献

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

dset[0] == 0：跳过
dset[1] != 1：dset[1] = dset[dset[1]] = dset[0] = 0
dset[2] != 2：dset[2] = dset[dset[2]] = dset[1] = 0
dset[3] == 3：跳过

dset[4] != 4：dset[4] = dset[dset[4]] = dset[2] = 0

从而使得 dset 转变为 [0, 0, 0, 3, 0]，使用 Counter 统计每棵树的结点数量 (筛除只有 1 个结点的)，根据结点数 v 累加 $蓝桥杯【第15届省赛】Python B组 32.60 分,\frac{v(v+1)}{2},词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,访问,方法,第42张$ 即可

from collections import Counter
n, m, l, r = map(int, input().split())
class DisjointSet(list):
    def __init__(self):
        # s.j.: self[i]  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