2018暑假七林集训（一）

day1

考试……

orz dyh大佬rank1

day2

考试……

day3

考试……（感觉好像越考越简单，也许是一定是我的错觉）

day4

今天终于开始讲课了。

1. set：upper_bound与lower_bound，分别是求元素值大于查找值的第一个元素的位置与元素值大于等于查找值的第一个元素的位置。


2. multiset：可重集，具体操作和set基本一样，就是一个可以保存重复元素的set。


3. ST表：后面单独开坑吧。


4. 树链剖分：同上

orz tyz大佬rank1

day5

考试……

orz dyh大佬rank1 240分

day6

说好的“基础”搜索呢，讲二进制优化就算了，居然将启发式搜索技术A*。可能我对基础的理解的偏差吧。。。改天开个坑讲A*。至于模拟退火，简直是玄学呀，蒟蒻已经完全懵逼qaq。DFS基本上还是会的，就不说那么多了。

再次orz dyh大佬rank1

day7

各种玄学的二分题目。。。刷新三观呀。凸优化到时候单独开坑吧。二分的方法总体还是很灵活的，就不一道一道题单列出来了。

orz dyh大佬再次rank1

day8

今天是"基础"DP。DP的题套路还是有的，但是又不好想，所以这里把每道例题单列一下。

1.01背包：太简单不解释

DP时不清楚状态转移的顺序时，可以使用记忆化搜索

2 .完全背包：同上

3.多重背包：优化——二进制打包

eg：

自然数拆分——转换为二维完全背包

最长路——记忆化搜索或拓扑排序

最长上升子序列——基础算法，nlogn算法：二分优化

滑雪——记忆化搜索，略

合并果子——区间DP（虽然好像可以用贪心……）

加分二叉树——树形DP

树上最大独立集——同上

树上最大独立集2——基环树DP，思路：断掉换上 的一条边，假设端点为x和y，显然x和y至少有一个不能选，以x，y费别为根，跑一次上题的DP。

基环树：删去图上环的任意一条边即可变成一棵树，称为基环树

树上背包——略

搭建双塔——刷表转移

BZOJ3928（洛谷P4766）——区间DP，将外星人视为线段

POI2015 Myjnie——又是一道区间DP，三维状态转移，总复杂度O()。

作为一个蒟蒻，再次被大佬们吊打了一早上，感觉下午考试要炸。

orz dyh大佬再次虐场

day9

今天就是最后一天了，又是考试……今天的题很水，一个半小时就做完了。T3莫名TLE，大佬说可能是林老电脑太慢。。。

orz wjk大佬rank2

这个暑假的集训就结束了，接下来准备开始刷题和补博客的坑qaq。