第三年蓝球杯，感觉题目比往年简单多了。题量合适够我这种菜鸟解答... ...
大概可能有45分，希望进省一大三最后i一次机会了55555
试题 A: 穿越时空之门
本题总分：5 分 【问题描述】 随着 2024 年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘 的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。 在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数 位之和。 在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示 中各数位之和。 穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等 同于四进制领域的力量时，他才能够成功地穿越。 国王选定了小蓝作为领路人，带领着力量值从 1 到 2024 的勇者们踏上了这 段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这 2024 位勇者中，有多少人符合穿越时空之门的条件。思路：进制转换... ...
答案：63
多此一举的输出纯粹怕粗心。
def check(a): jin_2, x2 = jin_s(a, 2) jin_4, x4 = jin_s(a, 4) print(a, x2, x4) if jin_2 == jin_4: return True return Falsedef jin_s(x, m): res = [] while x: res.append(x%m) x //= m return sum(res), resdef main(): res = 0 for i in range(1, 2025): if check(i): res += 1 print(res, '**************')# 63if __name__ == '__main__': main()试题 B: 数字串个数
本题总分：5 分 【问题描述】 小蓝想要构造出一个长度为 10000 的数字字符串，有以下要求： 1) 小蓝不喜欢数字 0 ，所以数字字符串中不可以出现 0 ； 2) 小蓝喜欢数字 3 和 7 ，所以数字字符串中必须要有 3 和 7 这两个数字。 请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其 对 10 9 + 7 取余后的结果。思路：第一反应先构造长度2-4，模拟找规律。发现DP即可
答案：157509472
def main(): n = 10000 p = int(1e9 +7) dp = [[[0] * 2 for i in range(2)] for j in range(n+1)] # 前缀指的是不包括当前字符串的前子串 # 状态为[当前str长度][前缀是否有3][前缀是否有7] # 边界 dp[1][0][0] = 7 # 没有3和7,只能是除37的其它七种方案 dp[1][0][1] = 1 # 有3,一种方案 dp[1][1][0] = 1 # 有7,一种方案 dp[1][1][1] = 0 # 有3和7,不可能(长度为1不可能同时出现37) # 枚举阶段,决策为当前i位置填什么字符 for i in range(2, n+1): # 状态转移 dp[i][0][0] = (dp[i-1][0][0] * 7) % p # 前缀无37(当前可填7种1、2、4、5、6、8、9) dp[i][0][1] = (dp[i-1][0][1] * 8 + dp[i-1][0][0]) % p # 从有7(可填8种)、和均没有(可填1种) dp[i][1][0] = (dp[i-1][1][0] * 8 + dp[i-1][0][0]) % p # 从有3(可填8种)、和均没有(可填1种) dp[i][1][1] = (dp[i-1][1][1] * 9 + dp[i-1][0][1] + dp[i-1][1][0]) % p # 从有37(可填9种)、只有3(1种)、只有7(1种)三种情况 # 答案 print(dp[n][1][1]) # 157509472if __name__ == '__main__': main()试题 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 的矩形网格中有多少对 这样的格子满足条件。 对于所有评测用例，1 ≤ n, m ≤ 1000 ，1 ≤ Ai, j ≤ 1000 。 目标算法O(n^2)思路：对于每个元素,判断对‘X’型方向上有无相同元素。
因为矩阵斜行的下标满足 (i+j)%2000和(i-j)%2000是相等的，参考八皇后问题。 所以可用二维哈希 [斜行][元素值]。import sysdef main(): input = lambda: sys.stdin.readline().strip() # 快读 n, m = map(int, input().split()) maps = [] hax0 = [[0]*1001 for i in range(2001)] # 斜行=> '\' hax1 = [[0]*1001 for i in range(2001)] # 斜行=> '/' for i in range(n): maps.append(list(map(int, input().split()))) # 记录这一斜行每个元素出现次数 for j, x in enumerate(maps[-1]): hax0[(i-j) % 2000][x] += 1 hax1[(i+j) % 2000][x] += 1 res = 0 for i in range(n): for j in range(m): ai = maps[i][j] # 因为要排除自己,所以需要大于1才行,还需要-1。 # 例如当前斜行有2个相等元素,有一个是自己,所以只能配成一对 if hax0[(i-j) % 2000][ai] > 1: res += hax0[(i-j) % 2000][ai] - 1 if hax1[(i+j) % 2000][ai] > 1: res += hax1[(i+j) % 2000][ai] - 1 print(res)if __name__ == '__main__': main()试题 D: 神奇闹钟
时间限制: 10.0s 内存限制: 512.0MB 本题总分：10 分 【问题描述】 小蓝发现了一个神奇的闹钟，从纪元时间（1970 年 1 月 1 日 00:00:00 ）开 始，每经过 x 分钟，这个闹钟便会触发一次闹铃（纪元时间也会响铃）。这引起 了小蓝的兴趣，他想要好好研究下这个闹钟。 对于给出的任意一个格式为 yyyy-MM-dd HH:mm:ss 的时间，小蓝想要 知道在这个时间点之前（包含这个时间点）的最近的一次闹铃时间是哪个时间？ 注意，你不必考虑时区问题。 对于所有评测用例，1 ≤ T ≤ 10，1 ≤ x ≤ 1000，保证所有的时间格式都是 合法的。 目标复杂度应该要(9999年-1970年，以间隔迭代肯定超时，所以不能迭代)思路：datetime库，就用了两个最简单的类函数进行拼凑。
import sysfrom datetime import datetime, timedelta # 时间类、时间差值类def main(): input = lambda: sys.stdin.readline().strip() start = datetime(1970, 1, 1, 0, 0) for i in range(int(input())): aa, bb, mmm = input().split() n, y, r = map(int, aa.split('-')) s, f, m = map(int, bb.split(':')) # 和秒没有关系,因为从0:0:0开始,又是整数间隔分钟 # 实例化当前时间 now = datetime(n, y, r, s, f, 0) # 到目前的差值时间 diff = now - start # 计算差值时间的 (mod 间隔)的余数 totmins = int(diff.total_seconds())//60%int(mmm) # 把当前时间前移 差值对间隔余多少分钟 print(str(now-timedelta(minutes=totmins)))if __name__ == '__main__': main()试题 E: 蓝桥村的真相
时间限制: 10.0s 内存限制: 512.0MB 本题总分：15 分 【问题描述】 在风景如画的蓝桥村，n 名村民围坐在一张古老的圆桌旁，参与一场思想 的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要 么是无可救药的说谎者。 当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流 发言，编号为 i 的村民提出了这样的断言：坐在他之后的两位村民——也就是 编号 i + 1 和 i + 2 （注意，编号是环形的，所以如果 i 是最后一个，则 i + 1 是 第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。 在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？ 请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中， 说谎者的总数。 对于所有评测用例，1 ≤ T ≤ 105，3 ≤ n ≤ 1018。 目标算法需要O(T)或者O(Tlogn)思路：刚开始没思路，先写个暴力找规律(因为数据范围2<=n<=10e18)，必须公式或者log。
然后发现，n是3的倍数答案就是n*2，不是3的倍数答案就是n本身
import sysdef check(n, xxxxx): """ 检查该排列是否符合要求 :param n: :param xxxxx: 用来拆分的数 :return: """ # 拆分二进制,枚举集合状态 lis = [] while xxxxx: lis.append(xxxxx%2) xxxxx //= 2 res = [0] *(n-len(lis)) + lis # 不够长的补0 # 扩大一倍,解决环的问题 lis = res * 2 for i in range(n): if lis[i] == 1: if lis[i+1] ^ lis[i+2] == 0: return False, res else: if lis[i+1] ^ lis[i+2] == 1: return False, res return True, resdef sol(n): """ 这是用来暴力找规律的 """ ans = 0 for i in range((2**n)): flag, lis = check(n, i) if flag: print(lis) ans += lis.count(0) print(n%3, n, ans, "***************"*5)def main(): input = lambda: sys.stdin.readline().strip() t = int(input()) # 用来暴力的 # for n in range(3, 22): # sol(n) for i in range(t): n = int(input()) if n%3 == 0: print(n*2) else: print(n)if __name__ == '__main__': main()试题 F: 魔法巡游
时间限制: 10.0s 内存限制: 512.0MB 本题总分：15 分 【问题描述】 在蓝桥王国中，两位魔法使者，小蓝与小桥，肩负着维护时空秩序的使命。 他们每人分别持有 N 个符文石，这些石头被赋予了强大的力量，每一块上都刻 有一个介于 1 到 10 9 之间的数字符号。小蓝的符文石集合标记为 s 1 , s 2 , . . . , s N ， 小桥的则为 t 1 , t 2 , . . . , t N 。 两位魔法使者的任务是通过使用符文石，在各个时空结点间巡游。每次巡 游遵循这样一条法则：当小蓝使用了符文石 s i 到达新的结点后，小桥必须选用 一个序号更大的符文石（即某个 t j 满足 j > i ）前往下一个结点。同理，小桥抵 达之后，小蓝需要选择一个序号 k > j 的符文石 s k 继续他们的巡游。 为了成功地穿梭时空，两个连续使用的符文石上的数字符号必须有共鸣， 这种共鸣只有当数字符号中 至少包含一个 特定的元素——星火（数字 0 ）、水波 （数字 2 ）或者风语（数字 4 ）时，才会发生。例如，符号序列 126 , 552 , 24 , 4 中 的每对连续符文都包含了至少一个共鸣元素，则它们是一系列成功的巡游；而 如果是 15 , 51 , 5 ，则不成立，因为它们之间的共鸣元素不包含星火、水波或风语 中的任意一个。 小蓝总是先启程，使用他的符文石开启巡游。 你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样 的序列形式为 s i 1 , t i 2 , s i 3 , t i 4 , . . . ，其中序列索引满足 i 1 < i 2 < i 3 < i 4 < . . . ，并且序 列中每一对相邻的符文石都至少包含一个共鸣元素。 对于所有评测用例，1 ≤ N ≤ 105，1 ≤ si , ti ≤ 109。 目标复杂度 O(N) 或者 O(N logN)思路：题目太多字了，没看这题
赛后补题 例如：
126 393 581 42 44
204 990 240 46 52
贪心的话直接选择第一个满足的就行了，所以难点就是快速找满足条件的第一个
两组满足条件的下标入数组
1 4 5
1 2 3 4 5
直接二分查找,交替找第一个大于上一块石头下标就行了... ...
真简单，大无语事件因为字多不想看... ...
试题 G: 缴纳过路费
时间限制: 10.0s 内存限制: 512.0MB 本题总分：20 分 【问题描述】 在繁华的商业王国中，N 座城市被 M 条商路巧妙地连接在一起，形成了一 个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最 多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过 商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。 有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝 眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费 总和，而是这条路线上 最贵 的那一次收费。这个标准简单而直接，让他能迅速 评估出一条路线是否划算。 于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线 成本介于他心中预设的两个数 L 和 R 之间。他相信，这样的路线既不会太廉 价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。 作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。 对于所有评测用例，1 ≤ N ≤ 105，1 ≤ M ≤ min(2 × 105 , N×( 2 N−1) )，1 ≤ L ≤ R ≤ 109 ,1 ≤ u, v ≤ N, u , v，1 ≤ w ≤ 109。 还是最高nlogn复杂度思路：属实是让我给押到题了，赛前特意查缺补漏了这一篇最短路径之寻找最大边的最小值（Floyd、Dijkstra、Kruskal）_路径最大值最小-CSDN博客
所以直接kruskal，然后并查集维护连通块大小，新如果能够联通那么新增加的点对，就是连通前size的乘积。
但是:
虽然我熟练掌握了各种树状数组、线段树、LCA、SCC缩点、割点和割边的求法
就是忘记了并查集如何维护size，忘记了合并的时候这个 size += size该写在哪里... ...
痛失20分，我还调试了一个半小时。
以下代码是错的... ... 需要自行解决并查集size的问题
import sysdef main(): """ 注意这个代码是错的，比赛时写的，因为忘记了并查集维护size怎么写，调了一个半小时没写出... """ def find(x): nonlocal fa, size if x == fa[x]: return x fa[x] = find(fa[x]) size[fa[x]] += size[x] return fa[x] def merge(x, y): nonlocal fa, size xx, yy = find(x), find(y) if xx==yy: return False fa[x] = y size[y] += size[x] return True input = lambda: sys.stdin.readline().strip() n, m, l, r = map(int, input().split()) size = [1 for i in range(n +1)] fa = [i for i in range(n+1)] edges = [] for i in range(m): u, v, w = map(int, input().split()) edges.append((w, u, v)) ans = 0 for w, u, v in sorted(edges): aa, bb = find(u), find(v) if l <= w <= r: print(size[aa], size[bb], '*****') temp = size[aa] * size[bb] if merge(u, v) and l <= w <= r: ans += temp print(ans)if __name__ == '__main__': main()