Keyence Programming Contest 2020 题解

AutumnKite

题解AtCoder

发布于：2020年9月10日

次浏览

比赛地址

来不及了，ABC 不写了。

D - Swap and Flip

题意

有 \(n\) 张卡片从 \(1\) 到 \(n\) 排列，第 \(i\) 张正面写着 \(A_i\)，反面写着 \(B_i\)，一开始都正面朝上。

你每次操作可以交换相邻两张卡片的位置并将这两张卡片翻面。

求使得朝上那面的数字不降的最小操作次数，或输出无解。

\(n\le 18\)

题解

假设最终序列中第 \(i\) 张卡片是原来的第 \(p_i\) 张卡片，那么如果 \(i\) 与 \(p_i\) 奇偶性相同，则朝上的是 \(A_{p_i}\)，否则是 \(B_{p_i}\)。另外，由于每次交换相邻的两张卡片，所以最小交换次数就是 \(p_i\) 的逆序对数量。

于是我们可以考虑枚举奇数位置的卡片集合，然后我们就可以确定奇数位置和偶数位置的朝上的数的可重集合。由于我们最终求的是逆序对数量，所以如果两个数相等那一定是位置靠前的仍然靠前。所以我们可以确定一个 \(p_i\)。直接求逆序对即可。

时间复杂度 \(O(2^nn^2)\)。

代码

E - Bichromization

题意

给定一个 \(n\) 个点 \(m\) 条边的无向连通图，每个点还有一个额外的值 \(D_i\)。

你需要对每个点黑白染色，给每条边赋一个 \(1\) 到 \(10^9\) 的整数权值，使得：

• 至少有一个点是黑色，至少有一个点是白色。
• 对于每个点 \(u\)，满足与它最近的异色点 \(v\) 到 \(u\) 的最短路为 \(D_u\)。

\(n\le 10^5,m\le 2\times 10^5,D_i\le 10^9\)。

题解

首先如果存在一个点 \(u\) 满足 \(\forall (u,v)\in E,D_v>D_u\)，此时 \(v\) 如果与 \(u\) 异色，则 \((u,v)\) 的权值一定不小于 \(D_v\)；如果 \(v\) 与 \(u\) 同色，则 \(D_v\) 也无法更新 \(D_u\)。所以此时 \(D_u\) 不会被任何一个 \(v\) 更新到，一定无解。

接下来我们考虑按照 \(D_u\) 从小到大依次染色。

如果 \(u\) 相连的点中已经存在被染色的点，那么我们任取其中一个 \(v\)，将 \(u\) 染成与 \(v\) 异色的点，将 \((u,v)\) 的边权置为 \(D_u\)，此时 \(u\) 一定会被 \(v\) 更新到，而 \(v\) 因为 \(D_v \le D_u\)，不会被更新到。

如果不存在，则此时一定存在至少一个 \(v\) 满足 \(D_v=D_u\)，任取其中一个，将 \(u,v\) 染不同颜色，将 \((u,v)\) 的边权置为 \(D_u\)，此时 \(u,v\) 能互相被更新到。

可以发现，上述染色过程中，每次都可以保证当前被染色的点 \(u\) 满足 \(D_u\) 的限制。

剩下没有被赋权值的边全部赋成 \(10^9\) 即可。

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

代码

F - Monochromization

题意

有一个 \(H\times W\) 的黑白矩阵 \(A\)，求有多少个 \(H\times W\) 的黑白矩阵可以通过 \(A\) 按任意顺序执行任意次以下几种操作得到：

• 选择一行，全部染成黑色或白色；
• 选择一列，全部染成黑色或白色。

对 \(998244353\) 取模。

\(H,W\le 10\)

题解

首先我们考虑 \(A\) 全白的情况。

对于一个矩阵，定义可移除行为颜色全相同的行，可移除列为颜色全相同的列。那么一个矩阵能得到当且仅当重复执行若干轮以下操作后变为空矩阵：

• 将所有可移除行删除（剩下的行重新按顺序排列形成一个新的矩阵）；
• 将所有可移除列删除（剩下的列重新按顺序排列形成一个新的矩阵）。

可以发现由于这两个操作交替地、重复地执行，且每次把能删除的都删除，一个矩阵对应的操作序列一定是唯一的。

这样我们避免了算重，只需要统计合法操作序列数量即可。

我们发现，需要关注的不仅仅是当前矩阵的行数和列数，上次删除的是行还是列，我们还需要关注上一次删除的行或列的颜色是否全部相等。

假设上一次删的全部是列，现在需要删除行。如果上次删的列颜色不全相等，那么再上一次删行时一定已经把能删的都删完了。

如果上次删的列颜色全部是黑色，那么如果有全黑色的行，那么我们把之前删的黑色的列重新加回去时，这一行仍然是全黑色的，我们可以在上一次删行时把这一行删掉。所以这一次删行时删的行一定都是白色，这样才能保证之前把能删的都删完了。

于是 \(f_{i,j,k}\) 表示上一次删的是行，当前矩阵大小为 \(i\times j\)，上一次删的行有 \(k\) 种不同的颜色（\(k\in \{1,2\}\)）。\(g_{i,j,k}\) 类似，表示上一次删的是列。

转移比较简单，具体可以参考代码。要注意设置初始值是，应该把删除的行是同种颜色的方案也计入 \(f_{i,m,2}\)，这是因为第一次删除列时没有再上一次的删除列操作，仍然可以删除不同颜色的列。

接下来回到原问题。此时一个矩阵能得到的条件是通过上述移除操作，直到无法移除后，每个位置的颜色与 \(A\) 中对应位置（即没有进行移除操作前的位置）的颜色相同。

若最后的矩阵为空，与之前的问题相同，需要特殊处理。

否则，我们枚举最后保留的行和列，合法的条件是保留的行和列组成的矩阵不存在可移除行和可移除列。然后把方案数直接加上即可。注意此时由于固定了行和列，需要除以两个组合数。

时间复杂度 \(O(2^{H+W}(H+W))\)。

代码

更新于：2021年5月29日

贪心

枚举

构造

DP

组合数学