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。 考虑对于所有的连边方案，在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ，有多少方案是以其为 LCA 的，发现共有以下几种情况： $2-2$ 结构：在 $u$ 的两棵不…

题目链接。 解析 后边的 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$ 节点的最大贡献。 先预处理出从每个点开始走可以回到的最高点，对于叶子节点，初始先将其贡献打到其第 $…