[BZOJ 1002]轮状病毒

根据Matrix-Tree定理,这题可以求出基尔霍夫矩阵,然后当成行列式求值即可

这样做并没有什么错,大概也能AC,但是时间复杂度是立方级的,并且写起来并不简单(要用到高斯消元什么的,更何况此题还要用高精度)

或许DP也可以?

不过有一个简单的递推式:d[n]=d[n-1]*3-d[n-2]+2

证明比较麻烦(绝大多数人是找规律出来的),可以到这找:http://vfleaking.blog.163.com/blog/static/17480763420119685112649

这题要用高精也太烦人了,我就用了Python写(Python语法真特么烦人啊)

Q:真要考试你交Python啊?

A:我用Python打出来表然后交表啊。

代码:

继续阅读

[BZOJ 4390]Max Flow

这明明不是道网络流题。

这就是道树剖题……

没有什么太难的地方,然而还是调试了几遍才过。

代码:

继续阅读

[BZOJ 2456]mode

原来这就是BT众数题的始祖啊~

首先讲一下方法(这种方法其实叫摩尔投票法):

继续阅读

[BZOJ 4196]软件包管理器

终于A了!

在CodeVS,洛谷甚至UOJ上各种A

但是在BZOJ上各种TLE。BZOJ评测姬自带10倍常数?

这题处理安装很简单,一直溯到根。

删除……注意一下树剖的一些神奇性质。

继续阅读

[BZOJ 1036]树的统计

终于A了这题了!

树剖大水题~

然而zzs这种蒟蒻还是要交很多次才过:

继续阅读