7.12专题分享总结

  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$的边。