526互联

2023.12 杂题

发布时间 2023-12-11 11:28:57作者: cnyz

I found it hard, it's hard to find. Oh well whatever nevermind.

目录

CF1904E Tree Queries

Tag：T-欧拉序；S-线段树。

注意到 \(\sum k\) 和 \(n\) 同级，大抵是一个和 \(k\) 相关的做法，虚树大概是不可行的，所以考虑一些别的东西。

使用欧拉序描述整棵树，那么这个时候 \(x\) 所在的连通块可以划分成若干个欧拉序上面的区间，这个区间量级是 \(O(k)\) 的。

处理答案只需要离线询问后每次换根即可，这里的维护是容易的，Code，\(O(n\log n)\)。

CF1904F Beautiful Tree

Tag：G-优化建图；G-拓扑排序；A-倍增。

怎么感觉是简单题。

考虑 \(O(n^2)\) 怎么做，显然嗯建个图出来跑拓扑排序就秒杀了。

所以要做到 \(O(n\log n)\) 上我们的倍增优化建图就完事了哈哈，实在是有点难绷。

其实写起来有点像 ST 表优化建图？不管了反正就板子优化建图，Code。

ABC332G Not Too Many Balls

Tag：G-网络流；D-背包。

hot tea！显然有网络流建模：

  • 建立二分图，左侧 \(n\) 个点，右侧 \(m\) 个点，以及源点 \(S\) 汇点 \(T\)。

  • 令 \(i\) 为第 \(i\) 个左部点，连边 \((S,i,A_i)\)，令 \(j\) 为第 \(j\) 个右部点，连边 \((j,T,B_j)\)。

  • 连边 \((i,j,ij)\)。

直接求最大流肯定过不去，考虑有什么好的优化，直接在最大流角度有点 hard，考虑转最小割。

令左侧点集为 \(P\)，右侧点集为 \(Q\)，左侧和 \(S\) 连一起的点集为 \(X\)，右侧和 \(S\) 连一起的点集为 \(Y\)。

那么最小割即：

\[\min_{X\subseteq P}\min_{Y\subseteq Q} (\sum_{i\in P\setminus X} A_i+ \sum_{j\in Y}B_j+ \sum_{i\in X}i\sum_{j\in Q\setminus Y}j) \]

直接做仍然很难做，考虑枚举 \(\sum_{i\in X}i\)，则答案变为（令 \(L=\sum_{i\in X}i\)）：

\[\begin{aligned} \min_{L=0}^{N(N+1)/2}\min_{X\subseteq P,\sum_{i\in X}i=L}\min_{Y\subseteq Q} (\sum_{i\in P\setminus X} A_i+ \sum_{j\in Y}B_j+ L\sum_{j\in Q\setminus Y}j)=\\ \min_{L=0}^{N(N+1)/2} (\min_{X\subseteq P,\sum_{i\in X}i=L}\sum_{i\in P\setminus X} A_i+ \sum_{j\in Q}\min(B_j,jL)) \end{aligned} \]

这个时候前后就拆成了两部分，第一部分可以背包解决，第二部分可以求出每个 \(j\) 在何时切换，然后扫一遍完事，总时间复杂度 \(O(N^3+M)\)，Code。