BZOJ水题泛做

我已经做了5/100


1001: [BeiJing2006]狼抓兔子

学了下平面图的技巧,对于每一个构成的空间重标号,然后平面与平面之间连边,重新构造一个另外的起点,于是最小割转为最短路


1002: [FJOI2007]轮状病毒

生成树计数,考虑Matrix-Tree定理,一棵n个点的图的生成树个数等于他的基尔霍夫矩阵的n-1阶主子式的行列式的绝对值。

但是考虑到这题会出现高精度的情况,而高乘高加再搭配高斯消元,三高无法承受,只能另寻他法

然后vfk提出了一种很快的线性递推方程,于是就A了这题


1003: [ZJOI2006]物流运输

直接做不好做,我们发现其实我们可以求出第i天到第j天不改变路程最少每天需要走的路程

然后这就变成了一个很简单的动态规划,设dp[i]表示前i天的答案即可。


1004: [HNOI2008]Cards

由于每个颜色都有数量限制,考虑burnside引理

本质不同的方案数有

\frac{1}{m+1}\sum_{i=1}^{m+1}\Gamma (i)

其中\Gamma(i)表示对于第i种置换会有多少个点不变

而我们知道,对于一种置换,考察其循环过程,每一个点i,在经过一段连续的置换后,还原成初始点,他的颜色在这段置换中是一定不会变的。

因此我们可以根据这个关系,设dp[i][r][b][g]表示前i段置换,各种颜色数量分别为r,b,g的不变点个数,这显然是一个背包问题,我们可以把第一维降掉

不要忘记可以不进行置换。


1138:[POI2009]Baj 最短回文路

吼题啊,很容易得出一个方程f[x][y]表示xy的最短回文路。

这么暴力转移的时间复杂度是O(n^{2}),有点辣鸡。

我们不妨加一维,记方程g[x][y][z]表示xy,最后一条边的边权是z的最短回文路

那么f[x][y]=min\begin{Bmatrix}g[x][a][z]+1\end{Bmatrix}\;\;\;(a->z->y

然后g也可以用f推出来

这样就O(nm)


 

发表评论