牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

省选模拟88 题解

A. 或许容易发现 $u,v$ 联通仅当 $u \oplus v$ 能被集合 $S$ 通过 $\oplus$ 运算表出。所以只需要维护线性基内元素个数。然后暴力的做法就是直接线段树分治。然后有一个能进行删除的离线操作是，不断尝试用被删除最晚的替换线性基中的元素。 B. 这就是 ...

线性基莫队根号分治 dp 状压

2020-05-05

0 381

省选模拟100 题解

A. 小B的棋盘这种方案不好枚举的题的一个解决方案就是考虑怎样的方案是可能合法的。如果 \(k \geq n\) 那么一定无解，否则可以找到至少一组点的中点来表示最终的答案。容易发现取 \(k+1\) 个点至少存在一个能匹配到的，所以复杂度可以做到 \(O(n^2 k)\)。如果判断一下每个...

最小生成树 lct dp

2020-05-19

0 409

省选模拟101 题解

石子游戏问题可以简单转化为最少能取出多少个数，使得异或和为 \(k\)。显然答案是小于 \(log(A_i)\) 的，因为线性基已经可以拼出所有数了。所以可以考虑枚举这个答案，然后就是 \(dp_{i,j}\) 表示用 \(i\) 个数能否拼出 \(j\)。转移可以用 \(FWT\) 优化，...

状压容斥 fwt dp 筛法

2020-05-20

0 367

数据结构乱写

loj6515 贪玩蓝月容易发现本题中要求的信息不支持快速合并，不支持快速删除，但是支持快速插入。所以一个简单的离线做法就是线段树分治。只要按照时间建线段树，把每个操作插入到对应节点上。最后 \(dfs\) 一遍线段树顺便插入，在叶子节点输出答案即可。然而这个信息是支持快速合并两个信息的。...

dp 单调队列分块启发式合并线段树 lct

2020-07-13

0 448

noi前第九场题解

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

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

2020-07-21

0 379

noi前第十场题解

A. 集合划分可以直接写出一个简单的 \(dp\)，然后发现这个 \(dp\) 的信息只需要存 \(A\) 集合选的个数和末尾选的哪个集合。不妨写成一个多项式，那么我们只关心边界的情况。所以写一个分治 \(FFT\) 即可。 B. ACT4！⽆限回转！考虑对于每条边，枚举所有能到达...

计算几何分治多项式 dp 辛普森积分

2020-07-22

0 405

noi前第十一场题解

##A. 数容易发现答案是 \(f_m=\sum \limits_{i=0}^n a_i[x^i](1-x)^m(1+x)^{n-m}\) 然后就有一个显然的 \(O(n^2)\) 做法，并不会优化。一个优化的方法是，考虑 \((1-x)\) 和 \((1+x)\) 相加为 $2$。所以可以将...

组合计数计算几何多项式 dp

2020-07-24

0 501

noi前第十二场题解

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

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

2020-07-25

0 553

noi前第十三场题解

A. 钩子可以发现大概问题是一层一层的。对于每一层，一定会选完所有长度为 \(2x,2x-1\) 的连续段之后递归下一段。可以考虑将这样的选择合并在一起考虑，然后做一个 \(dp\)。可以发现概率的大小大概只与剩下的奇数、偶数段的个数有关，所以记录奇数段的个数就可以转移了。然后的问题是怎...

ETT 分治 dp

2020-07-27

0 443

noi前第十四场题解

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

dp 多项式生成函数线段树

2020-07-28

0 503