题目链接。 解析 后边的 dp 方式似乎和已有题解有一些差异。 首先考虑从第 $1$ 张纸片开始一张张放，计算出每张纸片有多少种放法，这分为三种情况： 最后局面该纸片占两格，显然只有 $1$ 种放法。 最后局面该纸片占一格，那么可能的放法有 $4$ 种，去除其中会覆盖最终局面的放法即可。 最后局面不存在该纸片，那么可能的放法为所有未被覆盖的位置的放…

题意 题目链接。 给你一个序列 $a$，让你输出一个序列 $b$ ，这个 $b$ 满足跟 $a$ 有 $x$ 个位置上的元素一样。有 $y$ 个元素跟 $a$ 里边的元素一样。值域是 $1\le v \le n+1$。 解析 先考虑这么一件事情：假如你已经确定了这 $x$ 个位置是什么，那么问题转化为：你需要将若干个元素交换位置，使得与原来元素相同…

题意 在左下角是 $(0,0)$，右上角是 $(W,H)$ 的网格上，有 $(W+1)\times (H+1)$ 个格点。 现在要在格点上找 $N$ 个不同的点，使得这些点在一条直线上。并且在这条直线上，相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。 解析 纯组合方法求方案数，是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 …

题意 题目链接。 给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$，请输出距离最近的两个点的距离。 解析 在这题下给一篇正经的分治做法，已有的分治做法是用 vector 实现的，可能对于部分同学来说代码实现不便。其他题解都是非分治的。 我们将所有点按照 $x$ 坐标排序后标号为 $1,2,\dots n$，记 $…

题意 题目链接。 洛谷这题的评测似乎炸掉了，这里有 Znloye 提供的临时测试点。 求 $a^{a^{a^{\dots}}}(b\ 个\ a)$ 的末 $9$ 位数，$t$ 组数据。 解析 保留末 $9$ 位数等价于对于 $10^9$ 取模，再补全前边的 $0$ 即可。 而对于这种 Power Tower，一种常用的方法是使用扩展欧拉定理，再在快…

题目链接。 发现题解区说大多都是直接说再连一条边权为 $-1$ 的边，在这里略微证明一下正确性。​ 解析 首先发现若图中没有环，最大答案为所有联通块的最长链长度之和，最小答案为 $3$。 若存在环，则最大答案为所有环的 $\gcd$​​。为了在可接受的时间内找到所有环，我们对于每一条边的 $u\rightarrow v$​​，从 $u$​​ 向 $…

题意 题目链接。 给定 $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,…

题意 题目链接。 给定一个长度为 $n$ 的环，有 $k$ 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。 解析 先考虑如果是链的话就是一个朴素的贪心：每次在所有左端点不大于当前位置的点中选取一个右端点最大的跳过去。对于环，容易想到将其断开，在其后面复制一份即可。 问题转化为了一个长度为 $2n$ 的链，求最少数量的区域使其能够覆盖长度至少为 …

题目链接。 解析 考虑最终序列。由于序列较长，先考虑序列短小的情况，即长度为 $3$ 时。 对于一个长度为 $3$ 的序列 $S_{1,2,3}$，要使其不存在回文串，需要满足 $S_1\neq S_2,S_2\neq S_3,S_1\neq S_3$，你发现这三个字母必须是互不相同的，由于字符串仅由三种字母组成，最终序列的前三个字母一定是以下六种…

题意 题目链接。 数轴上有若干传送门，初始是关闭或开启。对于关闭的传送门，经过后就会开启；对于开启的传送门，到达后会被传送到一个位置，然后会关闭。求从 $0$ 点走到 $x_n+1$，即最后一个传送门右边一格的所需时间。 解析 首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门，则记 $f_…