Good problem. 题意 题目链接 Monocarp 词典包含 $n$ 个单词，由 $12$ 个拉丁字母组成。单词编号从 $1$ 到 $n$ 。每个单词中的每一对相邻字符都是不同的。对于每个单词 $i$ ，Monocarp 也有一个整数 $c_i$ ，表示他使用这个单词的频率。 Monocarp 想要设计一个键盘，让他可以轻松地输入其中的一…

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

题意 题目链接。 给你一个由 $n$ 个整数组成的数组 $a$ 。 你需要在所有三元组 $(i,j,k)$ 中找出 $a_{i} | ( a_{j} \& a_ {k} )$ 的最大值，使得 $i < j < k$ . 这里 $\&$ 表示 位与运算，而 $|$ 表示 位与运算。 由 Codeforces Better!…

题意 题目链接。 交互题。 狐狸给你两个正整数 $n,k$，并且她有一个长度为 $n$ 的隐藏数组。对于一段区间 $(l,r)$，其价值 $f(l,r)$ 等于长度乘以区间最大值。 你有 $2n$ 次查询次数，每次查询形如 ? l x，狐狸会告诉你一个数 $r$，表示最小的满足 $f(l,r)=x$ 的 $r$，或是 $n+1$ 表示不存在 $r$…

题意 题目链接。 使用 coze.com 的 gpt-4 进行翻译和格式美化. 给定一个包含$N$个顶点的树$T$，设$F$是$T$的顶点的一个子集，如果$F$满足以下条件，则称$F$为$x$根火花： $F$包含顶点$x$ - $F$是$T$的连通子图——也就是说，由$F$导出的子图$T[F]$是连通的。 令$d_F(u)$表示节点$u$在$T[F…

题意 题目链接。 使用 coze.com 的 gpt-4 进行翻译和格式美化. 一个长度为$M$的数组$A$被称为前缀平衡，如果它满足以下条件： 让$S_A$表示在$A$中出现的所有元素的集合。 对于每个$x \in S_A$，和索引$i(1 \leq i \leq M)$，让$f_i(x)$表示$x$在$[A_1, A_2, \dots, A_i…

题意 题目链接。 给定一个序列 $y$​, 初始有一个全零序列 $x$​。每次可以选择一个长度为 $k$​ 的前缀或者一个长度为 $k$​ 的后缀将其加一，代价是 $k$​。问最少需要多少代价能使得对于所有 $i$​ 都满足 $b_i\geq a_i$​。 序列的长度范围为 $1 \le n \le 10^6$。 解答 Key 1: 考虑什么情况下…

题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包，每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个，我们需要这个答案序列先单调非降再单调非升，即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …

题意 题目链接。 给你一棵树，你可以在树上连两条边，这两条边会分别形成两个环，要求这两个环没有任何相同的边或结点，求连边的方案数。 解析 蛮有趣的一个树形 dp。 考虑对于所有的连边方案，在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ，有多少方案是以其为 LCA 的，发现共有以下几种情况： $2-2$ 结构：在 $u$ 的两棵不…

这是第一场所有赛题都由我命制的公开比赛，也是第二场我参与命题的公开比赛。 比赛时由于内测下来大家都觉得 D 比 E 难，就更换了 DE 的顺序，本篇题解中没有发生更换，望读者注意。 比赛链接：Link. A. 伊甸之花 题目链接：Link. 若乐曲中同时存在 $1$ 和 $m$ 则无解，否则一定可以通过整体上移/下移一个音调来满足条件，时间复杂度 …