算法比赛复习

陆陆续续四个多月的学习小总结，具体题目和题解在下方：

写了这个总结后，又做了一些真题，结果发现是一些特性不符合比赛的编译器版本，所以有些基础的转换还不太行，还有一些奇怪的输入，其他的都还好，我寻思着，这比赛不考多点算法的东西，整这么多奇葩的输入干啥。

字串问题和并查集和大数问题（以及进制）需要补充

容器以及algorithm算法部分

对以下容器和不同类型数组的使用有一定的理解
string,
vector,list,deque,
queue,stack,
priority_queue
set,unorder_set,
map,unorder_map
father数组，树状数组
a[] a[][] a[][][]

algorithm库的使用 max,min
*max_element,*min_element
sort,heap_sort
next_permutation
fill memset
swap
reverse
lower_bound,upper_bound

算法部分

总结链接

1.递归{ ①1.92. 递归实现指数型枚举 ②. 93. 递归实现组合型枚举 ③. 94. 递归实现排列型枚举 }
。
2.dfs{ ①迷宫问题 ②固定方向路径数问题 ③皇后问题（dfs+回溯） }
。
3.bfs与逆向bfs{ ①迷宫问题 ②单源到单源单位长读最短路径 }
。
4.回溯（dfs+回溯）{ ①全排列问题 ②括号生成与括号配对问题 ③皇后问题 ④岛屿问题 }
。
5.最小生成树(kruscal+并查集){ ①抽象成点的连接的最小代价问题 ②村庄（城市）通路问题 }
。
6.单源到多源最短路(dijkstra){ 从某个点i到其他任一点的最短距离 }
。
7.多源到多源(floyd){ 抽象成n个点两两最短路问题 }
。
8.拓扑排序{ 做一系列的事情，需要前置条件 ①课程表 }
。
9.dp{ 1)线性dp： ①路径问题 ②背包九讲 ③不相邻背包 ④序列和以及序列最值问题 ⑤记忆化搜索dsf+dp 2）区间dp： ①区间dp转换成线性dp 最长公共子序列 }
。
10.各种排序{ 插入排序，二分插入排序，希尔排序，选择排序，堆排序，冒泡排序，归并排序，快排 }
。
11.数学问题（GCD，快速幂，矩阵快速幂）{ ①GCD ②快速幂 ③矩阵快速幂 ④朴素素数 ⑤埃筛 ⑥欧拉筛 }
。
12.前缀和{ ①一维前缀和 ②子矩阵和 ③树状数组解决前缀和以及动态数组的插入问题 }
。
13.二分思想{ 找一个开区间，使得ans一定在区间里，对半分区间，并且具有二段性（有且仅有一个区间存在ans) ans一定在左区间的右端点，或右区间的左端点。因此每次更新l或r，都设置为区间的端点。最终若端点为ans即存在，否则不存在。
①模板1：确认ans在左区间-> r=m； m的计算保持不变。 ②模板2：确认ans在右区间->l=m；
m的计算应该改为：m=(l+r+1)/2; }

。===========================================================
。
最后需要学习的东西：
1.set map 操作 √
2.二分，前缀和 √
3.一道递归题 1h33’ -2h6’
4.一道模拟排序：1h9’ -1h25’
5.树状数组、线段树 √ ⚪
6.贪心