AcWing 1. A + B
语法I/O题
- py3 版
import sys
for line in sys.stdin:
print(sum(map(int, line.split())))
print(sum(map(int, input().split())))
AcWing 2. 01背包问题
0-1背包。降维优化，下标自后往前计算。
AcWing 3. 完全背包问题
完全背包，状态方程转换，下标自前往后计算。
AcWing 4. 多重背包问题 I
多重背包，朴素版
AcWing 5. 多重背包问题 II
多重背包，转0-1背包+二进制优化
AcWing 6. 多重背包问题 III
多重背包，单调队列优化
AcWing 7. 混合背包问题
混合背包，分类调用 0-1、完全、多重 三类背包问题
AcWing 9. 分组背包问题
分组背包，0-1背包变种，以组为单位做0-1背包，每组遍历尝试每一个。
n, m = map(int, input().split())
dp = [0] * 110
while n:
gps = [tuple(map(int, input().split())) for _ in range(int(input()))]
for j in range(m, -1, -1):
for (v, w) in gps:
if j >= v:
dp[j] = max(dp[j], dp[j - v] + w)
n -= 1
print(dp[m])
AcWing 16. 替换空格
基本语法，字符串处理
AcWing 17. 从尾到头打印链表
1. 递归的基础理解
AcWing 21. 斐波那契数列
1. 公式递推
2. 矩阵快速幂
AcWing 23. 矩阵中的路径
dfs基础，注意递归时的现场恢复
AcWing 26. 二进制中1的个数
位运算，n & (n - 1)
AcWing 29. 删除链表中重复的节点
链表维护工
AcWing 34. 链表中环的入口结点
快慢针+数学分析
AcWing 35. 反转链表
1. 3针翻转
2. 递归的基础理解
AcWing 36. 合并两个排序的链表
归并排序基础操作
AcWing 78. 左旋转字符串
空间$O(n)$：截段拼接
空间$O(1)$：3次翻转法
AcWing 79. 滑动窗口的最大值
单调队列
0始排位下标，报数自1开始，n个人报m个数的经典约瑟夫环问题
数学推导公式
AcWing 84. 求1+2+…+n
递归退出条件
(n>0) && (res += getSum(n-1))
AcWing 87. 把字符串转换成整数
基础api
AcWing 89. a^b
$a^b \mod p$ ，快速幂以及mod性质
AcWing 858. Prim算法求最小生成树
Prim 算法
遍历边实现 + 优先队列实现，比较和Dijkstra的异同
AcWing 859. Kruskal算法求最小生成树
Kruskal 算法
获取边，排序，并查集求最小生成树
AcWing 1140. 最短网络
最短生成树
读取上(下)三角的边，然后上Kruskal
AcWing 1141. 局域网
总边长-最小生成树
AcWing 1142. 繁忙的都市
最小生成树 + 生成树的最大边
使用Kruskal较方便
AcWing 1143. 联络员
必选边限制下的最小生成树
使用Kruskal较方便
AcWing 1144. 连接格点
必选边+特殊大小边的图+最小生成树
先处理必选边，再处理竖向的小边，再处理横向的大边即可
加油啊
冲！