很涩的一个题。 题意 题目链接 假如我们有一个 AC 自动机，我们可以取出其中的点，字符边和 Fail 边，这样其就变成了一个有 $n$ 个点和 $2n-2$ 条边的有向图。现在给出你这样一个有向图，你需要找到其原始的 AC 自动机结构（包括 1. 找到根 2. 找到哪些边是 Trie 树边 3. 给所有的 Trie 树边分配一个字符，字符集大小不…

题意 题目链接。 给你一个序列 $a$，让你输出一个序列 $b$ ，这个 $b$ 满足跟 $a$ 有 $x$ 个位置上的元素一样。有 $y$ 个元素跟 $a$ 里边的元素一样。值域是 $1\le v \le n+1$。 解析 先考虑这么一件事情：假如你已经确定了这 $x$ 个位置是什么，那么问题转化为：你需要将若干个元素交换位置，使得与原来元素相同…

题意 题目链接。 给定一张有向无自环图，求一个点集满足： 点集内任意两个不同点距离不小于 $2$（即无边相连）。 对于任意一个不在点集内的点，存在一个点集内的点到它的距离不大于 $2$（即两步能达）。 解析 算法实现与 @Mickey_snow、@_Anchor 等题解类似，本篇题解主要重申一种可能更清晰的证明以及错解的 Hack。 简单阐述解法：…

解析 题目链接 题意很清晰了。 我们考虑凳子的折扣情况。由于凳子本身也是一个物品，那么如果存在一个比凳子贵的物品在购物车中，那么打折的是凳子，如果有一个比凳子便宜的物品在购物车中——那还不如给凳子打折呢！合着这个商场就是给凳子打折而已。 因此，由于凳子的打折情况最优就是给自己打折，那么我们将凳子按照价格排序，对于前 $k-1$ 辆购物车，每辆购物车…

题意 题目链接 大体见翻译。注意树被"拍扁"到平面中之后，要求所有边都与坐标轴平行，且所有点是整点。 解析 首先有一件很显然的事情，就是如果有任意一个点的度数大于 $4$，结果一定为 $-1$，因为由于边的方向只有上下左右四种，所有第五条边是无论如何也无法连出去的。 接着考虑对于可行的情况，我们只需要满足没有任何两条边相交就可以了。那么我们考虑什么…

这道题乍看不难，但是构造过程中发现非常毒瘤，因为有一种情况极难构造。 题意 题目链接 构造一张完全有向图（即任意两点之间都有一条单向边），使任意两有序点之间的距离不大于 $2$。题意应该还算是比较容易理解的。 解析 $n$ 为奇数 题目已知 $n \ge 3$ 且 $n=4$ 时不可行。我们首先考虑 $n$ 是奇数的情况，我认为这种情况还是比较好想…