牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

省选模拟60 题解

A. 摧毁图状树考虑一个暴力做法。维护一个堆，每次取出深度最大的点，如果他还没有覆盖，那么就给答案增加 $1$。否则直接跳过，然后直接跳到他的 $k$ 级祖先加入堆中，复杂度是 $O(n^2log)$ 的。然后发现这样一个事情，这个复杂度肯定是不满的。比如说对于单次操作，复杂度大...

树状数组期望 dp

2020-04-03

0 746

杂题

1.容易发现题意中的子序列没啥用，其实要求的是集合个数。然后考虑并不是所有的点对都是需要关注的，处理的方法是把所有的数按照大小排序。其实按照大小排序就是 $0/1 tire$ 树的样子，所以这样做的话，一个集合中的两两最小异或值实际上就是按照顺序的两两异或值的最小值。然后只要考虑每个...

dp 期望容斥字符串组合计数

2020-04-07

0 457

省选模拟69 题解

A. 最小生成树因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，所以最优的策略肯定是将这棵树弄成一个菊花图。然后考虑把所有的边权按顺序列出来。如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。那考虑一个特殊的情况，如果说...

二项式反演多项式动态dp dp 分治构造题结论题容斥贪心

2020-04-13

0 381

省选模拟70 题解

A. 小 Y 增员操直播群考虑一个暴力做法，每次枚举较小的集合的大小，在判断合法之后可以直接将原问题划分为两个子问题。两个子问题是互不干扰的，所以直接 dp 就好了。然后可以发现枚举大小是没有必要的。考虑与元素 $n-1$ 连边的最小的点 $x$。如果两个集合大小相等，那么 $x...

线段树 dp

2020-04-14

0 362

省选模拟75 题解

A. 比特币考虑把第 $k$ 位为 $1$ 的问题放在模 $2^{k+1}$ 意义下考虑，这样问题就简单了。因为若干个循环的贡献被强制放在了同一段上考虑。然后随便弄个数据结构维护一下即可。 B. 测试类似约数个数和一题，可以用类似的构造方法来展开 $d(i*j*k)$ 这个函...

数学莫比乌斯反演多项式 dp 斯特林数

2020-04-20

0 403

省选模拟76 题解

A. MiniumCut 首先看到这个题，可以想到最小割树。然后发现原图的最小割树与原图是等价的。那也就是说，答案可以表示为一个树。然后考虑如何求出来这个树。大概的思路就是由小到大考虑每一组关系或者由大到小考虑每一组关系。这里用后一种思路，大概套用一下类似克鲁斯卡尔重构树的思想，然...

最小生成树回文自动机 Hash dp

2020-04-21

0 419

省选模拟80 题解

A. 数字如果枚举 $x\ and \ y$ 的取值，可以进行一个简单的dp。 $dp_{i,0/1,0/1,0/1,0/1}$ 表示从高到低到第 i 位，最高的几位分别是否与 $lx,rx,ly,ry$ 相同，然后这个 dp 数组的取值也只有0/1。所以可以 dp 套 dp。在考虑过...

分块多项式 dp套dp dp 根号分治矩阵数位dp

2020-04-25

0 408

省选模拟83 题解

A. table 首先考虑怎么暴力 dp，然后发现难点在于怎么知道不受影响的格点的个数。其实特殊之处在于碰到矩形边界之后没办法计数，所以考虑枚举在哪个位置碰到了矩形边界。然后发现每次转移是类似的，只要求 $a$ 次向下走，$b$ 次向右走，$c$ 次在边界上走能贡献的总的权值。其实等价...

组合计数树状数组 dp

2020-04-29

0 413

省选模拟85 题解

A. rng 有这样一个想法，我们把实数值域变成整数的。具体来说就是把给每个区间的 $r_i$ 都减去 $1$。这样的话期望就不难计算了：以值域作为下标，修改就是每次把 $[l_i,r_i]$ 区间加上一个 $\frac{1}{r_i-l_i+1}$。每次查询逆序对，其实就是求这个...

dp 莫比乌斯反演数学线段树

2020-05-01

0 409

省选模拟86 题解

A. 人生有一点 dp 套 dp 的意思，内层的 dp 就是直接在拓扑序上进行的简单 dp。外层记录的是 dp 的状态，然后 $O(n^3)$ 的做法是显然的。当转移到第 $i$ 个位置的时候，只要关心前面有多少个黑点 dp 值为 $1$，前面有多少个白点 dp 值为 $1$，前面的 d...

字符串状压后缀自动机 dp

2020-05-02

0 380