牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共73篇）

noi前第十四场题解

A. ⼩W数排列做过类似的题，思路大概将所有数从大到小插入。这样相邻两个位置的贡献就转化为一加一减。可是这样做会导致值域变得很大，其实这样没用到题中 \(l\) 很小的限制。考虑这样一个做法，把每次一加一减的贡献差分掉。每次基准线降低的时候直接统计降低的高度*降低的个数的贡献。因...

dp 多项式生成函数线段树

2020-07-28

0 503

noi前第十六场题解

##A. 小B的班级莫名想到了一个结论，这种题可以找到选中的点形成的重心。然后求所有点与重心距离的和即可。原因是，任意一个子树大小均小于 \(m\)，所以总可以构造出方案。在这道题中，只要枚举最接近 $1$ 号点的可能的重心，然后计算方案数就可以 \(O(n^3)\)。仔细想一下，可以把...

线段树分治单调栈 KMP 字符串

2020-07-30

0 518

<span>noi前第十九场题解</span>

##A. 欢迎来到塞莱斯特山容易想到对每个联通段进行 \(dp\)。这样在归并子树的过程中只需要枚举两者分别的段数，枚举合并成多少段。转移系数只要做一个 \(O(n^3)\) 的 \(dp\) 就可以预处理出来。复杂度大概就是子树归并的复杂度 * \(n\)，写个指针卡卡内存就能过了。 &n...

线段树分治多项式 dp

2020-08-03

0 493