联合省选 2020 补题记录

冰火战士

有两个二元组集合$(A,B)$。有$q$次操作形如：

• 在$A$中插入 / 删除一个二元组。
• 在$B$中插入 / 删除一个二元组。

每次操作后，你要输出

$$\max_{t} \min\left( \sum_{(x,y)\in A}[x\le t]y, \sum_{(x,y)\in B}[x\ge t]y \right)$$

$q \le 2\times 10^6, x\le 2\times 10^9, \sum y\le 2\times 10^9$.

树状数组 三分 二分

注：时限 3s。

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

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

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

时间复杂度$O(n\log_2n)$。

代码

组合数问题

给出$n, z, p, m, a_i$，求

$$\sum_{k=0}^n \binom{n}{k} f(k)z^k \bmod p$$

其中$f(x) = \sum_{i=0}^m a_ix^i$。

$n\le 10^9, m\le 1000, a_i\le 10^9, z\le 10^9$。

斯特林数 下降幂

推式子题。

$$\begin{aligned} & \sum_{k=0}^n \binom{n}{k} f(k)z^k \\ = & \sum_{j=0}^m a_j\sum_{k=0}^n \binom{n}{k} k^jz^k \\ = & \sum_{j=0}^m a_j \sum_{i=0}^jS(j,i) \sum_{k=0}^n \binom{n}{k} k^{\underline{i}} z^k \\ = & \sum_{j=0}^m a_j \sum_{i=0}^j S(j,i) \binom{n}{i} i! \sum_{k=0}^n \binom{n-i}{k-i} z^k \\ = & \sum_{j=0}^m a_j \sum_{i=0}^j S(j,i) n^{\underline{i}} z^i (z+1)^{n-i} \end{aligned}$$

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

$$\binom{a}{b} \binom{b}{c} = \binom{a}{c}\binom{a-c}{b-c}$$

代码

树

给出一棵带点权$a_i$的树，设$u$的子树是$T_u$，那么定义$u$的价值

$$val(u) = \bigoplus_{v\in T_u}\text{dist}(u,v)a_v$$

求$\sum_{i=1}^n val(i)$。

$n, a_i \le 5.5\times 10^5$。

Trie 启发式合并

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

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

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

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

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

算上启发式合并的复杂度，总复杂度$O(n\log n)$。

完整代码

信号传递

有一个长度为$n$的序列$s$，其中$1\le s_i \le m$。对于一个$m$的排列$p$，规定

$$f(i) = \begin{cases} p_{s_{i+1} } - p_{s_i} & p_{s_i} \le p_{s_{i+1} }\\ k(p_{s_{i+1} } + p_{s_i}) & p_{s_I} > p_{s_{i+1}} \end{cases}$$

求一个排列$p$使得最小化$\sum_{i=1}^{n-1} f(i)$。输出这个最小化的和即可。

$m\le 23, n\le 10^5, k\le 100$。

状圧 DP 卡空间

一看$m$很小，考虑状圧。那么对于$[m]$的一个子集$S$，假设这个子集分布在$p$的一个前缀$p[1,|S|]$，那么我们枚举$p_{|S|+1}$上的数，容易算出增量。这样就可以转移了。

但这题卡空间。

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

复杂度可以做到$O(2^mm)$。

作业题

给出一个$n$个点$m$条边带边权$w$的无向图$G$。对于其生成树$T$，记

$$val(T) = \gcd_{(u,v)\in T}w(u,v)\cdot \sum_{(u,v)\in T}w(u,v)$$

求$G$的所有生成树的权值和。

$n\le 30, w(u,v)\le 1.6\times 10^5$。

矩阵树定理 莫比乌斯反演

做这种题有两个要点：

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

首先看到$\gcd$，给它上一个$\varphi \ast 1=\text{ID}$：

$$val(T) = \sum_{d | w_1,d|w_2,\ldots, d|w_{n-1}}\varphi(d)\cdot \sum_{(u,v)\in T}w(u,v)$$

那么改一下枚举顺序得到

$$\sum_{d=1}^{W} \varphi(d) \sum_{T\in\text{span}(G(d))} \sum_{(u,v)\in T}w(u,v)$$

这里$G(d)$指$(V, E'=\{(u,v)\in E : d | w(u,v)\})$，也就是仅保留$d$的倍数的边。

当然，边权得整成一个$1+w(u,v)x$来做矩阵树。详情见 矩阵树定理学习笔记

你一看，复杂度$O(Wn^3)$，它说它是暴力。

它可不是暴力啊。把$E'=\varnothing$的情况去掉，考虑边数是$O(n^2)$的，看来是$O\left(\frac{\sum_{(u,v) \in E}\sigma_0(w(u,v))}{n-1}n^3\right) = O(n^4\max_{w\le W}\sigma_0(w))$啊。

不用劝了

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

正确性

考虑这样一个消元过程：枚举$i$：

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

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

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

代码

魔法商店

给出$n$个二元组$(c_i, v_i)$。

满足$\{c_e : e\in A\}$是线性基的$A$被称作礼品集合。定义礼物集合$A$的价值$W(A) = \sum_{e\in A}v_e$。

给出两个不同的礼物集合 ，要求将$v_i$变成$v_i'$使得对于任意礼物集合$C$都有$W(A)\le W(C)\le W(B)$。

最小化变换的代价：$\sum_{i=1}^n (v_i - v_i')^2$并输出。

$n\le 1000, m\le 64, v_i\le 10^6, 0\le c_i< 2^{64}$。

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

线性空间是拟阵，则根据强基交换定理，对于$A$，我们找到所有$x\in A, y\notin A$使得$A' = A-\{x\}+\{y\}$是礼物集合，那么只要保证$W(A)\le W(A')$即可。

$W(A)\le W(A')$等价于$v_x'\le v_y'$。

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

时间复杂度$O(n^2m\log_2n)$。其中 Dinic 复杂度$O(n^2m)$。

要写当前弧优化。

代码

消息传递

给出一棵$n$个点的树，$m$次询问$(x,k)$，求距离点$x$为$k$的点数。$T$组数据。

$n,m\le 10^5,T\le 5$。

点分治

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

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

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

时间复杂度$O(T(n+m)\log n)$。

代码

丁香之路

有一个$n$个点的完全图，其中$(u,v)$的长度是$|u-v|$。对其中的$m$条边打标记。给定起点$s$，对于每个结点$i$，求出从$s$走到$i$且每条被打标记的边至少被经过一次的最短距离。

边可以多次被经过。

$n\le 2500$。

欧拉回路 最小生成树

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

设$E' = E + \{(s,i)\}$，不难想到将奇度点两两配对连边，但这样构造出来的不一定是连通的欧拉图。

但注意到本题边长度特殊，我们可以把点按照$1,2,\ldots,n$的顺序排成一行。对于加入的边$(u,v)$，我们可以将其分解为$(u,u+1), (u+1,u+2),\ldots, (v-1,v)$。这与原边是等价的，并且可以连上沿途的点。

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

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

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

时间复杂度$O((n^2+m)\log n)$。

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

代码