蓝桥杯 刷题对应的题解

飞机降落

• 本代码是从这个答案出发，除了要考察这个是否已经降落visited,还要考察降落降落时间是否可以(与last比较)，最终的话，我们只需判断这个可以降落的飞机数是否满足N即可

# 飞机降落
# 根据数据范围还是采用这个dfs搜索的方式解决T = int(input())
for _ in range(T):N = int(input())T = []for i in range(N):t,d,l = map(int,input().split())T.append([t,d,l])# visited[i]表示i飞机已经降落visited = [False]*N# 通过搜索的方式判断是否存在一个组合可以安全降落# 需要记录哪些信息？# 当前所需下降的飞机curi,上一个飞机结束降落的时间，已经安全下降的飞机数vindef dfs(curi,last,vin):if vin == N:return True# 打算从答案的视角，当遇到这个还没降落的飞机，并且满足降落的条件for ne in range(N):if not visited[ne] and last <= T[ne][0]+T[ne][1]:visited[ne] = Truestart = 0if last <= T[ne][0]:start = T[ne][0]else:start = last# 找到满足的就需要提前返回if dfs(ne,start+T[ne][2],vin+1):return Truevisited[ne] = Falsereturn Falseflag = 0for i in range(N):if dfs(i,0,0):flag = 1breakif flag:print("YES")else:print("NO")

数位排序

• 直接暴力即可

import os
import sys# 请在此输入您的代码# 感觉暴力即可，就是存储的时候设置这个优先级n = int(input())
store = []
for i in range(1,n+1):s = list(map(int,list(str(i))))sumnum = sum(s)store.append([sumnum,i])
store.sort(key = lambda x:(x[0],x[1]))
m = int(input())
print(store[m-1][1])

最长不下降子序列

import sysinput = lambda: sys.stdin.buffer.readline().rstrip()maxn = 100010
b = [0] * maxn
dp = [0] * maxn
tree = [0] * (maxn * 4)#权值线段树，维护dp数组，不需要初始化
#更新下标为x，与val取max
def update(o, l, r, x, val):if l == r:tree[o] = max(tree[o], val)returnmid = (l + r) >> 1if x <= mid:update(o << 1, l, mid, x, val)else:update(o << 1 | 1, mid + 1, r, x, val)tree[o] = max(tree[o << 1], tree[o << 1 | 1])#查询区间[L,R]最大值
def query(o, l, r, L, R):if L <= l and r <= R:return tree[o]mid = (l + r) >> 1ans = 0if L <= mid:ans = max(ans, query(o << 1, l, mid, L, R))if R > mid:ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R))return ansn, k = list(map(int, input().split()))
a = list(map(int, input().split()))
if n == k:print(n)
else:#离散化S = set(a)    #去重b = list(S)   #排序tot = len(b)b.sort()for i in range(len(a)):left, right, ans = 0, tot - 1, -1while left <= right:mid = (left + right) >> 1if b[mid] >= a[i]:ans = midright = mid - 1else:left = mid + 1a[i] = ans + 1a = [0, *a]ans = 0#从前往后遍历a，放入权值线段树中for i in range(1, n + 1):dp[i] = query(1, 1, tot, 1, a[i]) + 1update(1, 1, tot, a[i], dp[i])#重新清空权值线段树tree = [0] * (maxn * 4)for i in range(n, k, -1):#a[i-k+1] ... a[i]相等 均等于a[i-k]#最后一段要注意：查询的是[a[i-k],tot]中的最大值ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1)tmp = query(1, 1, tot, a[i], tot) + 1ans = max(ans, tmp + k)update(1, 1, tot, a[i], tmp)print(ans)