第三年蓝球杯，感觉题目比往年简单多了。题量合适够我这种菜鸟解答… …
大概可能有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 False
def jin_s(x, m):
res = []
while x:
res.append(x%m)
x //= m
return sum(res), res
def main():
res = 0
for i in range(1, 2025):
if check(i):
res += 1
print(res, '**************')
# 63
if __name__ == '__main__':
main()试题 B: 数字串个数（满分）
本题总分：5 分 【问题描述】 小蓝想要构造出一个长度为 10000 的数字字符串，有以下要求： 1) 小蓝不喜欢数字 0 ，所以数字字符串中不可以出现 0 ； 2) 小蓝喜欢数字 3 和 7 ，所以数字字符串中必须要有 3 和 7 这两个数字。 请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其 对 109 + 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]) # 157509472
if __name__ == '__main__':
main()
试题 C: 连连看（满分）
时间限制: 10.0s 内存限制: 512.0MB 本题总分：10 分 【问题描述】 小蓝正在和朋友们玩一种新的连连看游戏。在一个 n × m 的矩形网格中， 每个格子中都有一个整数，第 i 行第 j 列上的整数为 Ai, j 。玩家需要在这个网 格中寻找一对格子 (a, b) − (c, d) 使得这两个格子中的整数 Aa,b 和 Ac,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 sys
def 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 sys
from datetime import datetime, timedelta # 时间类、时间差值类
def main():
input = lambda: sys.stdin.readline().strip()
start = datetime(1970, 1, 1, 0, 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 sys
def 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, res
def 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 到 109 之间的数字符号。小蓝的符文石集合标记为 s1, s2, . . . , sN， 小桥的则为 t1, t2, . . . , tN。 两位魔法使者的任务是通过使用符文石，在各个时空结点间巡游。每次巡 游遵循这样一条法则：当小蓝使用了符文石 si 到达新的结点后，小桥必须选用 一个序号更大的符文石（即某个 tj 满足 j > i）前往下一个结点。同理，小桥抵 达之后，小蓝需要选择一个序号 k > j 的符文石 sk 继续他们的巡游。 为了成功地穿梭时空，两个连续使用的符文石上的数字符号必须有共鸣， 这种共鸣只有当数字符号中至少包含一个特定的元素——星火（数字 0）、水波 （数字 2）或者风语（数字 4）时，才会发生。例如，符号序列 126, 552, 24, 4 中 的每对连续符文都包含了至少一个共鸣元素，则它们是一系列成功的巡游；而 如果是 15, 51, 5，则不成立，因为它们之间的共鸣元素不包含星火、水波或风语 中的任意一个。 小蓝总是先启程，使用他的符文石开启巡游。 你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样 的序列形式为 si1 , ti2 , si3 , ti4 , . . .，其中序列索引满足 i1 < i2 < i3 < i4 < . . .，并且序 列中每一对相邻的符文石都至少包含一个共鸣元素。对于所有评测用例，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
直接二分查找,交替找第一个大于上一块石头下标就行了… …
真简单，大无语事件因为字多不想看… …
import re
import bisect
def solution(A, B):
if not A: # 小蓝一个都拿不了
return 0
left = A[0] # 小蓝开始贪心拿第一个
cnt = 1 # 答案
cur_lis = B # 交替的数组，小蓝选了一个，接下来小乔选
while True:
try:
left = cur_lis[bisect.bisect(cur_lis, left)] # 不断用二分交替找第一个大于的数
cnt += 1
cur_lis = A if cur_lis is B else B
except: # 直接用异常来判断结束
return cnt
if __name__ == '__main__':
n = int(input())
# 使用re筛选含有024的符文数字
pat = re.compile('[024]')
# 把符合调节的符文下标存入待选数组
# A 为小蓝待选, B为小乔
A = [i for i, x in enumerate(input().split(), 1) if pat.search(x)]
B = [i for i, x in enumerate(input().split(), 1) if pat.search(x)]
print(solution(A, B))
试题 G: 缴纳过路费（91%分）
时间限制: 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[u]*size[v]。
但是:
虽然我熟练掌握了各种树状数组、线段树、LCA、SCC缩点、割点和割边的求法
就是忘记了并查集如何维护size，忘记了合并的时候这个 size += size该写在哪里… …
痛失20分，我还调试了一个半小时。
以下代码只能得到91%分，原因不详
import sys
def main():
input = lambda: sys.stdin.readline().strip()
def find(x):
nonlocal fa, size
if x != fa[x]:
fa[x] = find(fa[x])
return fa[x]
def merge(x, y):
nonlocal fa, size
xx, yy = find(x), find(y)
if xx == yy:
return False
fa[xx] = yy
size[yy] += size[xx]
return True
n, m, LL, RR = map(int, input().split())
size = {i: 1 for i in range(1, n + 1)}
fa = {i: i for i in range(1, n + 1)}
edges = []
for i in range(m):
u, v, w = map(int, input().split())
# 不满足的边直接筛掉
if w > RR or w < LL:
continue
edges.append((w, u, v))
ans = 0
# 并查集维护不小于某边权的集合
# 从大到小枚举,并且去除不符合条件的边
for w, u, v in sorted(edges, reverse=True):
aa, bb = find(u), find(v)
# 记录连通前两个连通块的全连接大小
temp = size[aa] * size[bb]
# 如果是第一次连接两个集合,说明该边是两个连通块的最大连接边(最贵的路)
if merge(u, v):
ans += temp
print(ans)
if __name__ == '__main__':
main()
试题 H: 纯职业小组
时间限制: 10.0s 内存限制: 512.0MB 本题总分：20 分 【问题描述】 在蓝桥王国，国王统治着一支由 n 个小队组成的强大军队。每个小队都由 相同职业的士兵组成。具体地，第 i 个小队包含了 bi 名职业为 ai 的士兵。 近日，国王计划在王宫广场举行一场盛大的士兵检阅仪式，以庆祝王国的 繁荣昌盛。然而，在士兵们入场的过程中，一场突如其来的风暴打乱了他们的 行列，使得不同小队的士兵混杂在一起，次序乱成一团， 尽管国王无法知道每个士兵的具体职业，但为了确保仪式能顺利进行，国 王打算从这些混乱的士兵中选出一部分，组成 k 个“纯职业小组”进行检阅。 一个“纯职业小组”定义为由 3 名同职业的士兵组成的队伍。 请问，国王至少需要选择多少名士兵，才能确保这些士兵可以组成 k 个 “纯职业小组”。
思路：没做这题… … 因为不甘于并查集size，调了一个半小时未放弃… …
版权声明：本文为博主作者：普通小明原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/qq_38262237/article/details/137775496
