牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共13篇）

省选模拟60 题解

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

树状数组期望 dp

2020-04-03

0 746

杂题

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

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

2020-04-07

0 457

省选模拟93 题解

A. A 肯定是用子序列自动机。然后暴力就是预处理出 DAG 上的路径数然后强行跑。优化的方法类似重链剖分，设 \(f_i\) 表示节点 \(i\) 之后的路径数。 \(f_i\) 等于每个转移边的加和。考虑求出每个节点的重转移。当 \(f_i<inf\)，重转移为每个转移中 \(f\) ...

倍增构造题矩阵期望线性代数

2020-05-11

0 399