ZONe Energy Programming Contest 题解

[toc]

AC代码

A – UFO Invasion

B – Sign of Friendship

C – MAD TEAM

有 $N$ 个人，每个人有 $A,B,C,D,E$ 五个属性，选择 $3$ 个人组成一个团队去参加比赛，这个团队的五项属性定义为每项属性中三个人的最大值，团队的能力值是该团队五项属性中最低的那一项。询问这个团队可能的最大能力值是多少？

$N\leq 3000,\ A,B,C,D,E_i\leq 10^9$ 。

二分+状压。二分搜索答案 $x$ 是否可行，然后每个人的五项属性都只有 $\geq x$ 和 $<x$ 两种状态，我们用一个五位二进制数即可表示，判断一下是否存在三个状态或起来为31（二进制11111）即可。

D – Message from Aliens

给定一个加密字符串 $S$ ，你可以通过以下过程解密：

从 $S_0$ 到 $S_{N-1}$ 遍历字符串，如果不是字符 R 就加入字符串 $T$ ；

如果是字符 R 就翻转字符串 $T$ ；

得到的字符串 $T$ 中如果存在相邻的连续相同字符，就将这段连续相同字符去除，直到该串没有相邻的相同字符为止。

$|S|\leq 5\times 10^5$ 。

简单的模拟，第 $1,2$ 步可以用双向队列模拟，设置一个是否翻转的标识符记录状态即可。第 $3$ 步是经典的括号匹配问题，用栈模拟。

E – Sneaking

给定一个 $R\times C$ 的网格图，你要从 $(1,1)$ 走到 $(R,C)$ ，询问最少需要多少花费？一共有四种不同的移动：

从 $(r,c)$ 移至 $(r,c+1)$ ，花费为 $A_{r,c}$ ；

从 $(r,c)$ 移至 $(r,c-1)$ ，花费为 $A_{r,c-1}$ ；

从 $(r,c)$ 移至 $(r+1,c)$ ，花费为 $B_{r,c}$ ；

从 $(r,c)$ 移至 $(r-i,c)$ ，花费为 $1+i$ 。

所有移动都不能越过网格图的边界。

$R,C\leq 500; 0\leq A_{i,j},B_{i,j}\leq 1000$ 。

容易发现，如果没有操作 $4$ ，我们直接可以暴力建图跑dijkstra，边数的量级是 $O(RC)$ 的，因此我们只需考虑如何处理操作 $4$ 。

操作 $4$ 如果是 $i$ 而不是 $i+1$ 的话其实也可以直接建图，因为这个操作是在同一列上进行的，那么我们只需要在 $(r,c)$ 和 $(r+1,c)$ 之间建立一条权为 $1$ 的边即可，但是多了一个 $1$ 就会导致这个操作失效，因此我们考虑如何将这个 $1$ 加上：

对于每个点 $(r,c)$ 创建一个辅助点 $(r’,c’)$ ；
从 $(r,c)$ 到 $(r’,c’)$ 建一条权值为 $1$ 的边，$(r’,c’)$ 到 $(r,c)$ 建一条权值为 $0$ 的边；
从 $(r’,c’)$ 到 $((r-1)’,c’)$ 建一条权值为 $1$ 的边。

这个建图的本质就是让所有点在进行操作 $4$ 时都必须先登上它对应的辅助点，并且花费一点权值，这样我们就解决了操作 $4$ 里多余的 $1$ ，跑dijkstra即可。

F – Encounter and Farewell

有 $N$ 个点，标号从 $0$ 到 $N-1$，两个点 $a,b$ 之间可以建一条边当且仅当：$a\oplus b$ 不能在一个给定的数组 $A_M$ 中出现（$\oplus$ 表示异或）。

询问这个图上能否构造出一个生成树？可以的话给出一个构造方案。

$M<N\leq 2^{18}$ ，保证 $N$ 是 $2$ 的幂次。

先简化一下问题，转换成：给定一个 $N$ 个点的完全图，点 $a,b$ 之间边的边权是 $a\oplus b$ ，再给出一个集合 $A$ ，拆除所有边权 $\in A$ 的边，询问图是否连通（如果连通就必定可以构造生成树）？为方便起见，后文中 $N=2^n$ 。

这个问题我画了很久的图才想清楚，其实挺简单的。。。关键就是注意到：在这张图上，如果从点 $a$ 可以走到点 $b$ ，那么走过路径的异或和一定就是 $a\oplus b$ 。这是因为这条路径的异或和是 $(a\oplus c_i)\oplus (c_i\oplus c_{i+1})\oplus\cdots\oplus (c_j\oplus b)$ ，中间的节点全都会被约掉。因此，可以固定 $a=0$ ，这时如果可以从 $0$ 点走到其他所有点，这个图就是连通的。此时由于 $a$ 固定为零，如果所有 $b\in(1,2,\cdots,2^n-1)$ 都可以被集合 $B$ 中的元素线性表出（集合 $B$ 是全集 $(0,1,2,\cdots\,2^n-1)$ 与集合 $A$ 的差集），那这个图就是连通的。

这个问题直接用线性基就可以在 $O(N\log N)$ 的复杂度下解决了。

构造一种方案其实也就是这个思路，用并查集维护连通性，$i$ 从 $0$ 枚举到 $2^n-1$ ，如果 $i$ 还不能被线性表出，就将 $a\oplus b=i$ 且不连通的点对连边即可。