Good problem. 题意 题目链接 Monocarp 词典包含 $n$ 个单词,由 $12$ 个拉丁字母组成。单词编号从 $1$ 到 $n$ 。每个单词中的每一对相邻字符都是不同的。对于每个单词 $i$ ,Monocarp 也有一个整数 $c_i$ ,表示他使用这个单词的频率。 Monocarp 想要设计一个键盘,让他可以轻松地输入其中的一…
题意 题目链接。 给你一个由 $n$ 个整数组成的数组 $a$ 。 你需要在所有三元组 $(i,j,k)$ 中找出 $a_{i} | ( a_{j} \& a_ {k} )$ 的最大值,使得 $i < j < k$ . 这里 $\&$ 表示 位与运算,而 $|$ 表示 位与运算。 由 Codeforces Better!…
一些动态规划类型 树形 DP 树形 dp 的常用方法(例如树上背包)是将接下来要处理的儿子与以及处理完的儿子的全体进行合并,即把处理多个子树的问题转换为依次合并两个儿子的问题。 树形 dp 类型众多,故这里不多做赘述。 状压 DP 状压 dp 的核心是把状态用二进制数进行压缩(有些时候可能会用到四进制,如果一个点有三种或四种状态)。处理状压 dp …
题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包,每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个,我们需要这个答案序列先单调非降再单调非升,即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …
题目链接。 解析 后边的 dp 方式似乎和已有题解有一些差异。 首先考虑从第 $1$ 张纸片开始一张张放,计算出每张纸片有多少种放法,这分为三种情况: 最后局面该纸片占两格,显然只有 $1$ 种放法。 最后局面该纸片占一格,那么可能的放法有 $4$ 种,去除其中会覆盖最终局面的放法即可。 最后局面不存在该纸片,那么可能的放法为所有未被覆盖的位置的放…
题意 在左下角是 $(0,0)$,右上角是 $(W,H)$ 的网格上,有 $(W+1)\times (H+1)$ 个格点。 现在要在格点上找 $N$ 个不同的点,使得这些点在一条直线上。并且在这条直线上,相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。 解析 纯组合方法求方案数,是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 …
题意 题目链接。 给定 $n$ 行 01 串,其中有 $m$ 个区间为 $1$。删除若干 01 串使剩余串美丽,若干条 01 串美丽当且仅当任意相邻两个 01 串至少有相同的一位均为 $1$。 $n,m\le 3\times10^5$。 解析 考虑记 $f_i$ 为以第 $i$ 串结尾的最长美丽串的长度。发现 $f_i=f_j+1,j\in[1,…
题意 题目链接。 数轴上有若干传送门,初始是关闭或开启。对于关闭的传送门,经过后就会开启;对于开启的传送门,到达后会被传送到一个位置,然后会关闭。求从 $0$ 点走到 $x_n+1$,即最后一个传送门右边一格的所需时间。 解析 首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门,则记 $f_…
题意 题目链接。 给出一颗树,走到叶子节点后可以回到它的第 $k$ 祖先,求最多可以访问多少叶子节点。 解析 定义 $f_{i}$ 为从 $i$ 节点开始走,最后走回到 $i$ 节点的贡献,$g_i$ 为从 $i$ 节点开始走,最后不用回到 $i$ 节点的最大贡献。 先预处理出从每个点开始走可以回到的最高点,对于叶子节点,初始先将其贡献打到其第 $…
题意 题目链接。 $n\times m$ 的场地上存在一些箱子,碰到了就会被推动,不可以使任何箱子被推出场地。求从 $(1,1)$ 走到 $(n,m)$ 的方案数。 解析 发现该问题类似于过河卒,考虑 dp。由于向右和向下移动所涉及的箱子不同,且如果越过了箱子就一定不会再次推到(不能往回走),考虑如下设置状态: 记 $f_{i,j}$ 为从上方走到…