- VERY EASY: day1, day2, day4, day6, day9, day11, day20
- EASY: day3, day7, day13, day16, day18, day19, day22, day24
- MEDIUM: day5, day8, day10, day12, day14, day17, day23, day25
- HARD: day21
首先建立从src到dest的映射表：用vector存储Tup，每个Tup是一个三元组，第一个值是src，第二个值是dest，第三个值是连续映射的长度。
然后对映射表按照第一个值排序，用二分查找找到最后一个src不大于key的项。接着判断src+len是否大于key，如果是，说明key在src表示的映射范围内，返回key-src+dest即可。如果不是，说明key是在表外的，返回key即可。
主要思路是用分治法构建seed to location的映射表，然后用二分查找到映射表上的区间范围，在这个区间范围里找每个区间的左端点映射的值，取最小值即可（因为每段区间上映射到的location是单调递增的）。
关键在于如何构建映射表。从seed_to_soil递归向下构建，首先根据上层调用传来的区间范围，找到这个区间范围在本层中映射到的每个区间，在每个区间上递归调用下一层，直到层数为0，将该层的区间插入到seed to location的映射表中。
很简单，跟着模拟就行了。
盲猜有环，然后对每个A起点计算其到Z终点的步数，这就是环的长度。最后对所有的环的长度取最小公约数。
DFS找环，用环的长度除以2即可。
考虑从每行开始，每经过一层“墙壁”则反转内外状态。计算所有在墙内的点的个数即可。
首先还是找环，然后将S点替换为等价的墙壁形状，接着从每行遍历，需要注意只有通过“L---7”或“F---J”或“|”才会改变状态，通过“L---J”或“F---7”不会改变状态（这一点坑了我好久。。。），我这里取巧，只有通过“|”、“F”、“7”才会改变一次状态。
直觉用DP，但是状态转移各种特判非常坑，DEBUG了好久。希望能有简洁的写法。
dp[i][j]表示i长度的前缀，匹配前j个连续段的个数。 转移方程：
- s[i-1] == '.', dp[i][j] = dp[i-1][j],必定是在前i-1个字符中匹配前j个连续段的个数
- s[i-1] == '#', 第j个连续段一定以s[i-1]结尾，所以往前找第j段的长度，假设长度为k，则dp[i][j] = dp[i-k][j-1]，必定是在前i-k个字符中匹配前j-1个连续段的个数
- s[i-1] == '?', 前两种情况之和。
注意初始化
dp[0][0] = 1;
for (int i = 1; i <= m; i++) dp[0][i] = 0;
bool flag = false;
for (int i = 1; i <= n; i++) {
if (springs[i-1] == '#') flag = true;
if (flag) dp[i][0] = 0; //如果前面有#，那么不可能匹配到0个连续段
else dp[i][0] = 1;
}part1的DP写出来之后，直接用到part2就行。
模拟
猜测有周期，用样例测了一下发现周期前还有前缀，于是考虑倒着用KMP算法，从右往左构建Next数组，当Next[i] * 2 == i + 1时，说明这个数组后缀有周期
但感觉还是有点靠猜了
本来以为只是一道很简单的dijkstra算法题，但是用最朴素的dijkstra算法却错了。
分析一通之后发现由于限制了直线走的步数，所以并不满足最优子结构（在1到i的最短路径path[1...i]上的某一点j，1到j的最短路径是path[1...j]），因为可能通过当前最优的点可能无法沿着最短路径前进。
于是我又写了回溯法企图暴力穷举，然后发现哪怕采取了剪枝，计算量还是太大了，不太可行。
来回折腾了快一天都没写出来，最后参考了reddit上的求助贴，要把一个网格点看成16个点，既方向（上下左右）和可能的连续长度（0,1,2,3）的排列，这样就可以遍历到所有可能情况。emmmm，最后还是dijkstra。
其实这题应该easy的，单纯是我太菜了。
改一下part1里的更新条件，保证连续长度在4以上，需要注意由于不能只在直线上走小于4格就停下，所以每次前进的步数为4或1（连续长度已经超过4）.
BFS模拟
不会写，摆烂了
DFS回溯法暴力
用DFS回溯法暴力算了2分钟，感觉收敛了，提交之后AC了
问题本身是NP-Hard，应该有贪心+概率的算法或者启发式算法可以逼近，但是想不出来了
二维平面上求出所有交点，然后判断一下是否在过去的路径上就行了
选三个冰雹，然后设它们分别经过$t_1$,$t_2$,$t_3$时间后位于同一直线上，然后列出方程：
发现是三元二次方程，用python的sympy库解出$(t_1,t_2,t_3)$，然后倒推出石子的速度$\vec{V}$，最后求出石子的初始位置$\vec{R_0}$。
求无向图无源最小割，和两个连通图的顶点数，一开始抄了stoer-wanger算法，但是不知道怎么直接得出两个连通图的顶点数，感觉还要再跑两次dfs。
然后注意到题目给的图是无权图，且最小割已经给定，可以用karger算法，当求得的最小割为3时停止，且两个连通图的顶点数明显是合并到最后两个未合并的顶点上的顶点数，于是直接计算即可。