1.结构体排序:
当一个对象有多个属性(如学生有姓名,成绩,学号),我们用结构体把它们打包在一起。排序时需要自定义比较规则;告诉sort函数谁在前面
核心要领:
* 比较函数时,返回true表示第一个参数排在前面
* 多关键字排序:当第一个关键字不等时,再比较第二个关键字,以此类推。
* 用struct定义结构体,把相关数据组织在一起。
识别信号:
* "按x排序,若相同则按照y排序"
* "输出所有人的排名","第k名","前m名"
* 稳定排序需要用stable_sort
2.筛法
判断质数和批量求质数是两个不同的问题:
* 判断质数(试除法):判断单个数n是否是质数,只需要从2到√n遍历查看是否有n的因子即可。
* 批量求质数(埃氏筛):批量求1-n内所有质数,从2开始,每找到一个质数就把它的所有倍数标记为和数,时间复杂度是O(n log log n)
埃氏筛代码:
3.枚举
枚举三要素:
* 确定枚举对象:要枚举什么?(枚举答案、枚举子集)
* 确定枚举范围:循环从哪开始到哪结束?
* 合法条件:什么样的对象是题目要求的答案?
识别信号:
* 枚举算法的数据范围通常都不大(NNN ≤\le≤ 1000)。
* "所有方案","有多少种可能","恰好满足"
4.贪心:
贪心算法的核心思想是每一步都做出当前最优的选择,希望局部最优能推导出全局最优。
使用条件:
* 排序后才能选择。
* 区间贪心(按开始时间/结束时间/时长排序)
5. 二分查找与二分答案:
* 二分查找:在有序数组中查找目标值,每次比较中间元素,将搜索范围缩小一半。时间复杂度O(logn)
* 二分答案:要求解最大值最小或最小值最大,不直接求解,而是二分猜答案,每次check当前猜测是否可行。
6.双指针:
概念:双指针是一种用两个指针(变量)在数组或序列上同时移动来解决问题的技巧,核心思想是避免不必要的重复计算。
常见类型:
* 同向双指针(滑动窗口):两个指针同向移动,维护一个窗口。用于"最长/最短连续子序列"的问题。
* 相向双指针:一个从头,一个从尾向中间靠拢。用于有序数组上的查找。
识别信号:
* 暴力需要O(n2n^2n2)的双层循环,且内层循环的起点随外层单调移动。
7.前缀和与差分:
前缀和:预先处理好前缀和数组s[i]=s[i-1]+a[i],之后任意区间[l,r]的和可以O(1)计算出s[r]+s[l-1]。
差分:差分是前缀和的逆运算。构造差分数组d[i]=a[i]-a[i-1],对区间[l,r]整体加减一个值,只需要修改两个端点就能修改整个区间d[l]+=v,d[r+1]-=v。
识别信号:
* 要多次修改区间的和:前缀和预处理
* 要多次修改区间的值:差分
8.STL数据结构:
容器 特点 用途 stack 后进先出 括号匹配,表达式求值 queue 先进先出 BFS map 键值对 计数,离散化 set 有序不重复的集合 去重、查找
9.递归与深搜:
递归:函数自己调用自己的技巧,本质是把大问题分解为相同结构的子问题。
深搜:是递归最重要的应用之一,从一个状态出发,沿着一条路径走到底,走不动了就回到上一个状态,尝试其他路径。
10.广搜:
广搜:是逐层扩展的搜索方式:先访问距离起点为1的状态,在访问距离为2的状态,以此类推。
11.递推与动态规划:
递推:用已知的数学公式/数学规律,从小到大推出位置的项。
动态规划:把问题分解为更小的子问题,用状态数组描述这些子问题,通过状态转移方程,由小到大的计算出子问题的值,从而得出原问题的解。
12.文件读入读出:
读入:freopen("文件名","r",.stdin)。
读出:freopen("文件名","w","stdout")。
关闭读入读出流:fclose(stdin)//关闭读入流,fclose(stdout)//关闭读出流。