bzoj 2748: [HAOI2012]音量调节 DP

dp[i][j]表示唱完第i首歌,音量为j是否可行。

bzoj 3894: 文理分科 最大流

我们先不考虑一个人周围人选什么。建图就非常显然了。s连向所有人,流量为选文的满意度,所有人向t连边,流量为选理的满意度。然后我们考虑一下如果表示说自己和周围一圈四个人选择一样的科目带来的额外满意度呢。我们考虑新建两组点,分别表示一个人和周围四个人选文/理给这个人带来的额外满意度。我们从s连边到一个点[……]

Read more

bzoj 2743: [HEOI2012]采花 离线 树状数组

10^6的数据果然就算5s莫队也跑不过。。。。。。。。。卡常了半天,然后弃疗了。

正解挺神的。我们搞出来一个nxt数组,表示与i颜色相同的下一位在哪。

我们先把所有第二次出现一种颜色的位置+1。

然后把询问按左端点排序。

然后我们维护一个flag。我们看如果flag小于询问的[……]

Read more

bzoj 1218: [HNOI2003]激光炸弹 枚举

维护二维前缀和,然后枚举正方形

这么一道傻逼题竟然WA了好多次。。。开始自己YY了一个枚举点,然后点为正方形的顶点之类乱七八糟的。quq。

bzoj 1875: [SDOI2009]HH去散步 矩阵乘法优化

这题要求不能走一条边然后立即走回来。所以用点来进行dp不太好判断,我们考虑用边进行DP。dp[i][j]表示走完第i条边总距离为j的方案数。所有边拆成2条,然后用矩阵优化下转移就好了。注意矩阵不要搞太大,刚好就好,否则容易RE爆栈。开始在处理不能从自己的反向边走来的地方处理的不太好,然后GG。
[[……]

Read more

bzoj 1800: [Ahoi2009]fly 飞行棋 枚举

数据那么小,枚举一下,维护个前缀和判断就好了。

bzoj 2467: [中山市选2010]生成树 奇妙推论

我们考虑,一个n五角星圈,由4n个点,5n条边,变成树要删n+1条边。可以感受到,一个五边形至少删一个边。那么还有一个五边形删了2条边。并且其中一条一定在内环。那么答案就是 4 * n * 5 ^ (n – 1)

不太懂神犇们用的奇怪数学定理矩阵乱七八糟的是啥。
[crayon-5bef0a[……]

Read more