T1 前缀和
题目大意
给定一个长度为 n 的数组，有 m 次询问。
每次询问：
求区间：
如果每次都遍历区间，最坏复杂度是 O(nm)。
可以提前预处理前缀和。
核心思路
定义：
表示：
> 前 i 个数的总和。
所以：
相减：
代码
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2 异或前缀和
题目大意
给一个数组，多次询问区间：
所有元素的异或值。
核心思路
普通前缀和使用减法：
异或有一个重要性质：
定义：
那么：
前面的数字出现两次，会全部抵消。
所以：
代码
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3 奖学金
题目大意
每个学生有：
排序规则：
1. 总分高的在前；
2. 总分相同，语文高的在前；
3. 语文也相同，编号小的在前。
最后输出前 5 名。
核心思路
这是典型的：
> 结构体 + 自定义排序。
把每个学生的信息放进结构体。
比较函数直接按照题目要求写。
代码
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4 第一个大于 X 的数
题目大意
给定一个升序数组。
找到：
> 第一个严格大于 x 的元素位置。
也就是找最小的 i：
核心思路
二分答案。
如果：
说明 mid 有可能是答案，但是左边可能还有更早的位置：
否则：
代码
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5 第一个大于等于 X 的数
与上一题只有一个区别。
这一题找：
代码
两道二分一定要区分
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6 撤硕管理员
这题是典型的：
> DFS 选或不选。
题目要求从 n 个同学中选择任意一些，使选择的费用总和是质数，求方案数量。([ACGO][1])
核心思路
枚举到第 id 个同学，有两种选择：
所以：
到最后判断：
代码
复杂度：
核心模板：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T7 全排列问题
题目大意
输出：
的所有全排列。
要求每个数字占 5 个字符宽度。([ACGO][2])
核心思路
定义：
表示排列第 x 个位置放什么。
vis[i]：
每一层 DFS 枚举：
代码
核心口诀：
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T10 [CSP-J 2025] 多边形
题目条件是：
若选择的最大木棍为 mx，总长度为 sum，则必须满足：
题目保证 n<=5000，a[i]<=5000。([ACGO][4])
核心思路
先排序：
假设：
是当前方案中的最大边。
那么条件：
移项：
所以问题变成：
> 从前 i-1 根木棍中选择若干根，统计子集和大于 a[i] 的方案数。
定义：
表示：
> 当前已经处理过的木棍中，选出的木棍长度和为 j 的方案数。
因为最大 a[i] 只有 5000，所以所有：
的和统一存到：
即可。
代码
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T11 [CSP-J 2022] 上升点列
这题核心是：
> LIS + 二维 DP。
将所有点按照：
排序。
对于两个点：
如果：
就可以连接。
两个点的曼哈顿距离：
中间需要添加：
个点。([ACGO][5])
状态
表示：
> 以第 i 个原有点作为结尾，已经使用了 j 个新增点时，最长点列长度。
代码
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T12 [CSP-J 2019] 纪念品
这题是非常经典的：
> 每两天之间做一次完全背包。
每天可以买同一种纪念品无限次，因此属于完全背包。([ACGO][6])
核心思路
考虑第 i 天买，第 i+1 天卖。
第 j 个纪念品：
收益：
当前拥有 m 枚金币：
于是做一次完全背包，求最大利润。
然后：
继续处理下一天。
代码
复杂度：
最关键：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T13 [CSP-J 2020] 方格取数
这题的移动规则决定了：
> 只能不断向右进入下一列，但是在同一列中可以向上或向下移动。
所以不能只写普通：
因为同一列可能：
也可能：
因此每一列需要做两遍 DP。该题是 CSP-J 2020 T4。([ACGO][7])
状态
表示：
> 到达 (i,j) 时能获得的最大价值。
对于每一列分别：
代码
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
