Codeforces 1005F
题意：给你一个$n$个点$m$条边的无向图，要你选出$n-1$条边。你要在其中找到$k$种方案使得图连通并且 1 点到所有其他点距离之和最短。不足 $k$ 种就输出所有方案。

本题运用了最短路树的知识，最短路树就是一个点到其他点最短路的边组成的树。这个树可能有很多个。构造树的方法就是用最短路算法松弛时如果发现最短路相等，那么这里就有两条边可选进最短路树。
这里边权都是1，直接 BFS 。然后 DFS 每个点选一条边进最短路树即可，注意这里可能数组开不下，vector.resize() 就排上用场了。

知识点：
1 求最短路树长度相等时不要再入队, 否则计数会有重边
2 要记得删除调试输出
3 vector.resize() 的绝妙之处

Codeforces 1051D
题意：给一个$2$行$n$列的矩阵填上黑色和白色，求连通块个数为$k$个的填色方案数量。
好像这题和之前 edu 一题很像……
刚开始可以想到$dp(i,j,k)$为第$i$行第$j$列有$k$个连通分量的方案数，但是转移比较困难，不知道前面那一列的颜色，用包含行的状态也不好进行转移，所以我们要删去行的状态，增加颜色的状态，这里可以利用状压 DP 思想将最后一行状态压起来，问题就基本上能解决了。
$dp(j, k, st)$表示前$j$列有$k$个连通分量，$j$列的状态为$st$的方案数，然后转移即可。
具体转移看代码即可，太长了……
知识点：
1、DP 状态如果不方便转移，要想一想为什么不方便转移，是否能增加状态或者排序贪心等。增加状态也不一定只能增加一个，可以增加2个甚至很多个，可以使用状压的方法。

Codeforces 1051F
题意：给出一个边比点数多至多$20$条的无向连通图，每条边有一个边权，多次询问两点间最短路。
由于特殊条件，我们可以随便建一棵生成树(又称 DFS 树)，然后就会只有最多$20$条边不在树中。
对于每个二元组询问$(u,v)$，我们答案有两种情况：
1、只走树上的边
2、必须经过一条树外的边
对于第一个很容易用 LCA 求出来。对于第二个，我们记录这条边的一个顶点$i$，然后用 dij 求出顶点的单源最短路，必走这条边的代价等价于$dis(i,u)+dis(i,v)$，因为这样的路径$(u,v)$就能覆盖这条边。两个情况取最小值即可。
知识点：
1、这种有特殊性题目可以将图转化为树，noip 货车运输是同样的思想，区别在于本题是随便一个生成树( DFS 树)，而 noip 那题是要最小生成树
2、本题也一定程度上与 相同，最短路之后枚举边求解

Codeforces 1042F
题意：无向无根树$n$个点，要将树叶分成集合，使得每个集合中任意两个叶子距离小于等于$k$，问能最少分成几个集合？
题目是最优化问题。所以我们可以考虑贪心 / DP 等方法。本题要将无根树转化成有根树。之前做过一题不会把1当做根，这题如果用1会出问题(1可能是叶子)，具体看样例2。所以我们要选一个不是叶子的点作为根即可。
知道这个然后就是(下文来自此处，侵删)
对于每一个儿子，保存最大距离的叶子(合并思想)，然后排序之后，找到一个$R​$使得$[1,R]​$可以在一个集合内(集合中任意两个数大小不大于$k​$求法)。
然后将$[R+1,son]$内的点都各自成立一个集合。然后这个节点作为儿子的返回值为R点的$dis+1$。(感性理解一下，集合中任意两个数大小大于$k$，不能并到其他集合了)

本题几个要点:
1、根的选取 2、最长距离才有用 3、集合中任意两个数大小小于$k$求法
知识点：
1、集合中任意两个数大小不大于$k$，那么可以排序然后如果存在$a_{i-1}+a_i \leq k$，那么$i$是一个临界点，左边的(包含临界点)任意两个数大小小于$k$，右边反之。

Codeforces 1047C
题意：给你一个序列，你需要删除其中一些数使得序列GCD比原序列GCD大。
将所有数除以 GCD，然后现在对数进行质因数分解，那么每个质因子都可以乘回 原序列GCD 然后比 原序列GCD 大。但是质因数分解这里时间不太够，我们可以线性筛，用质数去找它的倍数，统计一下有几个数在序列中，越多越好，这样删的数就越少
(我数论太弱了，筛选都不会，GG
知识点：
1、线性筛时间复杂度大约$O(nlog(logn))$
2、将数字除以 GCD 数很好的思路

Codeforces 1042D
题意：给出一个序列，求出有多少个区间满足区间和小于$t$。
解：先处理前缀和$pre$，对于题目$pre_r-pre_l < t$成立即可。移项$pre_r-t < pre_l$，那么只需要检查$[1,i)$中的$pre_i$有多少个大于$pre_r-t$即可，右边不取因为前缀和的定义。这里方便没有将$l$写作$l-1$。可以取反做，也可以正着做。
然后就是求$[1,i)$有多少个大于$x$的数了。这个如果直接维护序列下标很难求，我们可以用树状数组维护值域，然后询问区间和就行了，但是要离散化。这题也可以维护下标，用一个平衡树求 $rk$ 即可。
知识点：对于区间维护，可以有两种形式
1、维护序列下标
2、维护值域
对于这个区间比某数大的，要想到在值域开线段树/树状数组

BZOJ 1433
题意：见上。
本题很容易看出是一个二分图最大匹配的题目。
将左边点抽象化为人，右边为床，边就是分配。然后分类讨论一下连边情况，最后看二分图最大匹配是否等于要安排的人即可。
知识点：
1、初始化数组要全部初始化，输入数组也要初始化
2、赋值时考虑是否会覆盖之前的值

BZOJ 1880
题意：求出$s_1$到$t_1$的最短路径与$s_2$到$t_2$的最短路径的最长公共长度是多少。
解：我们求出四个点出发的单源最短路，然后枚举一条路径$(i,j)$，判断这条路径是否在两条最短路上，用公式算出公共长度，然后更新答案即可。
Hack，枚举的路径不一定在两条最短路径的公共路径上，必须要先预处理出每个点是否在公共路径上，因为每次枚举的最短路径端点都要在公共路径上。
知识点：本题运用了最短路加枚举，与CF 544D思路类似。

最短路图+拓扑排序+DP 做法：
最短路图：所有$dis(s,i)+dis(j,t)=dis(s,t)$的边$(i,j)$组成的 DAG 图
将$s_1$到$t_1$最短路图求出来并且和$s_2$到$t_2$的最短路径求交，然后在 DAG 图上按照拓扑序求最长路。

1119 灾后重建
解：对于 Floyd 的方程式$dp(k, i, j)$是只有前$k$个点中$i$到$j$的最短路径，对于转移, 路径$(i,j)$有过$k$点或者不过$k$两种状态。然后滚动数组得到普遍的那个方程。
对于这题因为$t_i$单调递增，并且询问$t$也单调递增，所以每次相当于加入一些点。Floyd 的方程就能完成这一点。每次更新到只有前$k$个点即可，这$k$个点都是重建完的。答案就是$ma_{ij}$，并且起点终点重建完了。

知识点： Floyd 的方程式$dp(k, i, j)$是只有前$k$个点中$i$到$j$的最短路径
此题与CF 1037D都采用了将第一层循环灵活运用的方法。

Codeforces 1028E
题意：给你一个环$b$，要你构造一个环$a$，满足$a_i \% a_{i + 1}=b_i$

设$max(b)=mks$，要找到一个数$i$使得$b_i=mks$并且$b_{i-1} < b_i$
然后让$a_i=b_i$，然后后面的就按照$a_i=b_{i+1}+b_i$来算。对于前面的约束也很清楚了，否则余数不对。
然后就是注意无解当且仅当所有数相同并且不是$0$。
然后还要对$0$作出特判。
1、所有数都是$0$，直接输出$n$个相同数即可
2、如果当前$b_i=0​$并且$a_i=mks​$，那么$a_i​$要乘$2​$，否则无法通过下面数据

5
0 0 0 100 0