CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== A. Prefix Flip =====

**题目大意**：给你两个 01 串 $a,b$，每次操作可以将 $a$ 的一个前缀 ''%%flip%%'' 并 ''%%reverse%%''。要求在 $2n$ 次内将 $a$ 变成 $b$。

**题解**：注意到该操作的逆操作为自己。于是我们可以将 $a,b$ 变为全 0/全 1。每次找到第一个 $a[i]\neq a[i+1]$ 的地方，对 $i$ 操作即可。

===== B. Unmerge =====

**题目大意**：给定一个长为 $2n$ 的排列，问它能否表示成两个长度为 $n$ 数组（不一定有序）的归并。

**题解**：一个基本观察是，对于一个 $p[i]$，所有它后面的连续一段比它小的数都要和 $p[i]$ 在一个数组中。这个条件是充要的，因为考虑每一段的开头，它们是单调增的，因而各段可以任意分配到两个数组中。这样的话，背包一下即可。

===== C. Mastermind =====

**题目大意**：给你一个长度为 $n$ 的数组 $a$，让你构造一个数组 $b$，要求 $a,b$ 相同的位置数为 $x$，相同的元素数量（即当成多重集的交）为 $y$。两者的取值范围都是 $[1,n+1]$。

**题解**：首先把 $x$ 用掉，优先选取数量最多的，其次把 $n-y$ 用掉，同样选取最多的，填入 $n+1$ 个数中不存在的那个。最后需要让剩下的数循环移位，''%%delta%%'' 是最多的那个数的大小。此时最多允许有一个位置重复，可以尝试和第二步中某个位置交换。

===== D. The Majestic Brown Tree Snake =====

**题目大意**：一棵树上有一条蛇，每次可以头移动一步（尾也跟着移动一步）或尾移动一步（头也跟着移动一步）。给你一条蛇，问能否通过移动使得蛇头尾对调。

**题解**：设蛇的长度为 $L$。先证明一点引理。

==== 引理 1 ====

若某点有两棵子树，它们分别是长度 $<L$ 的一条链，那么这两条链可以合并成一个较长的链。

**证明**：一旦任何时候蛇跨越了这两条链，它就死在这里了，永远出不去。因而，蛇不会跨越这两条链，所以可以等效于只有一条较长的链。

根据这一引理，所有深度 $<L$ 的子树都可以归纳地合并成一条链。

==== 引理 2 ====

若某点有两棵子树，一个是 $<L$ 的一条链，另一个的深度 $\ge L$。并且此时蛇与两个子树没有交。那么 $<L$ 的链可以删掉。

**证明**：类似地，即使蛇走进了长度 $<L$ 的链，它也干不了什么，不如往另一棵更深的树走。

基于上述两个引理，我们可以提出如下算法：

假设当前蛇在一条链上滑动，链上每个结点挂了一些子树。这些子树按照引理 1、2 简化。初始时这条链就是蛇本身。开始时，蛇只能走到左、右两个端点的子树中。如果蛇能走到链上某个结点，它的子树中存在分叉，那么显然两个分叉长度至少为 $L$，因而可以在这里掉头。若没有分叉，仅有一条链长度 $\ge L$，而滑动所在链对应一侧的长度也 $\ge L$，那么这和分叉是等效的。否则，容易发现这一块至多有一条长度 $\ge L$ 的链，因而其它部分都被吸收。可以发现最终总会合并完可走的子树，如果此时还没有成功，就不可能翻转。
CVBB ACM Team

用户工具

站点工具

页面工具
