蓝桥杯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 八

6

模拟

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)

暴力 or 前缀和

1.求和 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
# 暴力 40%

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

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

print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 巧妙的前缀和 100%
n = int(input())
A = list(map(int, input().split()))

sum1 = sum(A) 
ans = 0
for i in range(n):
    sum1 = sum1 - A[i]
    ans = ans + A[i] * sum1 
print(ans)



# 正经的前缀和 100%

n = int(input())
a = list(map(int, input().split())) 
sum1 = [0] * (n + 1)  # 前缀和数组
ans = 0
# 输入数组元素并计算前缀和，同时计算结果
for i in range(n):
    sum1[i + 1] = sum1[i] + a[i]  # 前缀和
    ans = ans + a[i] * sum1[i]  # 你这个不能叫前缀和，应该叫后缀和，老弟
print(ans)

4.4 七

满分100，难度为0

1.九进制转十进制 - 蓝桥云课

前缀和

1.二维前缀和 - 蓝桥云课

前缀和

2.棋盘 - 蓝桥云课

前缀和

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
n, m = map(int, input().split())
a = list(map(int, input().split()))

r = [0] * (m + 1)
l = [0] * (m + 1)

# 把有矿的位置存到r,l里面，对应的位置加一
# 如5 4
#   0 -3 -1 1 2
# 此时，r = [0, 1, 1, 0, 0]，l = [0, 1, 0, 1, 0]。

# 这里一定要判断i <= m，不然会出现段错误，因为我们r = [0] * (m + 1)
for i in a:
    if i > 0 and i <= m:
        r[i] = r[i] + 1
    elif i < 0 and abs(i) <= m:
        l[abs(i)] = l[abs(i)] + 1

# 计算前缀和
for i in range(m):
    r[i + 1] = r[i + 1]  + r[i]
    l[i + 1] = l[i + 1]  + l[i]

ans = 0
# 先枚举往左走，再加上使用剩余体力向右走带来的价值
for i in range(1, m + 1):
    k = l[i]
    if m - 2*i > 0:
        k = k + r[m - 2*i]
    ans = max(ans, k)

# 反过来
for i in range(1, m + 1):
    k = r[i]
    if m - 2*i > 0:
        k = k + l[m - 2*i]
    ans = max(ans, k)

# 这里不用再讨论一直往一个方向走的情况，前面已经包含liao


if 0 in a:
    ans = ans + 1


print(ans)

4.5 六

1.寻找整数 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 先暴力找出一个范围，缩小暴力的程度，再暴力获得结果
# L=[]
# for i in range(187,10**12,187):
#     if i%44==33 and i%45==29 and i%46==15 and i%47==5 and i%48==41 and i%49==46:
#     #else:
#         L.append(i)
#     if len(L)>=2:
#         break
L=[5458460249, 12590206409]
step=L[1]-L[0]
flag=0
for i in range(L[0],10**17,step):
    if i%20==9 and i%25==9 and i%26==23 and i%27==20 and i%28==25 and i%29==16 and i%30==29 and i%31==27 and i%32==25 and i%33==11 and i%34==17 and i%35==4 and i%36==29 and i%37==22 and i%38==37 and i%39==23 and i%40==9 and i%41==1 and i%42==11 and i%43==11 :
        print(i)
        break

4.6 五

4..7 四

贪心

B-小紫的劣势博弈_牛客周赛 Round 85

小红想最小，那就拿最小的数，小紫想最大，那就减最小的数，排个序，然后奇加偶减即可

1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
nums = list(map(int, input().split()))

nums2 = sorted(nums)
ans = 0

for i in range(1, n + 1):
    if(i % 2 == 1):
        ans = ans + nums2[i - 1]
    else:
        ans = ans - nums2[i - 1]

print(ans)

前缀和

1.二维前缀和 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n, m, q = map(int, input().split())
a = [[0] * (m + 1) for _ in range(n + 1)] # n+1行，m+1列
k = [[0] * (m + 1) for _ in range(n + 1)] # 前缀和数组

 
# 输入二维数组a，并计算前缀和
for i in range(1, n + 1):
    a[i] = [0] + list(map(int, input().split()))
    for j in range(1, m + 1):
        k[i][j] = k[i][j-1] + a[i][j] + k[i-1][j] - k[i - 1][j - 1]


def get_k(x1, y1, x2, y2):
    if x1 > x2 or y1 > y2:  # 越界处理
        return 0
    return k[x2][y2] - k[x1 - 1][y2] - k[x2][y1 - 1] + k[x1 - 1][y1 - 1]

for _ in range(q):
    x1, y1, x2, y2 = map(int, input().split())
    print(get_k(x1, y1, x2, y2))

4.8 三

4.9 二

U535982 J-A 小梦的AB交换 - 洛谷

1
2
3
4
5
6
7
8
9
10
11
12
T = int(input())
for _ in range(T):
    n = int(input())
    s = input()

    a = 0
    for i in range(2*n):
        if i % 2 != 0:
            if s[i] == 'A':
                a = a + 1
              
    print(min())

4.10 一

贪心

C-小苯的Z串匹配_牛客周赛 Round 87

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    s = input().strip()
    cnt = 0
        
    for i in range(n):
        char = s[i]
        if char == '<':
            if arr[i] >= 0:
                cnt = cnt + 1
            arr[i] = -1
        elif char == '>':
            if arr[i] <= 0:
                cnt = cnt + 1
            arr[i] = 1
        elif char == 'Z':
            if arr[i - 1] * arr[i] <= 0:
                cnt = cnt + 1
            arr[i] = arr[i - 1] 
    print(cnt)

枚举

D-小红杀怪_2024BistuACM萌新练习赛01

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 math

def main():
    a, b, x, y = map(int, input().split())
    
    ans = float('inf')  # 初始化结果为最大值
    
    max_k = max((a + y - 1) // y, (b + y - 1) // y)  # 向上取整，表示最多使用多少次y技能可以确保一只怪物被击杀
    
    for i in range(max_k + 1):
        # 使用i次y技能时，两只怪物剩余血量
        num_a = max(0, a - i * y)
        num_b = max(0, b - i * y)
        
        # 用i次y技能，剩下的使用x技能
        res_a = (num_a + x - 1) // x
        res_b = (num_b + x - 1) // x
        
        ans = min(ans, i + res_a + res_b)  # 每次取最小值
    
    print(ans)

if __name__ == "__main__":
    main()

4.11 〇

前缀和

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

1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
a = [0] + list(map(int, input().split()))
sa = [0] * (n + 1)  # 前缀和

for i in range(1, n + 1):
    sa[i] = sa[i - 1] + a[i]

q = int(input())
for _ in range(q):
    m, n = map(int, input().split())
    print(sa[n] - sa[m - 1])

前缀和

U549625 小苯的区间和疑惑 - 洛谷

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
def main():

    n = int(input())
    a = [0] + list(map(int, input().split()))
 
    max_left = [0] * (n + 1) # 存储以i结尾的最大子数组和
    max_right = [0] * (n + 1) # 存储以i开头的最大子数组和
    res = [0] * (n + 1)      # 结果数组

    # 计算max_left数组（必须包含a[i]且以i结尾）
    max_left[1] = a[1]  # 初始化：第一个元素的最大和就是它本身
    for i in range(2, n + 1):
        # 状态转移：要么单独取a[i]，要么接上前面的子数组
        max_left[i] = max(a[i], max_left[i - 1] + a[i])
    
    # 计算max_right数组（必须包含a[i]且以i开头）
    max_right[n] = a[n]  # 初始化：最后一个元素的最大和就是它本身
    for i in range(n - 1, 0, -1):  # 从后往前遍历
        max_right[i] = max(a[i], max_right[i + 1] + a[i])
    
    # 计算结果：每个位置的和 = 向左扩展最大值 + 向右扩展最大值 - 重复计算的a[i]
    for i in range(1, n + 1):
        res[i] = max_left[i] + max_right[i] - a[i]
    
    print(*res[1:n + 1], sep=' ')
        
if __name__ == "__main__":
    main()

前缀和

[P3131 USACO16JAN] Subsequences Summing to Sevens S - 洛谷

有思路的前缀和

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
n = int(input())
pre = [0] * (n + 1)  # 前缀和数组（1-based索引）
first = [-1] * 7      # 记录每个余数第一次出现的位置
last = [-1] * 7       # 记录每个余数最后一次出现的位置

# 读取输入并计算前缀和模7的余数
for i in range(1, n + 1):
    num = int(input())
    pre[i] = (pre[i - 1] + num) % 7

# 记录每个余数第一次出现的位置（从后往前扫描）
for i in range(n, 0, -1):
    first[pre[i]] = i
first[0] = 0  # 特殊处理余数为0的情况

# 记录每个余数最后一次出现的位置（从前往后扫描）
for i in range(1, n + 1):
    last[pre[i]] = i

# 计算最大长度
max_len = 0
for i in range(7):
    if first[i] != -1 and last[i] != -1:
        max_len = max(max_len, last[i] - first[i])

print(max_len)

前缀和

[P8649 蓝桥杯 2017 省 B] k 倍区间 - 洛谷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n, k = map(int, input().split())  # 读取数列长度n和倍数k
arr = [0] * n  
for i in range(n):
    arr[i] = int(input())  

res = 0  # 初始化结果计数器（K倍区间总数）
m = 0  # 初始化当前前缀和的模k值
nums = [0] * k  # 初始化模k余数统计数组（记录各余数出现次数）
nums[0] = 1  # 初始状态：前缀和为0（空前缀）的余数为0，出现1次

for i in range(n):
    m = (m + arr[i]) % k  # 计算当前前缀和模k的余数
    res += nums[m]  # 累加相同余数的出现次数（新增的K倍区间数）
    nums[m] += 1  # 更新当前余数的出现次数

print(res)  # 输出K倍区间总数

DFS

[P2036 COCI 2008/2009 #2] PERKET - 洛谷

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
30
31
32
33
34
35
36
37
from math import inf

M = 15  # 最大配料数
a = [0] * (M + 1)  # 酸度数组（1-based）
b = [0] * (M + 1)  # 甜度数组（1-based）
n = 0  # 实际配料数
ans = inf  # 初始化为无穷大

def dfs(i, x, y):
    """
    深度优先搜索配料组合
    :param i: 当前配料编号
    :param x: 当前总酸度（酸度的乘积）
    :param y: 当前总甜度（甜度的和）
    """
    global ans
    
    if i > n:  # 所有配料处理完毕
        if x == 1 and y == 0:  # 排除清水情况
            return
        ans = min(abs(x - y), ans)  # 更新最小差值
        return
    
    # 两种情况：1. 使用当前配料 2. 不使用当前配料
    dfs(i + 1, x * a[i], y + b[i])  # 使用当前配料
    dfs(i + 1, x, y)  # 不使用当前配料


 
n = int(input())  # 读取配料数
for i in range(1, n + 1):
    a[i], b[i] = map(int, input().split())  # 读取酸度和甜度
    
dfs(1, 1, 0)  # 从第1个配料开始搜索，初始酸度1，甜度0
print(ans)


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