牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共4篇）

模拟51 题解

A. Tree 可以发现，在开始时以1为根处理出dfs序。那么： 1.修改节点的子树不包含lca，那么直接使用该节点的子树区间。 2.修改节点的子树包含lca，那么只要扣掉lca在该节点的哪一个儿子的子树部分就可以了。对于换根lca：分类讨论即可正解是求出root与a，root...

ntt 生成函数 dp 线段树单调栈凸包

2019-09-27

0 360

字符串专题测试1 题解

A. 阿尔法显然只要对位合并，最后查询不同的集合数就好了。似乎听过一个叫倍增并查集的东西，然而考场上没有$yy$出来。 $f_{k,i}$表示点$i$以及$i$往后数$2^k$个元素共同被合并的祖先。对于合并操作，直接用ST表的思路合并即可。考虑最终的下传操作：枚举倍增的次幂数...

并查集斯特林数生成函数多项式倍增

2020-01-02

0 427

省选模拟24 题解

A. U.N.OWEN就是她吗？字典序最大，只需要贪心。考虑用网络流来做这个题。每次二分一个答案，然后对当前操作和之前进行的操作与每个元素直接建边，判断是否存在完美匹配。因为题中保证了一个特殊性质，考虑通过霍尔定理优化。点集 $X,Y$ 存在完美匹配，仅当 $\forall Z ...

线段树生成函数二分图多项式最短路

2020-02-14

0 412

noi前第十四场题解

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

dp 多项式生成函数线段树

2020-07-28

0 503