程序设计实习实验班2017推荐习题

2017年6月24日1,6911

区间众数问题

这题写莫队是最容易的,可以对于每种出现次数的数字维护一个堆,用于删除时维护答案

【BZOJ3659】Which Dreamed It 神奇钥匙

求以1为起点的欧拉回路的个数乘1的度数

BEST theorem

【bzoj4031】[HEOI2015]小Z的房间

矩阵树定理

推荐阅读

POJ2373 Dividing the Path

用 dp(i) 表示覆盖到 i 的最小喷水装置数,单调队列优化 dp

Squares

预处理每个点向右和向下延伸的线段长度,枚举每个正方形左上角的点和边长

CF449D Jzzhu and Numbers

膜zmx(洵老师233):

直接做不好做,考虑容斥,求出f[s]表示选出若干个数字and起来之后对应于s二进制表示中为1的那些位置必须是1的方案。

考虑and的FWT的过程。

当前只考虑选出1个数字的话,令g[s]表示给定的数中s出现次数。

tf (g ) = (tf (g 0 + g 1), tf (g 1))

事实上就是处理了最高位的情况!这样继续分治下去做就可以弄出只选出1个数字时的f[s]。

考虑取若干个的情况,那么f[s]对应的可选集合{x1, x2, · · · , xf [s]}中的数任选,最后and出来都能保证对应于s的那些位置仍然为1。

令ans[s] = 2^f[s],这里的ans[s]即为选若干个数使得它们and起来对应s的位置必须是1的方案数。

考虑FWT的“意义”。

g[s]表示了and起来恰好是s的方案数,那么做了一次FWT之后求得

了and起来至少是s的方案数tf (g)。 那么IFWT的意义就和FWT相反。

ans[s]表示and起来至少是s的方案数,那么做了一次IFWT之后求得 了and起来恰好是s的方案数utf (ans)。

所求答案就是utf (ans)[0]。

SRM518 NIM

FWT xor 卷积

 

  • Name :Chouti2017年6月29日 下午9:32 回复

    黄学长怎么区间众数强行多个log啊 不太行吧

    #1