蓝桥杯30天-chls学算法

本文最后更新于：2025年3月18日 晚上

3.12 三十

2暴力 + 2贪心

总算没再摆烂，不过题目还是要问问豆包，才能理解，过几天重写一遍题目再试试

3.13 二十九

6 简单

贪心排序，其实就是排序

406. 根据身高重建队列 - 力扣（LeetCode）

1
2
3
4
5
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

# 先按子列表的第一个元素降序排序，当第一个元素相等时，再按第二个元素升序排序。
# 输出: [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
people.sort(key = lambda x: (-x[0], x[1]))

贪心，但是我感觉就是排序，可能这俩就经常结合着用吧

3074. 重新分装苹果 - 力扣（LeetCode）

排序 + 贪心

2279. 装满石头的背包的最大数量 - 力扣（LeetCode）

1
2
# 算两数组对应位置之差
chak = [a - b for a, b in zip(capacity, rocks)]

这玩意，力扣第一题吗，

可暴力

可哈希 + 前缀

1. 两数之和 - 力扣（LeetCode）

1
2
3
d = {} # 字典
d[11] = 0 # 就是 d = {11: 0}
d[7] = 1 # 就是 d 变为 {11: 0, 7: 1}。

前缀和

P8218 【深进1.例1】求区间和 - 洛谷

洛谷的IDE感觉有点小麻烦

emmm，纯史来的

二分查找 & bisect库

P2249 【深基13.例1】查找 - 洛谷

这个题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from bisect import *
import sys
input = lambda: sys.stdin.readline().strip()
n, m = map(int, input().split())
nums = list(map(int, input().split()))
Q = list(map(int, input().split()))

s = set(nums) # nums 构成的集合，如果待查询数组 q not in s，直接返回-1
for q in Q:
    if q not in s: 
        print(-1, end = " ")
    else: # q 一定出现在 nums 中, 利用技巧将“大于等于 x”转化成“大于 x-1”
        print(bisect(nums, q - 1) + 1, end = " ")
        
        
# 但是你要直接写：
# for q in Q:
#    if q not in nums:  
#          ……
# 就会报错，TLE，要先s = set(nums)，转换成集合
# 因为使用 if q not in nums: 来判断元素是否在列表 nums 中。列表的 in 操作符需要遍历整个列表，其时间复杂度为O(n)
# 而集合在 Python 中是基于哈希表实现的，其查找元素的时间复杂度为 O(1)（平均情况下）。这意味着无论集合的大小如何，查找元素所需的时间基本保持不变。

3.14 二十八

坏，今天怎么感觉激情减退力

莫斯，我直接去写题去

二分-中等

二分主要就是它边界的问题，一定要搞清楚

2563. 统计公平数对的数目 - 力扣（LeetCode）

二分-中等

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

3.15 二十七

草了wd，摆了一天

我再也不考虑宿舍学习了😭

3.16 二十六

library！

3 二分

二分答案 模板：代码模板 (Python) - Open Wiki Community

“二分答案” 这个名称源于其核心的解题思路，即通过二分法来枚举答案并判断其是否可行。

具体来说，在面对一个问题时，如果能够确定答案所在的范围，并且这个范围具有单调性（例如随着某个变量的增加，答案要么单调递增要么单调递减），就可以使用二分答案的方法。

它就像在一个有序的 “答案序列” 中进行查找，每次都取中间的那个值作为尝试答案，然后根据这个答案是否满足问题的条件来决定是继续在左半部分还是右半部分寻找，不断将答案的范围缩小一半，直到找到满足条件的最优答案。这种将答案空间不断二分以逼近正确答案的方式，就如同在有序数组中进行二分查找元素一样，所以被称为 “二分答案”。例如，在一些求满足某种条件下的最大（小）值问题中，通过二分答案可以高效地找到符合条件的最值。

二分答案

2226. 每个小孩最多能分到多少糖果 - 力扣（LeetCode）

二分答案

3.冶炼金属 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
a, b = zip(*[map(int, input().split()) for _ in range(n)])

def bisect(lo, hi, check):
    while lo < hi:
        i = (lo + hi) // 2
        if check(i):
            hi = i
        else:
            lo = i + 1
    return lo

# 恰好不存在A // v > B，即是恰好存在A // v <= B
def check_min(v):
    return all(A // v <= B for A, B in zip(a, b))

# 恰好存在A // v < B
def check_max(v):
    return any(A // v < B for A, B in zip(a, b))

m = bisect(1, 10**9, check_min)
M = bisect(1, 10**9, check_max) - 1
print(m, M)

1.分巧克力 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import os
import sys
 
# 请在此输入您的代码
 
h = [0] * 100000
w = [0] * 100000
 
def check(a):
    num = 0  # 记录分成长度为 a 的巧克力数量
    for i in range(n):
        num += (w[i] // a) * (h[i] // a)  # 每一大块可以分成的边长为 a 的巧克力数量
        if num >= k:
            return True  # 大于要求数量，返回真
    return False
 
n, k = map(int, input().split())
for i in range(n):
    h[i], w[i] = map(int, input().split())
 
l, r = 1, 100000
while l < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid + 1
    else:
        r = mid
 
print(r - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import os
import sys

##h = [0] * 100000
##w = [0] * 100000
 
def check(a):
    num = 0  # 记录分成长度为 a 的巧克力数量
    for h, w in c:
        num += (h // a) * (w // a)  # 每一大块可以分成的边长为 a 的巧克力数量
        if num >= k:
            return True  # 大于要求数量，返回真
    return False
 
n, k = map(int, input().split())
##for i in range(n):
##    h[i], w[i] = map(int, input().split())

c = [list(map(int, input().split())) for _ in range(n)]
 
l, r = 1, 100000
while l < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid + 1
    else:
        r = mid
 
print(r - 1)

3.17 二十五

md改成倒计时，急迫感一下就上来了😭

二分

730. 机器人跳跃问题 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def check(x):
    for i in range(n):
        x = 2*x - h[i]
        if x < 0:
            return False
    return True

n = int(input())
h = list(map(int, input().split()))

l, r = 0, 100000
while l < r:
    mid = (l + r) // 2
    if check(mid):
        r = mid
    else:
        l = mid + 1

print(l)

二分吗？暴力吧

1221. 四平方和 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
import math
import sys # 第一次用到它

n = int(input())

for i in range(int(math.sqrt(n // 4)) + 1):
    for j in range(int(math.sqrt((n - i*i) // 3)) + 1):
        for k in range(int(math.sqrt((n - i*i - j*j) // 2)) + 1):
            z = int(math.sqrt(n - i*i - j*j - k*k))
            if n == z*z + i*i + j*j + k*k:
                print(i, j , k, z)
                sys.exit()  # 直接终止整个程序

暴力

4.最少刷题数 - 蓝桥云课

BFS

695. 岛屿的最大面积 - 力扣（LeetCode）

3.18 二十四

都怪牢宇，光聊天

贪心

1963. 使字符串平衡的最小交换次数 - 力扣（LeetCode）

暴力

2614. 对角线上的质数 - 力扣（LeetCode）

#蓝桥杯，算法
蓝桥杯30天-chls学算法
http://viper2383.github.io/2025/03/12/蓝桥杯30天-chls学算法/
作者
w1per3
发布于
2025年3月12日
许可协议