习题
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] += val
i += i & -i
def query(i):
tmp = 0
while 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 += 1
ans = ans * tmp % mod
print(ans-1)
上面的代码只能通过
90%,总的来说，时间复杂度较高，在于这个求解选两个方案的时候，使用了两层循环，那么是否可以优化？可以，使用排序+二分即可说到二分，这里还得学会使用
python中现成的bisect模块，区分其中的bisect_left和bisect_right的用法，以及他们对应的四个参数的设置使用
bisect_right
from collections import defaultdict
import bisect
mod = 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) % mod
target = d[i][j] + dd
pos = bisect.bisect_right(d[i], target, lo=j)
cnt += pos - j - 1
ans = (ans * cnt) % mod
print(ans - 1) # 减去全部空集的一种情况
- 使用
bisect_left
from collections import defaultdict
import bisect
mod = 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 + 1
pos = bisect.bisect_left(d[i], target, lo=j)
cnt += pos - j - 1
ans = (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 = 0
pre = 0
for i,j in zip(a[:-1], b[:-1]):
if pre<i:
pre = x
cnt += 1
pre-=i
while pre-j<0:
pre += x
cnt += 1
pre-=j
if pre<a[-1]:
cnt+=1
return cnt <= m
l = max(a)
r = 3600
ans = -1
while l <= r:
mid = (l + r) // 2
if check(mid):
ans = mid
r = mid - 1
else:
l = mid + 1
print(ans)