7.12所讲的题目的落实，涉及图论、计数和思维题。
T1-LuoguP4609
第一类斯特林数＋组合数
题解见之前的博客
间章-关于第二类斯特林数某一公式的证明
证明：
将$m$个本质不同的小球放入$n$个本质不同的盒子（可空）中，显然是$n^m$。
另一种思路表示先枚举$k$个盒子非空，乘上$\begin{pmatrix} n\k\end{pmatrix}$表示从$n$个盒子中选出$k$个盒子，将这些球放进这$k$个盒子的代价是${\begin{Bmatrix}m\k\end{Bmatrix}}\times k!$，乘上阶乘是因为盒子本质不同。
和 $n$ 有关的只有 $C_n^k$，而这东西是可以利用杨辉三角快速转移的。常见于$\text{DP}$题以及多项式题。
T2-Bzoj4710
容斥原理＋组合数
题解见之前的博客
T3-CodeForces 961G
不难发现$Ans=p\sum val_i$（因为每个元素本身的权重是相同的），其中$p$是一个待定的系数。
有一种斯特林反演的方法，但是式子推起来很麻烦。
另一种思路是考虑划分集合后，因为$W(S)=|S|\cdot\sum_{i\in S}val_i$，故对于元素$i\in S$可以当做$S$中的每个元素都对$i$产生了一次贡献，所以我们只要枚举每一个数对$i$的贡献即可。
$i$对自己的贡献显然是$\begin{Bmatrix}n\k\end{Bmatrix}$，剩下的$n-1$个数的贡献则是$(n-1)\times\begin{Bmatrix}n-1\k\end{Bmatrix}$。
其中$\begin{Bmatrix}n-1\k\end{Bmatrix}$表示枚举的那个数和$i$在同一集合的方案数。
所以系数$p=\begin{Bmatrix}n\k\end{Bmatrix}+(n-1)\times\begin{Bmatrix}n-1\k\end{Bmatrix}$
T4-CodeChef CNTDSETS
将平移的限制转化为每一维都存在该维坐标为$0$的点，距离的限制转化为至少有一维的最大坐标为$d$。
考虑计算最大值小于等于$x$的方案$f(x)$，容斥“每一维都存在$0$”。答案就是：
T5-CodeForces 892E
考虑最小生成树$\text{Kruskal}$的一个性质，即不同权值的边是互不影响的。对于每一次询问，我们只需考虑同种权值的边能否出现在一棵生成树上。
预处理处每一种权值在处理之前该边对应的两点所在的联通块，然后对于每一次询问，先还原询问的每条边的连接状态，再去按照$\text{Kruskal}$连接所对应的的联通块，如果不会连接到相同的联通块，则是可行的。
T6-Bzoj4886
其实并不用考虑严格递增的问题，我们只需要使得底不重复出现就行了。
考虑一种建图方式，对于一个长方形$(a,b)$，建立一条$a$与$b$的无向边，考虑给边定向，则入点表示选其作为一个底，出点表示作为一条高，由于题目限制，每个点的入度必须为$1$，所以贡献为$(\text{degree}-1)\times \text{val}$。
因为只有$n$个点$n$条边，所以一个联通块的形态要么是树要么是基环树，然而树的根节点贡献是$\text{degree}\times \text{val}$，所以我们对于树要使权值最大的点为根（你可以认为其入度为$1$，但并不减少贡献）。
T7-LuoguP4366
主要解决边数很多的问题，剩下的细节就只有原图单向边和不要用优先队列就好了。
考虑到异或的性质，只需要对于每一个节点$i$，枚举每个二进制位$p$，连边$(i,i\oplus(1<<p),(1<<p)*c)$即可，边数缩减到$O(nlogn+m)$。
T8-LuoguP1407
考虑给边定向，对于婚姻关系，男向女连边，对于曾交往过的关系，女向男连边，如果一对婚姻关系中的两人在同一个强连通分量里面，则这对关系是不稳定的。
考虑这样做为什么是对的，一对不稳定的稳定关系必然处在一个环满足这个环上的边按婚姻－交往－婚姻－交往环形排列，所以以上联边方法可以保证将答案最大化。
T9-Atcoder2134
按照原题连边的话边会达到$O(nq)$，所以我们考虑如何缩小边的规模，考虑一次批量加边对$\text{MST}$的贡献，假设我们已经把边$(x,y,z)$按照$\text{Kruskal}$的方式处理完毕，则表示$(x,y)$两点在同一联通块内，所以我们不妨考虑将边$(y,x+1,z+1)$等效变为$(x,x+1,z+1)$，对于原图中的一次批量加边操作，设$d[i]$表示$(i,i+1)$的最小边权，每次仅需更新$d[x],d[y]$。（注意边$(x,y,z)$是无法等效的，直接加进即可）。
最后两次环形更新$d[i]=min(d[i],d[i-1]+2)$，更新两次是因为第一次中的最末尾的$d$可能更新最头的$d$。
然后将$(i,i+1,d[i])$加入图中，求出$\text{MST}$。
T10-Bzoj1922
一边跑$\text{Dijkstra}$，一边跑拓扑排序即可，只有一个点的保护点都出堆，该点才能入堆。
T11-Uoj67
删去一个点后只剩$n-1$个点，树有$n-2$条边，所以原图中有$m-(n-2)$条连边的非割点就是答案。
T12-Bzoj4289
考虑一种网络流式的建图方式—补流，有这样一个东西$max(a,b)=a+max(b-a,0)$。
所以对于每一个点，我们经过时可以加上它入边的权值即$a$，然后考虑在点的内部补差值。
具体来说，对于每一个点，将其所有的边从小到大排序，从小往大连差价边，从大往小连$0$边，也就是说，实际上原图的$n$个点并不用加入图中，直接将拆出来的两个点$(i,i+m)$间连权值为$w$的边，然后将$i$分配到编号小的点，$i+m$分配给编号大的点，作上述操作。
最后考虑怎么求出最短路，对于分配给$1$的出边，新建源点向$i$连边权为其$w$的边，对于分配给$n$的入边，向$i+m$连权值为$0$的边。