Codeforces Round 1041 (Div. 1 + Div. 2)

比赛链接

A. Mix Mex Max

注意到序列所有数需要全相等，且这个数不能是 $0$。

B. Hamiiid, Haaamid... Hamid?

开局时，Mani 有两种选择：在 $x$ 左面或右面的格子放障碍。

接下来，Hamid 也有两种选择：只向左走和只向右走。

Hamid 确定方向后，Mani 每次都会在 Hamid 前进方向的下一个格子放障碍。

总共四种情况，全部计算一下即可。

C. Trip Shopping

注意到 $k$ 没有用，因为 Ali 每次选择的 $(i,j)$ 一定相同。现在问题变成了：选择一对 $(i,j)$，使得 Bahamin 操作后，得分最小。

我们不妨设 $a_i\le b_i$：如果 $a_i>b_i$，则交换它们。

我们将 $a_i,b_i,a_j,b_j$ 从小到大排序，排序结果是 $x_1\sim x_4$。Bahamin 操作后，以下方案是最优的：

• $(x_1,x_4)$，$(x_2,x_3)$ 配对；
• $(x_1,x_3)$，$(x_2,x_4)$ 配对.

容易发现，如果配对后形成的两端区间有交，则方案最优。所以，如果存在 $(i,j)$，使得 $[a_i,b_i]$，$[a_j,b_j]$ 有交，则选择 $(i,j)$ 即可。因为这么选后，答案不会变大。

接下来我们要处理所有区间都没有交的情况。不妨设 $a_i\le b_i< a_j\le b_j$，那么设原来序列的价值为 $v$，则修改后价值变成了 $v-2b_i+2a_j$。将所有区间按照 $a_i$ 从小到大排序后，我们发现，选择的两个区间一定是相邻的。枚举即可。

D. Root was Built by Love, Broken by Destiny

我赛时有个地方忘记取模，导致吃了 3 个罚时，调了 30 多分钟，望周不知。

首先这个二分图必须是树，因为二分图上的环一定会产生交点。

然后所有非叶子节点必须要形成一条链。我们称其为主链。

我们发现，主链是固定的，我们要在主链上插入剩下的叶子节点。假设主链上的某点 $i$，它连接了 $cnt_i$ 个叶子，则它会产生 $cnt_i!$ 种排列方式。将所有主链节点的排列方式乘起来即可。

然后我们发现：如果主链长度 $\ge 2$，那么改变主链的方向，就会产生新的情况。此时需要将答案乘以 $2$。

我们又发现：可以交换两岸的所有节点。需要再将答案乘以 $2$。

然后这道题就做完了。

E. Ancient Tree

遍历到节点 $i$ 时，我们计算出集合 $S$，集合中的数表示该颜色在 $\ge 2$ 棵子树内出现过。$S$ 可以用 dsu on tree 求。

如果 $a_i=0$，那么分几种情况：

• $|S|\ge 2$：无论 $a_i$ 怎么选，都会对答案产生 $w_i$ 的贡献。
• $|S|=1$：选 $S$ 中的这个颜色即可，不会对答案产生贡献。
• $|S|=0$：无论怎么选，都不会对答案产生贡献。

如果 $|S|=1$，选择 $S$ 中的这个颜色，一定是最优的。因为这个颜色一定在 $i$ 子树中出现过，不会对 $i$ 祖先的计算产生任何影响。

如果 $|S|\ge 2$ 或 $|S|=0$，那么选它父亲的颜色即可（如果 $i$ 是根则任意选）。容易发现，这样即不会影响到 $i$ 点是否产生贡献，也不会对 $i$ 祖先的计算产生影响。

如果 $a_i \neq 0$，那么更简单了。判断一下是否产生贡献即可。