冰火战士

有两个二元组集合。有次操作形如:

  • 中插入 / 删除一个二元组。
  • 中插入 / 删除一个二元组。

每次操作后,你要输出

.

树状数组 三分 二分

注:时限 3s。

首先把离散化。容易发现里的第一个函数是关于不降的,而第二个函数是关于不增的。那么可以把三分改成二分。

在线段树上二分,常数爆炸。

在树状数组上二分就赢了。当然,能使用树状数组的前提是函数里的运算可逆。

时间复杂度

代码

组合数问题

给出,求

其中

斯特林数 下降幂

推式子题。

推式子的过程中有用到一个小结论:

代码

给出一棵带点权的树,设的子树是,那么定义的价值

Trie 启发式合并

一道 zerobit 模板题。我们需要支持

  • 插入一个数。
  • 把所有数加
  • 合并两个集合。
  • 求异或和。

考虑从低位到高位建 Trie,即把数字的二进制表示反转,然后建 Trie。

把所有数加相当于左右儿子交换,即模拟二进制的进位过程。

void inc(int u){
  if(!u)return;
  swap(lc[u], rc[u]);
  inc(lc[u]);
  pushup(u);
}

算上启发式合并的复杂度,总复杂度

完整代码

信号传递

有一个长度为的序列,其中。对于一个的排列,规定

求一个排列使得最小化。输出这个最小化的和即可。

状圧 DP 卡空间

一看很小,考虑状圧。那么对于的一个子集,假设这个子集分布在的一个前缀,那么我们枚举上的数,容易算出增量。这样就可以转移了。

但这题卡空间。

一个比较 OK 的做法是用 STL 的 queue 把状态按照 pop count 来 BFS。可以看 dyls 的博客

复杂度可以做到

作业题

给出一个个点条边带边权的无向图。对于其生成树,记

的所有生成树的权值和。

矩阵树定理 莫比乌斯反演

做这种题有两个要点:

  1. 相应的知识点要掌握;
  2. 会算复杂度。

首先看到,给它上一个

那么改一下枚举顺序得到

这里,也就是仅保留的倍数的边。

当然,边权得整成一个来做矩阵树。详情见 矩阵树定理学习笔记

你一看,复杂度,它说它是暴力。

它可不是暴力啊。把的情况去掉,考虑边数是的,看来是啊。

不用劝了

另外,这题涉及到一个多项式求逆的问题。对于常数项为的多项式,它没有逆。如果在高斯消元的过程中这一列剩余元素里下方的元素找不到常数项非的多项式,我们可以把这些元素对应的多项式同时除以,然后继续求行列式。求出的行列式再乘上即可。

正确性

考虑这样一个消元过程:枚举

  • 找到下方第一个非零(有逆元)元素并将它所在行与第行交换(行列式反号)。
  • 下方的元素都消成
  • 右方的元素都消成

这样我们会得到一个对角矩阵。而如果在这个过程中出现找不到非零元素(常数项非零的多项式) 的情况,我们可以直接把第列所有元素都除以。因为上面的元素都是,除以后还是。因此在这个消元算法的情形下我们的做法是对的。

那么对于原本的高斯消元做法呢?原本的算法里,上面可能有常数项非的多项式,对它们除以是没有解的(因为一个多项式乘常数项必为)。但这影响吗?不影响!因为上面的元素既不会参与接下来的消元,也不会参与行列式的计算。换个角度想,你把右边元素消成的过程,也不会对第行下面的元素造成影响。因此从行列式计算的角度,这一步可以不做。

代码

魔法商店

给出个二元组

满足是线性基的被称作礼品集合。定义礼物集合的价值

给出两个不同的礼物集合 ,要求将变成使得对于任意礼物集合都有

最小化变换的代价:并输出。

保序回归 拟阵 网络流 最大权闭合子图 整体二分

线性空间是拟阵,则根据强基交换定理,对于,我们找到所有使得是礼物集合,那么只要保证即可。

等价于

因此我们对于分别建出偏序关系,然后跑一个保序回归即可。

时间复杂度。其中 Dinic 复杂度

要写当前弧优化。

代码

消息传递

给出一棵个点的树,次询问,求距离点的点数。组数据。

点分治

强制在线的话可以点分树。

但其实可以直接点分离线做。

对于当前的连通块的分治重心和这个连通块里的询问集合,以为根,求出表示到距离为的点数,再对于的所有儿子求出表示子树中的点到的距离为的点数,就可以统计关于每个询问的贡献了。

时间复杂度

代码

丁香之路

有一个个点的完全图,其中的长度是。对其中的条边打标记。给定起点,对于每个结点,求出从走到且每条被打标记的边至少被经过一次的最短距离。

边可以多次被经过。

欧拉回路 最小生成树

固定。问题可以转化为:给出无向图,其中表示被打标记的边。要求往里加,再加若干条长度和最小的边,使得有欧拉回路。允许有重边,即是可重集。

,不难想到将奇度点两两配对连边,但这样构造出来的不一定是连通的欧拉图。

但注意到本题边长度特殊,我们可以把点按照的顺序排成一行。对于加入的边,我们可以将其分解为。这与原边是等价的,并且可以连上沿途的点。

我们先不管奇度点匹配的方法,假设我们已经匹配完了奇度点并按照上面的方法分解连边,使得图中没有奇度点了。那么为了让剩下的块连通,我们找一个 MST 即可,这个 MST 的边会被走两次。这个用 MST 算法就行,MST 的连边同样要分解。

最后,考虑奇度点如何匹配的问题。由于 MST 的边会被走两次,因此对于四个奇度点,按照上面的连法,匹配,是比匹配更优的。所以我们直接把奇度点按标号排序,相邻的依次匹配即可。

要对每个求答案,稍微优化一下复杂度就行。

时间复杂度

非要用桶排或者并查集优化也不是不行,但没必要。

代码