题意 题目链接。 一共有 $n$ 个格子，给定两个整数 $A,B$ 分别位于第 $1$ 和第 $n$ 格，中间有 $n-2$ 个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在 $[C,D]$ 之间。 解析 考虑这 $n$ 个数之间有 $n-1$ 对差，因此题目等价于： 是否存在 $A+\sum\limits^{n-1}_{i=1} …

一段时间没打字符串相关的题了，找道简单的 Trie 练练手。 题意 题目链接。 维护一个复古打印机，支持添加字母，删除字母，打印字母。求用最小步骤打印出所需的所有单词。 解析 首先容易想到建 Trie，然后在 Trie 上进行 dfs，每次走到一个结点就添加这个结点对应的字母，若走到了一个单词的结尾就打印，然后在每层 dfs 返回之前删除当前字母。…

题意 题目链接。 有一张 $n\times\ n$ 的网格，有 $1,2,3$ 三种颜色，每轮交互库会给出一种颜色，你需要在剩余两种颜色中选一种颜色涂在一个格子上，不可以使任何两个相邻格子颜色相同。你需要扮演涂色者将所有格子涂上颜色。 解析 首先我们考虑到，如果有一个空格子，其上下左右四个格子中有两种颜色，你就输了（因为交互库可以一直给出剩余的这种…

题意 题目链接 给出一个正方形区域，其中有一些点是障碍。每次询问给出两个球的初始位置，询问至少需要改变几次重力才能使两球相遇。 解析 首先我们发现，实际上仅有障碍周围（包括地图边界）上的点是有意义的（因为任何位置的球经过一次操作一定会到这些点，显然一次操作是可以枚举的）。我们定义每一组有意义的 $(x,y)$ 为一个状态，显然最多状态数为 $200…

题意 题目链接 给定 $n$ 个点，求一个由若干个点连接成的凸多边形，所包含的点数最多，输出点数。 解析 先说解法：将所有边按照 atan2(y,x) 的值排序， 然后枚举凸多边形起点，再遍历排序后的边进行 dp 转移，复杂度为 $O(n^3)$。 大致思路与已有题解相同，但是我在这里想要阐述一个困惑我许久的点：为什么是 atan2 ？ 搜索百度百…

非常有意思的一道题（虽然确实容易想不出来）。 题意 题目链接 维护一个 $0 \sim 2^n-1$ 的序列，支持两个操作：将下标为偶数的数按序提前，将下标为奇数的数按序后置；将下标为偶数的数按序后置，将下标为奇数的数按序提前。 解析 我们考虑两种操作的实质。 第一种操作（偶前奇后）：对于下标为 $x$ 的数，若 $x$ 为偶数，则它的新下标为 $…

题意 题目链接 树上的棋子博弈，每个点有权值。你可以添加一条边以试图反败为胜，不同的加边方法根据权值有一个代价，需要最小化这个代价。 解析 我们首先定义一个结点先手必败是 lose，先手必胜是 win，容易发现，叶子结点一定是 ​lose，然后对于每一个非叶子结点，只要它有一个儿子是 ​lose，它就是 win，否则，该结点也是 lose。一遍 d…

题目链接 解析 题意就不多阐述了，看原题就够了。个人觉得这是一道练归并排序性质的好题（虽然动规/堆维护等方法似乎也可行，但我认为最朴素的方法才是最美丽的）。 再发觉贪心不可行时，我们考虑分治维护每一轮比赛可能获胜的人。假设我们以及维护好了左区间（即上一轮比赛）哪些人可能能在上一轮获得胜利（也就是能活到当前这轮）以及右区间的这个信息，我们考虑如何合并…

题目链接 题意 给定一个二分图，二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$，则这两点之间有一条边。求二分图最大匹配。 解析 首先我们发现，如果暴力建边的话，我们可能会建 $n^2$ 条边，在 $100$ 组数据的情况下，非常容易 TLE。 我们考虑优化。对于一个左部点的权值和一个右部点的权值的…

题目链接 题意 星球的一天有 $h$ 小时，每小时有 $m$ 分钟。现在给定一个当前时间，询问最近的在镜中对称之后合法的时间。 解析 主要是注意一些细节。首先判断最近的对称过去合法的小时，如果给出的时间的小时本身对称过去就是合法的，那么分钟就要从给出的分钟开始找，一直找到第一个合法的。否则，如果小时与给定的不一致，分钟就一定为 $0$，即输出一定为…