蓝桥杯30天-chls学算法

本文最后更新于：2025年4月2日 晚上

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）

3.19 二十三

BFS

0长草 - 蓝桥云课

DFS

5.最大数字 - 蓝桥云课

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
import sys
input = lambda: sys.stdin.readline().strip()

N, A, B = map(int, input().split())
sN = str(N)
res = 0

def dfs(i, n, a, b):
    global res
    if i == len(sN):
        res = max(res, n)
        return
    x = int(sN[i])
    # 对于第i位，只有两种选择，执行a操作，或执行b操作
    # 对于执行a操作，计算当前数字可以进行加 1 操作的最大次数d，
    # 取9 - x（将当前数字加到 9 所需的次数）和剩余的操作 1 次数a中的较小值
    d = min(9 - x, a)
    dfs(i + 1, n * 10 + (x + d), a - d, b)

    # 例如，x=1,b=3,这时就能执行操作b，把x变成9
    if b >= x + 1:
        dfs(i + 1, n * 10 + 9, a, b - (x + 1))

dfs(0, 0, A, B)
print(res)

DFS

1.小朋友崇拜圈 - 蓝桥云课

这题牛魔的这么简单吗，感觉还是upTsingPig讲得好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10000) # 增加递归深度至少大于 n，因为 python 默认为 1000

n = int(input())
g = [0] + list(map(int, input().split()))
res = 0
d = {}

# u：当前正在访问的节点编号
# idx：当前节点 u 在 DFS 过程中的时间戳，表示这是第几次访问
def dfs(u, idx):
    global res
    # 如果 d.get(u) 不为 None，说明节点 u 之前已经被访问过，此时形成了一个环。
    if d.get(u) is not None:
        res = max(res, idx - d[u])
        return
    d[u] = idx
    dfs(g[u], idx + 1)

for u in range(1, n + 1):
    dfs(u, 1)

print(res)

3.20 二十二

时光时光慢些吧，我还什么都不会呢😭😭

枚举

1210. 连号区间数 - AcWing题库

并查集

P1551 亲戚 - 洛谷

3.21 二十一

3.22 二十

3.23 十九

3.24 十八

3.25 十七

3.26 十六

并查集 8太懂

P1536 村村通 - 洛谷

并查集

1.合根植物 - 蓝桥云课

前缀和

1.卡片 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
import os
import sys

# 前缀和
n = int(input())

ans = 0
for i in range(1, n + 1):
    ans = ans + i
    if ans >= n:
        print(i)
        break

模拟

1.裁纸刀 - 蓝桥云课

3.27 十五

3.28 十四

3.29 十三

我tmd真的是，该啊，哎

没紧迫感，总是想玩

3.30 十二

动态规划

70. 爬楼梯 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
from functools import *
class Solution:
    def climbStairs(self, n: int) -> int:
        @lru_cache(maxsize = None)
        def dfs(n):
            if n == 0 or n ==1:
                return 1
            else:
                return dfs(n - 1) + dfs(n - 2)
        return dfs(n)

动态规划

198. 打家劫舍 - 力扣（LeetCode）

选或者不选

\(f[i][1]\) 表示考虑完前 \(i\) 个屋子, 且第 \(i\) 个屋子选的最大金额

\(f[i][0]\) 表示考虑完前 \(i\) 个屋子，且第 \(i\) 个屋子不选的最大金额

不选，\(f[i][0] = \text{max(f[i - 1][1], f[i - 1][0])}\)

选， \(f[i][1] = \text{f[i - 1][0] + nums[i - 1]}\)

1
2
3
4
5
6
7
8
9
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[0] * 2 for _ in range(n + 1)]
        for i in range(1, n + 1):
            f[i][0] = max(f[i-1][1], f[i-1][0])
            f[i][1] = f[i-1][0] + nums[i-1]
        return max(f[n][1], f[n][0])

1
2
3
4
5
6
7
8
9
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = nums[0]
        for k in range(2, n + 1):
            dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2])
        return dp[n]

3.31 十一

§1.1 爬楼梯

动态规划

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
from functools import *
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @lru_cache(maxsize = None)
        def dfs(n):
            if n == 0 or n == 1:
                return 0
            else:
                return min(dfs(n - 1) + cost[n - 1], dfs(n - 2) + cost[n - 2])

        n = len(cost)    
        return dfs(n)

4.1 十

递归

sort

一维前缀和

DFS

整数二分

素数

GCD

图的存储

Dijkstra

dp

4.2 九

模拟

1.门牌制作 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
import os
import sys

ans = 0
for i in range(2, 2021):
    s = str(i)
    for j in s:
        if j == '2':
            ans = ans + 1
print(ans)

count方法

1
2
3
4
5
6
7
8
9
import os
import sys

# 请在此输入您的代码
b = 0
for i in range(1, 2021):
    a = str(i).count('2')
    b += a
print(b)

4.3 八

5

模拟

1.小球反弹 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import os
import sys


# ans=0

# l = 343720 # 长
# w = 233333 # 宽
# while True:
#     if l/w > 15/17: # w短，w要增加
#         w = w + 233333
#     elif l/w < 15/17:
#         l = l + 343720
#     else:
#         ans = (l**2 + w**2)**0.5
#         ans = ans * 2
#         print(ans)
#         break

print(1100325199.77)
1
2
# 保留两位小数
print(f'{ans:.2f}')

模拟

1.平方差 - 蓝桥云课

范围中奇数数量的计算

一个数的倍数的计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import os
import sys

# 自己找规律
# 奇数和4的倍数，两部分符合条件的结果

L, R = map(int, input().split())

# (R + 1) // 2 表示[1,R]之间奇数的数量
# L // 2 表示[1,L-1]之间奇数的数量
ans1 = (R + 1) // 2 - (L - 1 + 1) // 2

# R // 4 表示[1,R]之间4的倍数的数量
ans2 = R // 4 - (L-1) // 4

print(ans1 + ans2)

模拟

2.幸运数 - 蓝桥云课

数字转成字符串，字符串又转成列表，列表的计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import os
import sys

ans = 0

for i in range(1, 100000000):
    c = len(str(i))
    if c % 2 == 0:
        k = c // 2 # 中间位置
        cnt = list(map(int, list(str(i))))
        if sum(cnt[:k]) == sum(cnt[k:]):
            ans = ans + 1

print(ans)

模拟

3.幸运数字 - 蓝桥云课

注意check函数怎么写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def check(n, mod):
    x = n
    ans = 0
    # x % mod：计算 x 在 mod 进制下的最低位数字，然后将其累加到 ans 中。
    # x //= mod：将 x 除以 mod 并取整，相当于将 x 在 mod 进制下右移一位，去掉最低位数字。
    # 这个 while 循环会一直执行，直到 x 变为 0，此时 ans 中存储的就是 n 在 mod 进制下各位数字之和。
    while x > 0:
        ans += x % mod
        x //= mod
    return n % ans == 0

cnt = 0
i = 1

while True:
    if check(i,2) and check(i,8) and check(i,10) and check(i,16):
        cnt = cnt + 1
    if cnt == 2023:
        # print(i)
        break
    i = i + 1

print(215040)

暴力 or 前缀和

2.大学里的树木要维护 - 蓝桥云课

列表的应用： sum(A[a-1:b])计算a-b之间数字的和

1
2
3
4
5
6
7
8
# 暴力
N, M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(M):
    a, b = map(int, input().split())
    print(sum(A[a-1:b]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 前缀和

N, M = map(int, input().split())
A = list(map(int, input().split()))

ans = [0] * (N + 1) 
for i in range(N):
    ans[i + 1] = A[i] + ans[i]

for j in range(M):
    a, b = map(int, input().split())
    kkk = ans[b] - ans[a-1]

    print(kkk)

暴力 or 前缀和

1.异或和之和 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
# 暴力 60%
n = int(input())
A = list(map(int, input().split()))

ans = 0
for L in range(n):
    sum1 = 0
    for R in range(L,n):
        sum1 = sum1 ^ A[R]
        ans = ans + sum1

print(ans)

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