标签: 构造

6 篇文章

ICPC Online 2024 K AC Automation Chicken 题解
很涩的一个题。 题意 题目链接 假如我们有一个 AC 自动机,我们可以取出其中的点,字符边和 Fail 边,这样其就变成了一个有 $n$ 个点和 $2n-2$ 条边的有向图。现在给出你这样一个有向图,你需要找到其原始的 AC 自动机结构(包括 1. 找到根 2. 找到哪些边是 Trie 树边 3. 给所有的 Trie 树边分配一个字符,字符集大小不…
CF1381C Mastermind 题解
题意 题目链接。 给你一个序列 $a$,让你输出一个序列 $b$ ,这个 $b$ 满足跟 $a$ 有 $x$ 个位置上的元素一样。有 $y$ 个元素跟 $a$ 里边的元素一样。值域是 $1\le v \le n+1$。 解析 先考虑这么一件事情:假如你已经确定了这 $x$ 个位置是什么,那么问题转化为:你需要将若干个元素交换位置,使得与原来元素相同…
CF1019C Sergey’s problem 题解
题意 题目链接。 给定一张有向无自环图,求一个点集满足: 点集内任意两个不同点距离不小于 $2$(即无边相连)。 对于任意一个不在点集内的点,存在一个点集内的点到它的距离不大于 $2$(即两步能达)。 解析 算法实现与 @Mickey_snow、@_Anchor 等题解类似,本篇题解主要重申一种可能更清晰的证明以及错解的 Hack。 简单阐述解法:…
CF161B Discounts 题解
解析 题目链接 题意很清晰了。 我们考虑凳子的折扣情况。由于凳子本身也是一个物品,那么如果存在一个比凳子贵的物品在购物车中,那么打折的是凳子,如果有一个比凳子便宜的物品在购物车中——那还不如给凳子打折呢!合着这个商场就是给凳子打折而已。 因此,由于凳子的打折情况最优就是给自己打折,那么我们将凳子按照价格排序,对于前 $k-1$ 辆购物车,每辆购物车…
CF761E Dasha and Puzzle 题解
题意 题目链接 大体见翻译。注意树被"拍扁"到平面中之后,要求所有边都与坐标轴平行,且所有点是整点。 解析 首先有一件很显然的事情,就是如果有任意一个点的度数大于 $4$,结果一定为 $-1$,因为由于边的方向只有上下左右四种,所有第五条边是无论如何也无法连出去的。 接着考虑对于可行的情况,我们只需要满足没有任何两条边相交就可以了。那么我们考虑什么…
CF323B Tournament-graph 题解
这道题乍看不难,但是构造过程中发现非常毒瘤,因为有一种情况极难构造。 题意 题目链接 构造一张完全有向图(即任意两点之间都有一条单向边),使任意两有序点之间的距离不大于 $2$。题意应该还算是比较容易理解的。 解析 $n$ 为奇数 题目已知 $n \ge 3$ 且 $n=4$ 时不可行。我们首先考虑 $n$ 是奇数的情况,我认为这种情况还是比较好想…