牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共13篇）

noi前第九场题解

A. s1mple 可以发现 0/1 这个限制类似于求路径数，使得路径经过的边权恰好合法。显然可以用容斥来求，这样可以将问题转化为钦定其中若干条边权为 \(1\)，其他边权任意的路径数。这样做有一个好处，原来问题中的 \(2^{n-1}\) 的集合可以缩减状态数。对于钦定之后的若干条 \(1...

dp 多项式后缀自动机拉格朗日插值启发式合并状压字符串

2020-07-21

0 379

noi前第十二场题解

A. string 对于这类字符串匹配题，有个套路是直接用 \(FFT\) 优化。然后发现这题字符集很小，所以枚举一个字符，将匹配串中的这个字符设为 \(1\)，模式串中的非这个字符设为 \(1\)。然后用一些技巧优化一下，就可以用 \(|\sum|+1\) 次长度为 \(n\) 的 \(DF...

平衡树多项式 trie树 dp 字符串

2020-07-25

0 553

noi前第十六场题解

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

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

2020-07-30

0 518