2023.8.11
不背图论板子要反省一下自己了。
A
[ABC206E] Divide Both
求
\(1\le L\le R\le 10^6\).
先容斥。假定 \(n\le m\).
如果 \(x=1\) 或 \(y=1\) 那么 \((x,y)\) 一定被统计了，要减去 \(\displaystyle\lfloor\frac{n}{d}\rfloor+\lfloor\frac{m}{d}\rfloor-1\).
前面一小块就是 \(nm\)，后面是 \(\displaystyle\sum_{p=1}^{n}\mu(p)\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor\).
时间复杂度 \(O(n)\).
当然不用莫反估计也能做。
B
一张无向图。
-
问割边后两点的连通性。
-
问割点后两点的连通性。
\(n\le 10^5\)，\(m\le 5\times10^5\)，\(q\le 3\times10^5\).
第一个问题，边双缩点，判断树上两点所在的边双是否同时或同时不在一个点的子树内。
第二个问题，点双缩点，判断树上两点所在的点双的简单路径上是否包含一个点。
具体我也不知道码量多少。
正解应该是圆方树。
C
P5786 [CQOI2008] 传感器网络
求 DAG 的一颗生成树，保证图上 \(in_n=0\)，试让所有非根节点的儿子数的最大值最小，并给出 \(0\sim n-1\) 的字典序最小的父亲序列。DAG 不连通输出 \(-1\).
\(n\le 50\).
不考虑字典序，先最小化儿子数的最大值，容易二分一个 \(k\)，建图直接跑最大流，\(maxflow=n\) 说明 \(k\) 合法。
再去想字典序的问题，假设已经确定 \(fa_{0\sim n-1}\)，枚举 \(fa_i\).
假设选择 \(fa_i\)，再建一遍图跑最大流，为 \(n\) 说明 \(fa_i\) 合法，继续枚举 \(i+1\).
要跑 \(n^2\) 次网络流，所以复杂度上界为 \(O(n^6)\)，常数小到爆炸。