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$…

题意 题目链接。 给定一个序列 $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$。 对于每一个背包容量 …

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

题目链接。 解析 首先第一个帖子肯定会由某一个账号发出。大力观察可以发现当第二个账号发帖之后，接下来一定可以至少两个账号交替发帖，即安全系数不再会有损失。我们仅需要解决第二个账号第一次发帖在哪一个位置即可。 假设我们确定了第二个账号第一次发帖的位置 $i$，那么剩下的 $k-2$ 个账号一定会在 $[i+1,n]$ 中选择 $k-2$ 的最大值进行…

题意 题目链接。 数轴上有 $n$ 个虫洞，有 $q$ 个按坐标升序给出的飞船，保证飞船一定在不会在第一个虫洞左边或最后一个虫洞右边。每个飞船每秒会等概率左移一格或右移一格，对于每个飞船，求到达任意一个虫洞的期望时间。 解析 记 $f_i$ 为位置在 $i$ 的飞船的期望时间，只要 $i$ 位置没有虫洞（有虫洞期望时间显然为 $0$），就有 $f_…

题意 题目链接。 有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，每次操作选择 $k$ 个数，将这 $k$ 个数减去他们的与（二进制运算中的与）的和。求哪些 $k$ 可以在有限次操作内使所有数变成 $0$。 解析 蛮有趣的。把所有数化成二进制后，你考虑每一位。如果共有 $x$ 个数在某一位上为 $1$，那么考虑如果指定了一个 …