【保研算法题单】

基础算法

位运算

1. 801. 二进制中1的个数
   内容：(1)求二进制数中最后1的位置，int lowbit(int x){return x&-x};
   (2)求二进制数第k位的值。

高精度

1. 阶乘之和
   内容：高精度加法与高精度乘法结合
2. [模板题]高精度加法，高精度乘法(高精度x低精度)

二分

1. 一元三次方程有解
   内容：求三次方根的加强版。但是百步之内必有解药，题干强调了解空间的范围，以及两根之间的距离，所以想到在枚举两根之间的距离区间，每个区间都二分判断。
2. 跳石头
   内容：二分答案，将答案二分，每次看该答案能否在符合题意的情况下满足，判断是否符合题意是个难点。

搜索

深度优先搜索

1. P1219 [USACO1.5] 八皇后 Checker Challenge
   内容：经典问题，核心如何将二维性质的斜线转换为一维性质的数字：坐标相加/相减。但是相减会有负数，怎么办呢？加一个偏移量即可

广度优先搜索

1. 填涂颜色
   内容：对测试用例进行分析是重要的，尽可能的想到各种情况。比如此题边界1和外边界夹0的问题，可以通过外圈零来解决，并且也可以从外圈零开始搜索。
2. 马的遍历
   内容：方向向量

动态规划

1. 租用游艇
   内容：简单的一维dp问题，反而想复杂会解不出来。解空间集合：从1~i所有方法的花费。目的是求最小值。集合划分：任何集合的最后一步均为从某点k直接到i，以此为划分
2. 开心的金明
   内容：简单01背包变种。解空间集合：从1~i物品里选，总价格不得超过j。目的求题干要求的最大值。集合划分：以最后一个物品选还是不选划分。
3. 5倍经验日
   内容：如果失败却投入了药水必定亏，所以一个敌人只有打败和失败两种选择，再次转换为01背包问题
4. 装箱问题
   内容：仍是01背包问题，但不存在价值，而其实价值在这里就是容积
5. 采药问题
   内容：仍是01背包问题。
6. 通天之分组背包
   内容：最核心的点是将选物品，转换成了选择，然后组内再选，一定不要思维惯性
7. A+B Problem（再升级）
   内容：本质是多重背包问题，每个质数选还是不选，并且结合筛质数，先将质数筛出来。做的时候没想到多重背包问题

字符串

Trie树

1. 模板题
   内容：通过26叉树的形式维护字符串集合（字符串仅为小写英文/可数）。维护插入和查询操作。
2. 阅读理解
   内容：与模板输出查询次数不同，他是输出该单词存在于哪个文章，把cnt存值，改为cnt存数组即可。但是记得一定要抓住题目所有细节（比如去重）
3. 最大异或对
   内容：采用Tire树的形式将二进制串存储起来，其实刚开始摸这道题，思路对，但是就是没想出形式化的思路，只有简单的直觉。不过这确实启发我优化一个算法除了部分知识外，还可以从存储机构上入手。

数据结构

并查集

1. 修复公路
   内容：模板并查集算法，核心是集合操作；此题主要在于要与二分操作结合，因为该题明显是具有单挑性，时间越长，满足条件的情况就越多。【正解操作】，对输入排序后，进行并查集操作即刻，如果某次发现都在一个集合了，那么输出即可。

堆

1. 堆排序
   内容：每个结点总是大于其左右节点。插入、删除、修改、求最小值；以及On的建堆方法；核心是使用数组存储节点
2. 合并果子
   内容：哈夫曼树问题，每次找两个最小的合并即可。
3. 中位数
   内容：难度大。对顶堆，即小根堆和大根堆的组合。小根堆存放所有大于mid的数，而大根堆存放所有小于mid的数，所以小根堆的第一个是刚好大于mid的数，大根堆的第一个是刚好小于mid的数。不过这样使用堆确实也太难想了，想不到。

树

1. 求先序遍历
   内容：根据先序遍历和后序遍历的条件，使用递归求，善用递归很重要。

贪心

1. 跳跳！
   内容：贪心，每次选择落差最大的跳。平方，容易爆int，一定注意