cin = lambda: list(map(int, input().split()))for _ in range(int(input())): n, k = cin() cnt = Counter() for i in range(n): a, b = cin() cnt[a] += b if sum(c // 3 for c in cnt.values()) < k: print(-1) continue ans = 0 for c in cnt.values(): if c % 3 == 0: ans += c - 1 k -= c // 3 - 1 elif c % 3 == 1: if c == 1: ans += 1 else: ans += c - 2 k -= c // 3 - 1 else: ans += c k -= c // 3 if k <= 0: print(ans - k * 3) break else: print(ans + k)
测试样例
样例一
输入：
23 21 32 33 33 51 32 33 3
输出：
8-1
样例二
输入：
16 601 1002 433 511 322 553 98
输出：
274
最后
今年蓝桥杯省赛的成绩终于出来了，居然是河北省B组第一名哈哈哈~
可惜的是不知道具体多少分😥
最后祝大家都能蓝桥杯榜上有名，心想事成🤪❤️！！！！
有什么问题欢迎在评论区留言。
最后输出序列最大值即可。并查集、
代码
cin = lambda: list(map(int, input().split()))n, m, l, r = cin()e = [set() for _ in range(n + 1)]# s[i] == i 表示 i 为新点，sz[i] 表示新点 i 的大小s, sz = list(range(n + 1)), [1] * (n + 1)def find(x): if s[x] == x: return x s[x] = find(s[x]) return s[x]edges = [cin() for _ in range(m)]for u, v, w in edges: if w > r: continue su, sv = find(u), find(v) if w < l: # 合并 s[su] = sv sz[sv] += sz[su]# 以新点建图for u, v, w in edges: if l <= w <= r: su, sv = find(u), find(v) e[su].add(sv) e[sv].add(su)vis = [False] * (n + 1)def dfs(u, block): # block 保存新点，返回值表示总大小 block.append(u) res, vis[u] = sz[u], True for v in e[u]: if vis[v]: continue res += dfs(v, block) return resans = 0for i in range(1, n + 1): if s[i] == i and not vis[i]: block = [] t = dfs(i, block) for u in block: ans += sz[u] * (t - sz[u])print(ans // 2)
ans = 0def check(x): # 判断是否符合条件 s1, s2 = sum(int(i) for i in bin(x)[2:]), 0 while x: s2 += x % 4 x //= 4 return s1 == s2for i in range(1, 2025): ans += check(i)print(ans) # 63
怎么实现缩点呢？并查集！将所有小于 L 的边连接的点用并查集来合并，让集合的根作为合并后的新点。(3, 5)。再往后的村民的断言真假都可以通过前面的断言真假推断出来。(3, 4)、真话和后面的村民的断言为假话、
再往后就是之前的重复了。
代码
for _ in range(cin(0)): n = int(input()) print(n * (1 + (n % 3 == 0)))
F：魔法巡游
考察：哈希表、
代码
cin = lambda: list(map(int, input().split()))n, s, t = int(input()), cin(), cin()dig1, dig2 = defaultdict(int), defaultdict(int)digs = ('0', '2', '4')for i in range(n): num1, num2 = str(s[i]), str(t[i]) d1, d2 = dict(dig1.items()), dict(dig2.items()) for d in digs: if d in num2 and d in d1: dig2[d] = max(dig2[d], d1[d] + 1) for d in digs: if d in num1: if d in d2: dig1[d] = max(dig1[d], d2[d] + 1) else: dig1[d] = 1print(max(max(dig1[d], dig2[d]) for d in digs))
n, m = map(int, input().split())a = [list(map(int, input().split())) for _ in range(n)]ans = 0for i in range(1, n): # 枚举左上方向 for j in range(1, m): for k in range(1, min(i, j) + 1): if a[i][j] == a[i - k][j - k]: ans += 2for i in range(n - 1): # 枚举左下方向 for j in range(1, m): for k in range(1, min(n - i, j + 1)): if a[i][j] == a[i + k][j - k]: ans += 2print(ans)
测试样例
样例一
输入：
3 21 22 33 2
输出：
6
样例二
输入：
3 33 2 32 3 23 2 3
输出：
20
D：神奇闹钟
考察：时间处理
解题思路
可以使用 Python 标准库中的 datetime 模块来解决此题。DP
解题思路
用一个哈希表统计上一个包含 '0'、'4' 的符石作为序列末尾的最长序列长度。(1, 5)、比如点 A 是由 3 个旧点合并而来，与其连通的有 2 个新点，对应 5 个旧点，那么以 A 为第一个坐标的点对就有 3 x (8 - 3) 对。DFS
解题思路
分析：由于要满足路径中最贵的一次收费在 [L, R] 区间内，所以收费大于 R 的路径是一定不可以经过的，而对于收费小于 L 的路径可以经过，但是不能让整条路径的收费全部小于 L，要不然路径的最大值也小于 L 了。右上、
注意累加的点对有重复（(1, 2)、不知道是不是为了照顾参赛的选手水平。
然后再搜索满足条件的点对的数量，比如：有 3 个点缩成的点 A 和 2 个点缩成的点 B 之间有一条 [L, R] 之间的边，那么就有 2 x 3 = 6 个点对。右下四个方向。
对此，我们要：将所有小于 L 的边连接的点缩成一个点（缩点），并记录缩后的点数（就是记录有多少个点缩成了这一个点），大于 R 的边则直接舍弃（不加到图中）。
