牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

省选模拟49 题解

A. Manager 问题是每个子树的中位数。每次的修改操作是改成最大值。所以只要考虑修改前的值是 $x$，如果 $x$ 大于一个祖先的中位数，那么对中位数无影响，否则将答案更新为中位数右移一位的数即可。然后发现只要预处理出两种答案。每次的操作就是询问一条祖先链，这个只要用一个数据...

线段树启发式合并莫比乌斯反演 dp

2020-03-18

0 354

省选模拟54 题解

A. space 首先考虑建个图，发现每个点的入度出度均为 $1$，其实就是形成了若干个环排列。起点为 $(1,1,1,1)$ ，但是最终还要经过一次起点。所以在 $n \neq 1$ 时，考虑直接无视这个起点，转化为自选起点，但是要花钱来，然后要求经过每个点一次的最小代价。发现代价显...

折半搜索莫比乌斯反演 dp

2020-03-25

0 314

省选模拟73 题解

A. 决战因为把暴力放过去了，所以这题就成水题了。其实正解的做法与那道求匹配方案权值和的题在链上的情况很类似。大概就是说整一个分治出来，然后 $dp_{l,r}$ 处存放一个多项式。其中 $l,r$ 分别表示左右两个端点的状态，$x^k$ 项系数表示放置了 $k$ 个人的方案数。 ...

莫比乌斯反演分数规划二分答案多项式数学网络流

2020-04-17

0 383

省选模拟75 题解

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

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

2020-04-20

0 403

省选模拟85 题解

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

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

2020-05-01

0 409