训练

中考终于考完了！！！

前面的题慢慢施工ing……

ARC107F Sum of Abs

首先，我们现默认所有节点都被删了，可以用 \(A_i\) 的收益插入第 \(i\) 个节点。由于是求最大值，所以绝对值可以看作是限制有边的点同号。

我们考虑建图，对于第 \(i\) 个点，我们建两个点 \((i,-)\) 和 \((i,+)\) 表示取负或取正，每个点有点权，则 \((i,-)\) 和 \((i,+)\) 连边表示不能同时选。

对于一条边 \((u,v)\)，\((u,-)\) 和 \((v,+)\)、\((u,+)\) 和 \((v,-)\) 连边表示不能同时选。

于是跑二分图最大独立集即可。

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

对于球 \((a,b)\)，将点 \(p_a\) 和 \(q_b\) 连边，表示这个球需要被行或列碰撞。则要求连出来必须是基环树森林，否则无解。

因为点数为 \(2n\)，边数为 \(2n\)。若不全为基环树森林，则连通块中一定存在树，边数 \(<\) 点数，不可能存在完美匹配。

然后考虑对每棵基环树分开考虑，首先，树的部分边的方向是确定的，而环上只有两种情况。我们直接枚举，然后我们建出图，表示机器启动的先后关系（某台机器必须在某台机器后启动）。

注意到这个 DAG 一定是外向森林，所以拓扑序的方案数为 \(\frac{|S|!}{\prod_{i\in S} sz_i}\)。

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

首先，有个比较显然的结论，\(1,2,\cdots,n\) 都能被表示出来当且仅当，将 \(S\) 从小到大排序，\(\forall i\in [1,n], \sum_{j=1}^{i-1}S_j\ge S_i-1\)，可以通过归纳来证。