代码收藏家技术教程 22天前

CCF CSP历年真题汇总，附Python题解详解

2023012的真题

202312-1

仓库规划

5415. 仓库规划 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5418/

解题思路：

其实就是对比（x.y,z…..）需要找到一个每个元素都大于这个坐标得坐标，本题可以直接暴力求解，主要需要了解其python得数据结构，怎么能够方便的比较坐标括号中得每个元素我们采用zip

解题代码

n, m = map(int, input().split())
coding = [tuple(map(int, input().split())) for _ in range(n)]
results = []
for i in range(n):  # 枚举每个仓库
    for j in range(n):  # 枚举它的上级仓库
        if i != j and all(x < y for x, y in zip(coding[i], coding[j])):  # 满足上级仓库的定义
            results.append(j+1)
    if len(results) == 0:
        print(0)
    else:
        print(min(results))
    results=[]

知识点1：对于输入得灵活运用控制台（map）

n, m = map(int, input().split())
其中 int这个位置代表一个操作函数，后面是input通过空格划分

将输入的多个字符串转换为其他类

# 使用 map(float, input().split()) 将输入的字符串转换为浮点数
numbers = list(map(float, input().split()))
print(numbers)  # 输出：[3.14, 2.71, 1.41]

# 使用 map() 将输入的单词转换为大写
words = list(map(str.upper, input().split()))
print(words)  # 输出：['HELLO', 'WORLD']

对输入的每个元素应用自定义函数

# 定义一个自定义函数
def add_one(x):
    return x + 1

# 输入数字并转换为整数
numbers = list(map(int, input().split()))

# 对每个数字应用自定义函数
result = list(map(add_one, numbers))
print(result)  # 输出：[2, 3, 4, 5]

使用 map() 处理多行输入

# 读取第一行的数字 n
n = int(input())

# 使用 map() 读取接下来的 n 行输入，并将每行转换为整数
numbers = list(map(int, (input() for _ in range(n))))
print(numbers)  # 输出：[10, 20, 30]

多个输入的逐元素操作知识点1：对于输入得灵活运用控制台（map）

# 输入两个列表
list1 = list(map(int, input().split()))
list2 = list(map(int, input().split()))

# 使用 map() 和 lambda 函数逐元素相加
result = list(map(lambda x, y: x + y, list1, list2))
print(result)  # 输出：[5, 7, 9]

知识点2：zip得运用

zip() 是 Python 中一个非常强大的函数，用于将多个可迭代对象（如列表、元组等）“打包”成一个由元组组成的迭代器。每个元组包含来自每个输入可迭代对象的对应元素。

zip() 是一个非常灵活的函数，可以用于：
打包多个可迭代对象：将对应元素组合成元组。

同时遍历多个列表：简化代码逻辑。
解包：恢复为原来的多个列表。解包的过程是通过 * 运算符完成的，它可以将 zip 对象中的元组重新拆分为多个独立的列表。输出为按照列排列得元组
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# 遍历每一列
for col in zip(*matrix):
    print("列：", col)
    # 可以对每一列进行操作，例如计算列的和
    col_sum = sum(col)
    print("列的和：", col_sum)
列： (1, 4, 7)
列的和： 12
如果想要进行遍历得转化为列表
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# 交换第 1 行和第 2 行
matrix[0], matrix[1] = matrix[1], matrix[0]

# 交换第 1 列和第 2 列
transposed = list(zip(*matrix))
transposed[0], transposed[1] = transposed[1], transposed[0]
matrix = list(zip(*transposed))

print("交换后的矩阵：")
for row in matrix:
    print(row)
创建字典：通过 dict(zip(keys, values))。

排序：根据一个列表的值对多个列表进行排序。

举例说明

202312-2

因子化简

5416. 因子化简 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5419/

解题思路

题目写的比较晦涩难懂，但是看懂样例就比较简单了，主要掌握怎么求素数，怎么能在低时间复杂度下求素数（质数）。素数就是能被1或者它本身整除得，那2就是最小得素数。求素数就枚举，类似于辗转相除法，小素数除不尽了在试试大点得。一般情况下是在数字得一半就能找完，比如10=2*5，如果超过一般那跟小的一半是倍数关系了，但是特殊情况是如果这个数字本身就是质数例如7，那就是特例了，需要注意。

解题代码

q = int(input())
for _ in range(q):
    n, k = map(int, input().split())
    prime_factors = {}
    # 只需要检查到 sqrt(n)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n = n // i
            prime_factors[i] = prime_factors.get(i, 0) + 1
        i = i + 1

    # 如果 n 仍然大于 1，说明 n 本身是一个质因数
    if n > 1:
        prime_factors[n] = prime_factors.get(n, 0) + 1

    result = 1
    for factor, exponent in prime_factors.items():
        if exponent >= k:
            result *= factor ** exponent

    print(result)

知识点1：对于字典得灵活运用

题目中有个要求就是幂小于m得时候就给删除了，我们可以用字典实现这个操作：

1使用 `dict()` 构造函数

# 从键值对列表创建字典
person = dict([("name", "Alice"), ("age", 25), ("city", "New York")])

# 从关键字参数创建字典
person = dict(name="Alice", age=25, city="New York")

2. 访问字典中的值

person = {"name": "Alice", "age": 25, "city": "New York"}

# 访问键 "name" 对应的值
print(person["name"])  # 输出：Alice

print(person.get("name"))  # 输出：Alice

# 如果键不存在，get() 方法可以返回一个默认值
print(person.get("gender", "Unknown"))  # 输出：Unknown

prime_factors.get(i, 0)#获取当前i的值，如果不存在则默认为 0
prime_factors[i] = prime_factors.get(i, 0) + 1
prime_factors[i] = ...：更新字典中的计数。
这种写法非常适合在质因数分解或其他需要统计频率的场景中使用。

3.遍历字典

person = {"name": "Alice", "age": 25, "city": "New York"}

# 遍历字典的键
for key in person:
    print(key)  # 输出：name, age, city
# 遍历字典的值
for value in person.values():
    print(value)  # 输出：Alice, 25, New York
# 遍历字典的键值对
for key, value in person.items():
    print(key, value)  # 输出：name Alice, age 25, city New York

202309的真题

202309-1

坐标变换（其一）

5297. 坐标变换（其一） – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5300/

解题思路

此题没有难度

解题代码

n,m=map(int,input().split())
b=list()
c=list()
for i in range(n):
    a=list(map(int,input().split()))
    b.append(a)
for i in range(m):
    d=list(map(int,input().split()))
    c.append(d)
all=list()
for i in range(m):#操作需要改变的
    for j in range(n):#操作改变的次数
        c[i][0]=c[i][0]+b[j][0]
        c[i][1]=c[i][1]+b[j][1]
    for element in c[i]:
        print(element,end=" ")
    print()

知识点1：输出得控制

end=" " 是 Python 中 print() 函数的一个参数设置，用于指定输出内容后的结束符。默认情况下，print() 函数在输出内容后会自动换行（即 end="\n"）。通过设置 end=" "，可以让输出内容在同一行后继续输出，而不是换行。
print("Hello", end=" ")
print("World")
# 输出：Hello World
自定义分隔符：可以将 end 设置为其他字符，用于特定格式的输出。
print("Hello", end=",")
print("World")
# 输出：Hello,World

202309-2

坐标变换（其二）

5298. 坐标变换（其二） – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5301/

解题思路

此题没有难度，但是有点烦人得是他操作从1开始，但是我们平时存储得列表索引是从0开始，容易绕混了，直接暴力解决多开一位。主要是不能被他给绕进去了，我们要知道度数变化不影响长度得变化，长度得变化不影响度数变化.然后就是理解题意i到 j 是经过一系列得操作

解题代码

import math

# 读取输入的 n 和 m
n, m = map(int, input().split())

# 定义结构体 OP 对应的列表，存储操作信息
op = []
# 初始化 op 列表，索引从 1 开始，第一个元素用 None 占位
op.append(None)

# 初始化 s 和 ss 列表，用于存储中间结果
s = [0] * (n + 1)
ss = [0] * (n + 1)
# 初始化 s[0] 和 ss[0]
s[0] = 1
ss[0] = 0

# 读取 n 个操作信息
for i in range(1, n + 1):
    id_, x = map(float, input().split())
    id_ = int(id_)
    op.append((id_, x))
    if id_ == 1:
        s[i] = s[i - 1] * x
        ss[i] = ss[i - 1]
    elif id_ == 2:
        ss[i] = ss[i - 1] + x
        s[i] = s[i - 1]

# 处理 m 次查询
for _ in range(m):
    i, j, a, b = map(float, input().split())
    i = int(i)
    j = int(j)
    # 计算乘法因子
    cheng = s[j] / s[i - 1]
    # 计算度数差
    dushu = ss[j] - ss[i - 1]
    # 计算中间结果 aa 和 bb
    aa = a * cheng
    bb = b * cheng
    # 进行坐标转换
    a = aa * math.cos(dushu) - bb * math.sin(dushu)
    b = aa * math.sin(dushu) + bb * math.cos(dushu)
    # 输出结果，保留三位小数
    print(f"{a:.3f} {b:.3f}")

知识点1：避免重复计算

为了避免重复计算，可以开个列表把需要重复计算得数值存进去，如果需要从i到j之间得变化率
s[j] / s[i - 1]#计算变化率，为什么是i-1呢，因为是从i开始算的
知识点1：避免重复计算

解决索引跟顺序不一致得情况直接暴力多开一位数组
s=[0]*(n+1)
ss=[0]*(n+1)

2023005的真题

202305-1

重复局面

5081. 重复局面 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5084/

解题思路
这题别看题目复杂，其实上就是字符串得判断，因为他输出那一大堆其实就是一串字符串嘛

解题代码

import sys

def main():
    # 读取输入
    n = int(sys.stdin.readline().strip())  # 读取总步数
    positions = []  # 用于存储每一步的棋盘局面
    counts = {}  # 用于存储每个局面出现的次数

    for _ in range(n):
        # 读取 8 行棋盘局面
        board = [sys.stdin.readline().strip() for _ in range(8)]
        # 将棋盘局面拼接成一个字符串
        board_str = ''.join(board)
        # 更新局面出现次数
        if board_str in counts:
            counts[board_str] += 1
        else:
            counts[board_str] = 1
        # 输出当前局面是第几次出现
        print(counts[board_str])

if __name__ == "__main__":
    main()

知识点1：' '.join(s)，其中s是字符串列表，可以直接进行字符串拼接
board_str = ''.join(s)
知识点2：对于着这种换行输入直接用input()即可，不要用map容易出错，如果非要用map那么可以用一下代码来解决

场景1：如果两个单词之间有空格，如果没有空格把.split())去掉，不然单词要被切分为字母
3
hello world
foo bar baz
abc def ghi
b = []  # 初始化一个空列表，用于存储所有输入的行
n = int(input())  # 输入的第一行是一个整数，表示有多少行输入

for _ in range(n):
    a = list(map(str, input().split()))  # 使用 map() 将每行分割为字符串列表
    b.append(a)  # 将每行的字符串列表添加到 b 中

# 打印结果以验证
['hello', 'world']
['foo', 'bar', 'baz']
['abc', 'def', 'ghi']

202305-2

矩阵运算

解题思路：

这道题也不难，再纸上推一下规律就能找到循环去计算的规律。这道题的重点在于时间复杂度，如果先算QK矩阵相乘，会得到n * n的矩阵，会显示超时，所以要先算后面两个矩阵，时间复杂度是可以过的。

原始表达式分析：对于表达式 (W⋅(Q×KT))×V，这里的 ⋅ 并不是严格的向量点乘（内积那种，对应元素乘积求和），而代码中的操作是将 W 这个向量的每个元素与矩阵 (Q×KT) 对应行的每个元素分别相乘，本质是一种按元素的乘法。

代码计算顺序：

首先计算 Q×KT：在代码中，通过 K 矩阵赋值时 K[j][i] = row[j - 1] 实现了 K 的转置（读取数据时转置）。然后通过三重循环计算 K 和 V 的矩阵乘积 res（这一步相当于 KT×V ），接着计算 Q 和 res 的矩阵乘积 res2（这一步完成了 Q×KT×V 的计算）。

最后将 W 与 res2 操作：代码中 res2[i][j] *= W[i] 是将矩阵 res2 的每一行的每个元素与 W 向量对应位置的元素相乘，这是一种按元素的乘法操作，和我们通常说的向量点乘（对应元素乘积再求和）有所不同。

运算顺序合理性：矩阵乘法满足结合律，即 (A×B)×C = A×(B×C)。在这个问题中，(W⋅(Q×KT))×V 可以先计算 (Q×KT)×V 得到一个中间矩阵 res2，再将 W 按行与 res2 对应元素相乘。虽然从符号表示上看像是改变了 W 参与运算的顺序，但由于矩阵乘法结合律以及这里对 W 操作的本质（按元素相乘），最终结果是正确的。

解题代码

n, d = map(int, input().split())
Q = [[i for i in map(int, input().split())] for j in range(n)]
K = [[i for i in map(int, input().split())] for j in range(n)]
V = [[i for i in map(int, input().split())] for j in range(n)]
W = [i for i in map(int, input().split())]
tmp = []
ans = []
 
# 计算 K的转置 * V = tmp
for i in range(d):
    tmp.append([])
    for j in range(d):
        tmp[i].append(0)
        for k in range(n):
            tmp[i][j] += K[k][i]*V[k][j]
 
# 计算 Q * tmp = ans
for i in range(n):
    ans.append([])
    for j in range(d):
        ans[i].append(0)
        for k in range(d):
            ans[i][j] += Q[i][k]*tmp[k][j]
        ans[i][j] *= W[i]
 
for i in range(n):
    a = []
    for j in range(d):
        a.append(ans[i][j])
    print(*a)

知识点1：矩阵得转置

矩阵的转置就是行变成列，列变成行，不用思考那么多
kt=[[0 for _ in range(n)]for _ in range(d)]
for i in range(n):
    for j in range(d):
        kt[j][i]=k[i][j]

知识点2：列表推导式

列表推导式形式
# 使用列表推导式创建二维列表
two_d_list = [[0 for _ in range(4)] for _ in range(3)]
print(two_d_list)
上述代码中，外层的 [... for _ in range(3)] 循环执行 3 次，每次循环会创建二维列表中的一行。内层的 [0 for _ in range(4)] 也是一个列表推导式，它在每次外层循环时被执行，用于创建一行包含 4 个 0 的列表。最终，two_d_list 是一个 3 行 4 列且所有元素都为 0 的二维列表。

展开为普通 for 循环的形式
# 使用普通 for 循环创建二维列表，功能与上述列表推导式等价
two_d_list_expanded = []
for i in range(3):
    row = []
    for j in range(4):
        row.append(0)
    two_d_list_expanded.append(row)
print(two_d_list_expanded)

知识点3：列表和矩阵坐标之间得误解

2023003的真题

202303-1

田地丈量

5016. 田地丈量 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5019/

解题思路：

此题看似复杂，其实就是搞清楚坐标之间得关系，如果是左下角那应该是那个坐标大取那个，右上角那个小取那个坐标，还有就是特殊情况有时候根本就没重叠直接抛弃就行

解题代码

n,a,b=map(int,input().split())
s2=list()
for i in range(int(n)):
    s1=list(input().split())
    s2.append(s1)
s3=0
for i in range(int(n)):
    x1=max(int(s2[i][0]),0)
    y1 = max(int(s2[i][1]), 0)
    x2=min(int(s2[i][2]),a)
    y2 = min(int(s2[i][3]), b)
    # 确保 x2 - x1 和 y2 - y1 都是非负数
    if x2 > x1 and y2 > y1:
        s3 += (x2 - x1) * (y2 - y1)

print(s3)

202303-2

垦田计划

解题思路：

这题就有点恶心了，因为你要保证你的时间复杂度符合要求。仔细研究表格会发现其实又出现了索引不一致情况，所以我们还多开一位。另外暴力破解会超时，所以我们需要用二分法进行查找找到最低得时间。就类似于贪心一样

解题代码

'二分法+贪心算法'

n,m,k=map(int,input().split())
time=[]#记录每块天地的时间成本
cost=[]#记录每块天地减少一天的时间成本
for i in range(n):
    t,c=map(int,input().split())
    time.append(t)
    cost.append(c)
left=k#开垦时间肯定不会小于k
right=max(time)
def check(mid):
    totalcost=0
    for i in range(n):#一个一个遍历看那个大于mid
        if(time[i]>mid):
            totalcost+=cost[i]*(time[i]-mid)
    return totalcost<=m#小于m返回true，说明满足
while(left<right):
    mid=(left+right)//2
    if(check(mid)):#mad的值满足后m仍有结余
        right=mid#说明还能满足更下面的时间需求
    else:
        left = mid + 1#mid都满足不了，也不用让left成为mid了，直接mid+1
print(left)

知识点1：二分法得模板

1. 精确查找目标值（使用 `left <= right`）

适用场景

在一个有序数组中查找特定目标值的位置，如果目标值存在则返回其索引，不存在则返回 -1。

left <= right 确保能对整个数组进行完整搜索，即使 left 和 right 重合时也会进行检查。

当找到目标值时，直接返回其索引；若未找到，最终 left 会大于 right，循环结束，返回 -1

def binary_search_exact(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # 避免整数溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 示例
nums = [1, 2, 3, 4, 5]
target = 3
print(binary_search_exact(nums, target))

2. 查找左边界（使用 `left < right`）

适用场景

在有序数组中查找第一个大于等于目标值的元素的索引，常用于查找满足特定条件的最小位置。

left < right 保证循环在 left 和 right 相遇时停止，此时 left 指向的就是第一个大于等于目标值的位置。

当 nums[mid] < target 时，说明目标位置在 mid 的右侧，更新 left = mid + 1；否则，目标位置可能是 mid 或在其左侧，更新 right = mid。

def binary_search_left(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

# 示例
nums = [1, 2, 2, 2, 3]
target = 2
print(binary_search_left(nums, target))

知识点2：注意 mid=(lift+right)//2，不要忘记加括号

202212的真题

202212-1

现值计算

4891. 现值计算 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/4894/

解题思路：没有难度，把题目看懂即可，也就是说，看懂他让计算得是现值，也就是要用那个-k去计算，我们不在未来，未来的是预估收入

解题代码


def calculate_project_value(n, i, cash_flows):
    total = 0.0
    for k, cash in enumerate(cash_flows):
        total += cash * (1 + i) ** -k
    return total

# 读取输入数据
n, i = map(float, input().split())
cash_flows = list(map(int, input().split()))

# 计算总盈利或亏损
total_value = calculate_project_value(n, i, cash_flows)

# 输出结果
print(f"{total_value:.3f}")

知识点1：enumerate() 是什么？

迭代器不会一次性加载整个数据集，而是逐个生成元素，因此内存占用较低。

迭代器可以用于任何可迭代对象，包括列表、元组、字典、集合、文件对象等
enumerate() 是一个内置函数，它将一个可迭代对象（如列表、元组、字符串等）包装成一个枚举对象（enumerate 对象）。这个枚举对象是一个迭代器，它在每次迭代时返回一个包含索引和元素的元组。
my_list = ["a", "b", "c"]
for index, value in enumerate(my_list):
    print(index, value)
0 a
1 b
2 c

知识点2：数字得倒着遍历

range() 函数可以接受三个参数：起始值、结束值（不包含）和步长。通过设置步长为 -1，可以实现从大到小的遍历。
for i in range(10, 0, -1):  # 从 10 开始，到 1 结束（不包含 0），步长为 -1
    print(i)
10
9
8
7
6
5
4
3
2
1
for i in range(10, -1, -1):  # 从 10 开始，到 -1 结束（不包含 -1），步长为 -1
    print(i)

202212-2

训练计划

解题思路：第一就是多开一位数组，容易记忆依赖关系

当求最早开始时间得时候，就是要有依赖关系，在依赖最早开始时间得基础上加上依赖得那个节点完成需要得时间，依赖关系最早开始就得从头遍历，初始化为1，因为最早是从第一天。如果被多个依赖得话，被依赖得那个肯定要往后推
最晚得话就得如果没依赖得话直接减去完成得时间就是最晚开始得时间，但是如果有依赖得话那被依赖得节点就得从现在这个节点最晚开始得节点再向前推时间，但是可能存在这个被依赖得节点要被多个节点依赖，那肯定要根据木桶原理最大限度得先满足要求得往前推时间。那我们假设都无穷大得时间

解题代码

# 读取输入的 n 和 m
n, m = map(int, input().split())

# 初始化 p 和 t 列表
p = [0] * (m + 1)
t = [0] * (m + 1)

# 读取 p 列表的值
p[1:] = map(int, input().split())
# 读取 t 列表的值
t[1:] = map(int, input().split())

# 初始化结果列表
res = [0] * (m + 1)

# 计算最早开始时间
mx = 0
for i in range(1, m + 1):
    if p[i] == 0:
        res[i] = 1
    else:
        res[i] = res[p[i]] + t[p[i]]
    mx = max(mx, res[i] + t[i] - 1)

# 输出最早开始时间
print(" ".join(map(str, res[1:])))

# 如果最大结束时间超过 n，程序结束
if mx > n:
    exit()

# 初始化 res 列表为一个较大的值
res = [float('inf')] * (m + 1)

# 计算最晚开始时间
for i in range(m, 0, -1):
    if res[i] > n:
        res[i] = n + 1 - t[i]
    if p[i] != 0:
        res[p[i]] = min(res[p[i]], res[i] - t[p[i]])

# 输出最晚开始时间
print(" ".join(map(str, res[1:])))

知识点1：输出print(" ".join(map(str, res[1:])))

" ".join(...)

join 是字符串方法，用于将一个可迭代对象中的所有元素拼接成一个字符串，拼接时以指定的分隔符（这里是空格 " "）连接。

例如，对于 ['1', '2', '3', '4']，" ".join(['1', '2', '3', '4']) 的结果是字符串 "1 2 3 4"

202209的真题

202209-1

如此编码

202206的真题

202206-1

归一化处理

找不到页面 – AcWing找不到页面 – AcWinghttps://www.acwing.com/problem/content/submission/code_detail/39761221/找不到页面 – AcWing

解题思路：简单，略

解题代码

import math

n=int(input())
a=list(map(int,input().split()))
suma=0
ressum=0
for i in a:
    suma+= i
mena=suma/n
for i in range(n):
    ressum=ressum+(a[i]-mena)**2
d=ressum/n
fa=[]
for i in range(n):
    fa.append((a[i]-mena)/math.sqrt(d))
for f in fa:
    print(f)

202206-2

寻宝！大冒险！

4510. 寻宝！大冒险！ – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/4513/

解题思路：需要理解矩阵得颠倒，set提高运行效率，减少时间复杂度

解题代码

n, L, S = map(int, input().split())
points = set()
for _ in range(n):
    x, y = map(int, input().split())
    points.add((x, y))

# 读取藏宝图并调整顺序
tmp = []
for _ in range(S + 1):
    row = list(map(int, input().split()))
    tmp.append(row)
B = tmp[::-1]  # 反转得到正确的B数组

# 如果藏宝图的左下角不是1，直接返回0
if B[0][0] != 1:
    print(0)
    exit()

ans = 0
S_size = S  # 藏宝图的尺寸是S+1 x S+1，i和j的范围是0到S

for (x, y) in points:
    # 检查是否超出绿化图的范围
    if x + S > L or y + S > L:
        continue
    valid = True
    for i in range(S + 1):
        if not valid:
            break
        for j in range(S + 1):
            current_x = x + i
            current_y = y + j
            # 检查当前点是否符合藏宝图的要求
            if B[i][j] == 1:
                if (current_x, current_y) not in points:
                    valid = False
                    break
            else:
                if (current_x, current_y) in points:
                    valid = False
                    break
    if valid:
        ans += 1

print(ans)

知识点1：set()比list更加得高效，如果一致没有重复得元素，完全可以用set

集合的成员检查操作之所以高效，是因为它基于哈希表的实现方式。哈希表通过哈希函数快速定位元素的存储位置，从而在平均情况下实现 O(1) 的时间复杂度。而列表的成员检查需要逐个遍历元素，时间复杂度为 O(n)。

1添加元素

add(element)：添加单个元素。

update(iterable)：添加多个元素。
points = set()
for _ in range(n):
    x, y = map(int, input().split())
    points.add((x, y))
s = {1, 2, 3}
s.add(4)         # s 变为 {1, 2, 3, 4}
s.update([5, 6])  # s 变为 {1, 2, 3, 4, 5, 6}
2交集
intersection(other_set) 或 &：返回两个集合的交集
s1 = {1, 2, 3}
s2 = {2, 3, 4}

s_intersection = s1.intersection(s2)  # {2, 3}
s_intersection = s1 & s2              # {2, 3}
3并集
union(other_set) 或 |：返回两个集合的并集。
s_union = s1.union(s2)    # {1, 2, 3, 4}
s_union = s1 | s2         # {1, 2, 3, 4}
4差集
difference(other_set) 或 -：返回属于第一个集合但不属于第二个集合的元素。
s_diff1 = s1.difference(s2)  # {1}
s_diff1 = s1 - s2             # {1}

s_diff2 = s2.difference(s1)  # {4}
s_diff2 = s2 - s1             # {4}

知识点2：列表翻转

二维列表的行反转

tmp[::-1] 是 Python 的切片操作，表示从最后一个元素到第一个元素的逆序。
tmp = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

reversed_tmp = tmp[::-1]
print(reversed_tmp)
[
    [7, 8, 9],
    [4, 5, 6],
    [1, 2, 3]
]
二维列表的列反转

如果需要反转二维列表的列顺序，可以结合列表推导式和切片操作。
tmp = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# 反转每一行的列顺序
reversed_columns = [row[::-1] for row in tmp]
print(reversed_columns)
[
    [3, 2, 1],
    [6, 5, 4],
    [9, 8, 7]
]

202203的真题

202203-1

未初始化警告

4454. 未初始化警告 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/4457/

解题思路：傻逼题，题目难懂，0属于常数，虽然题目中没看懂

解题代码

def count_uninitialized_statements():
    # 读取输入
    n, k = map(int, input().split())
    initialized = [False] * (n + 1)  # 初始化状态数组，大小为 n+1
    uninitialized_count = 0  # 未初始化的语句计数器

    for _ in range(k):
        xi, yi = map(int, input().split())
        # 检查右值 yi 是否被初始化
        if yi > 0 and not initialized[yi]:
            uninitialized_count += 1
        # 左值 xi 在这条语句后被初始化
        initialized[xi] = True

    return uninitialized_count

# 调用函数并输出结果
print(count_uninitialized_statements())

202203-2

出行计划

4455. 出行计划 – AcWing题库高质量的算法题库https://www.acwing.com/problem/content/4458/

解题思路：用差分法解题，贴一下题解

# 差分解题思路（以区间修改并查询问题为例）

## 一、问题描述
假设有一个数组，需要对数组的某些区间进行多次修改（如给区间内所有元素加上一个固定值或减去一个固定值），并且在修改后需要查询数组中某些位置或区间的元素值。

## 二、解题思路
1. **构建差分数组**：
对于给定的原始数组 `a`（长度为 `n`），创建一个差分数组 `b`（长度也为 `n`）。
根据差分的定义：
   - `b[0] = a[0]`
   - 对于 `i > 0`，`b[i] = a[i] - a[i - 1]`

例如，若原始数组 `a = [1, 5, 3, 7]`，则差分数组 `b = [1, 4, -2, 4]`。构建差分数组的过程本质上是记录原数组相邻元素之间的差值变化。
2. **进行区间修改**：
当需要对原数组的区间 `[l, r]` 进行修改（如加上一个值 `x`）时，只需要对差分数组进行两个单点操作：
   - `b[l] += x`
   - `b[r + 1] -= x`（注意 `r + 1` 要在数组范围内）

这是因为差分数组记录了原数组的变化量，`b[l] += x` 表示从位置 `l` 开始，原数组元素的变化量增加了 `x`，而 `b[r + 1] -= x` 表示从位置 `r + 1` 开始，原数组元素的变化量不再增加 `x`，从而实现了对区间 `[l, r]` 的修改效果。
3. **还原原数组（查询操作）**：
如果要查询原数组某个位置 `i` 的值，或者需要得到经过多次区间修改后的完整原数组，就需要对差分数组求前缀和。
前缀和数组 `s` 的计算方式为：
   - `s[0] = b[0]`
   - 对于 `i > 0`，`s[i] = s[i - 1] + b[i]`

最终得到的前缀和数组 `s` 就是经过区间修改后的原数组。例如，对差分数组 `b = [1, 4, -2, 4]` 求前缀和，得到 `s = [1, 5, 3, 7]`，这就是原数组经过一系列操作后的结果。如果只查询某个位置的值，直接获取前缀和数组对应位置的值即可。

## 三、总结
差分算法的核心在于将对原数组的复杂区间操作转化为对差分数组的简单单点操作，通过差分数组记录变化量，再利用前缀和还原出原数组的最终状态，从而高效地解决频繁的区间修改和查询问题。

解题代码

## 差分 有可能是负数 要加上一个大数 映射到正数区间
M = 3* 10 ** 5 + 10
b = [0] * (M + M)
n,m,k = map(int,input().split())

for i in range(n):
    t,c = map(int,input().split())
    x2 = t - k # -1e5
    x1 = t - k - c + 1 # -3e5
    b[x1+M] += 1
    b[x2+M+1] -= 1


for i in range(1,M+M):
    b[i] += b[i-1]


for i in range(m):
    q = int(input())
    print(b[q+M])

解题思路：

解题代码

知识点1：

知识点2：

解题思路：

解题代码

知识点1：

知识点2：

解题思路：

解题代码

知识点1：

知识点2：

解题思路：

解题代码

知识点1：

知识点2：

解题思路：

解题代码

知识点1：

知识点2：

作者：小樊努力努力再努力

物联沃分享整理
物联沃-IOTWORD物联网 » CCF CSP历年真题汇总，附Python题解详解

代码收藏家普通

分享到：

2023012的真题

202312-1

仓库规划

解题思路：

解题代码

知识点1：对于输入得灵活运用控制台（map）

将输入的多个字符串转换为其他类

知识点2：zip得运用

打包多个可迭代对象：将对应元素组合成元组。

同时遍历多个列表：简化代码逻辑。

解包：恢复为原来的多个列表。解包的过程是通过 * 运算符完成的，它可以将 zip 对象中的元组重新拆分为多个独立的列表。输出为按照列排列得元组

创建字典：通过 dict(zip(keys, values))。

排序：根据一个列表的值对多个列表进行排序。

举例说明

202312-2

因子化简

解题思路

解题代码

知识点1：对于字典得灵活运用

1使用 dict() 构造函数

2. 访问字典中的值

3.遍历字典

202309的真题

202309-1

坐标变换（其一）

解题思路

解题代码

知识点1：输出得控制

202309-2

坐标变换（其二）

解题思路

解题代码

知识点1： 避免重复计算

知识点1： 避免重复计算

2023005的真题

202305-1

重复局面

解题思路 这题别看题目复杂，其实上就是字符串得判断，因为他输出那一大堆其实就是一串字符串嘛

解题代码

知识点1：' '.join(s)，其中s是字符串列表，可以直接进行字符串拼接

知识点2：对于着这种换行输入直接用input()即可，不要用map容易出错，如果非要用map那么可以用一下代码来解决

202305-2

矩阵运算

解题思路：

解题代码

知识点1：矩阵得转置

知识点2： 列表推导式

列表推导式形式

展开为普通 for 循环的形式

知识点3： 列表和矩阵坐标之间得误解

2023003的真题

202303-1

田地丈量

解题思路：

解题代码

202303-2

垦田计划

解题思路：

解题代码

知识点1：二分法得模板

1. 精确查找目标值（使用 left <= right）

适用场景

2. 查找左边界（使用 left < right）

知识点2：注意 mid=(lift+right)//2，不要忘记加括号

202212的真题

202212-1

现值计算

解题思路 ：没有难度，把题目看懂即可，也就是说，看懂他让计算得是现值，也就是要用那个-k去计算，我们不在未来，未来的是预估收入

解题代码

知识点1：enumerate() 是什么？

知识点2： 数字得倒着遍历

202212-2

训练计划

解题思路 ：第一就是多开一位数组，容易记忆依赖关系

解题代码

知识点1：输出print(" ".join(map(str, res[1:])))

202209的真题

202209-1

如此编码

202206的真题

解包：恢复为原来的多个列表。解包的过程是通过 `*` 运算符完成的，它可以将 `zip` 对象中的元组重新拆分为多个独立的列表。输出为按照列排列得元组

创建字典：通过 `dict(zip(keys, values))`。

1使用 `dict()` 构造函数

知识点1：避免重复计算

知识点1：避免重复计算

解题思路
这题别看题目复杂，其实上就是字符串得判断，因为他输出那一大堆其实就是一串字符串嘛

知识点2：列表推导式

展开为普通 `for` 循环的形式

知识点3：列表和矩阵坐标之间得误解

1. 精确查找目标值（使用 `left <= right`）

2. 查找左边界（使用 `left < right`）

解题思路：没有难度，把题目看懂即可，也就是说，看懂他让计算得是现值，也就是要用那个-k去计算，我们不在未来，未来的是预估收入

知识点1：`enumerate()` 是什么？

知识点2：数字得倒着遍历

解题思路：第一就是多开一位数组，容易记忆依赖关系

解题思路：简单，略

解题思路：需要理解矩阵得颠倒，set提高运行效率，减少时间复杂度

知识点2：列表翻转

解题思路：傻逼题，题目难懂，0属于常数，虽然题目中没看懂

解题思路：用差分法解题，贴一下题解

解题思路：

解题思路：

解题思路：

解题思路：

解题思路：

代码收藏家普通

发表回复取消回复