比赛：ARC205 Div.2

· · 题解

ARC205 Div.2

A - 2x2 Erasing

若每次操作都选择左上角的进行反转，容易看出存在一种操作顺序，使得每次操作只会减少一个四宫格数量，因此只需二维前缀和，统计有多少个四宫格即可。

Code

B - Triangle Toggle

无论怎样操作，每个点的黑边度数 d 的奇偶性不会改变。

因此每个点最终黑边度数最大是 (n-1)-(n-1-d)\bmod 2，即，答案的上界为 \frac{1}{2}\left(\sum\limits_{i=1}^{n} (n-1)-(n-1-d_i)\bmod 2\right)。

如果一个点的白边度数 \ge 2，那么这个点一定可以进行一次操作，因此这个答案的上界是可以取到的。

Code

C - No Collision Moves

无解情况：

  1. 两个不同方向的线段相交。
  2. 有线段包含关系。

判完无解之后直接贪心操作即可。

Code

D - Non-Ancestor Matching

自底向上贪心。

维护子树内空置点数，以及匹配数。

按顺序合并子树的时候，

  1. 之前子树的空置点和当前子树空置点匹配。
  2. 之前空置点和当前已匹配的两个点匹配。
  3. 之前已匹配的两个点和当前空置点匹配。

容易证明这是最优的。因为最终树内要么只剩一个空置点，这时候已经达到答案上界了；要么剩下的空置点两两都存在祖先关系，并且除了最底下的空置点可能存在非祖先关系节点外，其他空置点都和树上所有点存在祖先关系。

Code

E - Subset Product Problem

考虑暴力，就是相当于做 n 遍高维前缀和，复杂度 O(nV)。

对于这个动态高维前缀和，发现我们加入一个数的复杂度为 O(V)，查询的复杂度为 O(1)，非常不平衡。

于是为了平衡复杂度，考虑根号分治。维护 f(x,y) 表示序列中所有值为 2^{10}x+k 的数的乘积，其中 k\subseteq y，即 k\operatorname{OR}y=y。

这样每次加入一个数复杂度为 O(\sqrt{V})，查询复杂度为 O\sqrt{V}。总复杂度 O(n\sqrt{V})。

Code