文章目录
- 习题
- 1.抓猪拿国一
- 2.蓝桥字符
- 3.蓝桥大使
- 4.拳头对决
- 5.未来竞赛
- 6.备份比赛数据
习题
比赛地址
1.抓猪拿国一
- 十分简单的签到题
print(sum(list(range(17))))
2.蓝桥字符
- 常见的字符匹配的问题，是一个
二维dp的问题，转化为对应的动态规划求解
力扣的相似题目
可以关注灵神的讲解
import os
import sys# 请在此输入您的代码# 动态规划的问题
s = input()
n = len(s)
# 定义dp[i][j]表示为lan [:i] 在 s[:j]中出现的次数
dp = [[0]*(n+1) for _ in range(4)]
s1 = "lan"
# 初始化dp[0][i] = 1
for i in range(n+1):dp[0][i] = 1
for i in range(3):for j in range(n):if s1[i] == s[j]:dp[i+1][j+1] = dp[i+1][j] + dp[i][j]else:dp[i+1][j+1] = dp[i+1][j]
print(dp[-1][-1])
- 另一种思路，使用前缀的思路
3.蓝桥大使
- 考察的知识点是：
排序+贪心 - 可以看到最后总共求解的是
总共的最大值，那么我们可以先安排其中一方先选，另一方后选 - 在这里，我们让小蓝先选，那么小蓝应该选哪些元素？
贪心化的思路：选对应的下标中A[i]-B[i]差距最大的那些元素，这样的话，才可以发挥小蓝这边的优势
n = int(input())
A,B = [],[]
cha = []
for i in range(n):a,b = map(int,input().split())A.append(a)B.append(b)cha.append([a-b,i])
# 贪心化做法，排序，将A-B的结果作差，由小蓝先选
# 降序排序
ans = 0
cha.sort(reverse=True)
for j in range(n):if j <= n//2 -1:ans += A[cha[j][1]]else:ans += B[cha[j][1]]
print(ans)
4.拳头对决
- 题目有坑：
不是1v1,并且蓝队和红队的对应的A，B要区别好 - 题目的问题就转化为这个
如何在一个区间内，求解出小于A[i]的B[j]的个数？，在这里，就用到这个树状数组这一个工具
推荐大家先完成力扣的几个相关的知识，先感受一下
树状数组的功能与作用
相关的博客
- 要学会适应在大范围的时候，离散化这个数值再使用这个树状数组，并且到底求解的是
正序对还是逆序对，对应的排序是升序还是降序得区分好 - 一般都要使用
离散化，开的Tree的大小就得是离散化之后N的大小
N = int(input())
# 蓝队的是 A
A = list(map(int, input().split()))
# 红队的是B
B = list(map(int, input().split()))A.sort()
vis = set()
for i in A:vis.add(i)
for j in B:vis.add(j)
C = sorted(vis)
mat = {v:i+1 for i,v in enumerate(C)}
tree = [0]*(len(C)+1)
def update(i,val):while i < len(tree):tree[i] += vali += i & -i
def query(i):tmp = 0while i > 0:tmp += tree[i]i -= i & -i return tmp
ans = 0
for i in range(N):update(mat[B[i]],1)rank = mat[A[i]]ans += query(rank-1)
print(ans)
5.未来竞赛
- 这题的考点在于,由于每一个国家都是独立的，所以考虑使用
乘法定理，我们按照国家将选手分类，然后得出每一个国家的方案数，最后再使用乘法定理乘起来，减去全为0的情况 - 对于一个国家来说，
至多选两个，那么就是一个也不选+只选两个+选两个距离<=D的
from collections import defaultdict
# 直接暴力求解
N,D = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
# 先把这个选手按照国家进行分类
store = defaultdict(list)
for i,c in enumerate(A):store[c].append(i)
ans = 1# 使用乘法定理进行求解
for country in store:tmp = 1 + len(store[country])if len(store[country]) > 1:# 开始计算这个a = store[country]n = len(a)for i in range(n-1):for j in range(i+1,n):if abs(a[j]-a[i])<=D:tmp += 1ans = ans * tmp % mod
print(ans-1)
-
上面的代码只能通过
90%,总的来说，时间复杂度较高，在于这个求解选两个方案的时候，使用了两层循环，那么是否可以优化？可以，使用排序+二分即可 -
说到二分，这里还得学会使用
python中现成的bisect模块，区分其中的bisect_left和bisect_right的用法，以及他们对应的四个参数的设置 -
使用
bisect_right
from collections import defaultdict
import bisectmod = 10 ** 9 + 7
n, dd = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(list)for i in range(n): # 存每个国家的位置d[a[i]].append(i)ans = 1
for i in d.keys(): # 每个国家单独处理cnt = len(d[i]) + 1 # 空集情况 + 装1个监控的情况for j in range(len(d[i])):# cnt = (cnt + check(d[i], j)) % mod# cnt = (cnt + bisect_right(d[i],d[i][j]+dd,lo=j)-j-1) % modtarget = d[i][j] + dd pos = bisect.bisect_right(d[i], target, lo=j)cnt += pos - j - 1ans = (ans * cnt) % mod
print(ans - 1) # 减去全部空集的一种情况
- 使用
bisect_left
from collections import defaultdict
import bisectmod = 10 ** 9 + 7
n, dd = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(list)for i in range(n): # 存每个国家的位置d[a[i]].append(i)ans = 1
for i in d.keys(): # 每个国家单独处理cnt = len(d[i]) + 1 # 空集情况 + 装1个监控的情况for j in range(len(d[i])):target = d[i][j] + dd + 1pos = bisect.bisect_left(d[i], target, lo=j)cnt += pos - j - 1ans = (ans * cnt) % mod
print(ans - 1) # 减去全部空集的一种情况
6.备份比赛数据
- 典型的二分问题，因为这个 每天的备份时间与总的备份天数存在一个单调的关系
import os
import sys
# 请在此输入您的代码
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 二分
def check(x):cnt = 0pre = 0for i,j in zip(a[:-1], b[:-1]):if pre<i:pre = xcnt += 1pre-=iwhile pre-j<0:pre += xcnt += 1pre-=jif pre<a[-1]:cnt+=1return cnt <= m
l = max(a)
r = 3600
ans = -1
while l <= r:mid = (l + r) // 2if check(mid):ans = midr = mid - 1else:l = mid + 1
print(ans)
