我们考虑按照将所有的人分成若干个等价类，然后整组整组的考虑。 我们考虑使用生成函数来解决这个问题，设 \(x_i\) 是第 \(i\) 组的生成变量，\(f_i\) 是第 \(i\...
- 转载文章
- 2023-02-28
线段树分治。 我们发现这个形式就是线段树分治，那么我们就线段树分治。我们考虑如何在按秩合并并查集上维护二分图的关系。假设我们现在在同一个并查集中的 \(x\) 和 \(y\) 上连...
- 转载文章
- 2023-02-27
这道题的主流做法是主席树。 考虑离线怎么做，首先是莫队，但是很明显莫队很难往在线扩展。那么考虑线段树。 首先进行一些分析，我们可以对于每个 \(a\)，将第 \(i\) 个 \(a...
- 转载文章
- 2023-02-27
结构稳，01 分，枉划层，谁想锦衣自选人？不过贪婪座下臣。 \(\text{Treap}\) 我们的第一个想法是用衣服贡献人。把衣服按照 \(\{-p_i,c_i\}\) 为关键字...
- 转载文章
- 2023-02-27
题意：现在有无穷多个位置（从 \(1\) 开始），一开始都是 \(0\)，每次用 \(1/0\) 覆盖一个区间或翻转一个区间的 \(0/1\)。现在给出操作，求每次操作结束后第一个...
- 转载文章
- 2023-02-27
题意：每次插入/删除一个数，或询问当前所有数中异或上 \(p\) 之后小于 \(l\) 的有多少个。 看到动态最小化异或值的，我们首先想到 \(\text{Trie}\)，我们先建...
- 转载文章
- 2023-02-27
题意：对于一个序列，令一个 \(melody\) 为一个子序列满足子序列的相邻两项相差 \(1\) 或者模 \(7\) 同余。现在提取四个不重合的 \(melody\)，求最长总长...
- 转载文章
- 2023-02-27
题意：假设当前有 \(n\) 个点，求最多的边数，使得桥的数量 \(\ge\lceil\dfrac{m}{2}\rceil\)。 我们考虑构造，首先，整张图一共只有一个双连通分量。...
- 转载文章
- 2023-02-27
现在有 \(n\) 次操作，每次将一个点设为黑色，或者查询：从当前点到任意黑点路径上最小值的最小值。保证第一次操作是设置黑点。强制在线。 我们考虑这样一个过程，我们把第一次操作的点...
- 转载文章
- 2023-02-27
题意：压缩字符串，把字符串分成若干个子串，每个子串可以被压缩成“循环次数 \(+\) 循环节”的形式，求最小长度。 dp 求 lcp 先 \(O(n^2)\) dp 求出所有后缀对...
- 转载文章
- 2023-02-27
题意：求带边权无向图上 \(1\) 到 \(n\) 的异或最短路，可以重复经过某条边。 首先，我们考虑从 \(x\) 到 \(y\) 的路径 \(A\)，它的权值是 \(a\)。我...
- 转载文章
- 2023-02-27
题意：在 \((x,y)\) 放一个哨兵，可以监视本行后面的所有格子直到障碍、本列后面所有的格子直到障碍。求使全盘最多一个位置不被监视的方案总数。 我们发现，因为 \(nm\le ...
- 转载文章
- 2023-02-27
