还是比较有意思的题目。 有一个十分简单的做法，就是考虑直接比较相邻两个数（ 比较， 比较，以此类推）。此时单次需要 次操作，一共需要 次即可确定最大的元素。 这样的总次数是 次，需要询问 轮。我们似乎并不满意。 我们发现，题目限制给了更多的询问次数（ 次），但我们只用掉了其中的 次，浪费了很多次数。 我们可以考虑扩展一下我们的策略。我们考虑不两个两个的比，而是 个 个的比。具体的，假

首先由于都是平视，因此我们将这个东西分层考虑，每层分别考虑能看到几个。 由于最多有 个格子，因此这个只会变化 次。 将这个东西转一下，使得光线永远是从右上方照射过来，并且 坐标不为 。 考察什么时候会照到一个光线。实际上我们只关心垂直光线方向的投影。因此我们考虑将一个方块转化成经过右上方顶点的一条直线。 因此，我们就把这个问题转化成了一个线段覆盖问题，每次询问能看到几种颜色不同的线段。 不妨

别问为什么现在才来写题解。 题目需要求分解 成若干个不同的斐波那契数列中的数有多少种方案。 由于每个位置最多一次，因此我们可以考虑用一个 字符串来表示。 这个 字符串有两个性质。如果 （换句话说，有连续的 110），那么将其替换成 也是合法的（即，替换为 001）。同理，你也可以考虑拆解。 不妨考虑拆解的情况。你发现，一旦你把 001 拆成 110，那么，第二个 就再也不能继续往下拆了。

题解区什么鬼。 只讲转移不说意义吗。这个真的很显然吗。 不妨考虑先钦定操作序列（敲字符还是退格），再钦定具体敲了哪个键。 首先，考虑这一个点，如果一个字符最终被删掉了，那么这个字符是 是 其实无所谓。如果一个字符最终被保留了下来，那么这个字符就必须是对应位置上的字符。 换句话说，假设敲了 个没有被退掉的字符， 个被退格键退掉了，那么总共的敲键方案数就是 。原因每个是 个被退掉的字符都有

不知道算不算题解。 大概是一些零散的想法。 首先一个观察就是，用栈从左侧往右扫描。然后你发现栈内元素一样说明这两个点的区间就是可以消除的。 因此你可以对栈哈希。哈希可以直接考虑数组哈希的做法，对于第 位乘上一个大质数的 次幂在加起来。用栈可以维护到栈顶为止的哈希值，每次 push 就是栈顶的值加上当前值乘上 。 不过，这个东西还是太难发现了。 我们不妨换个角度。 简而言之，你从左往右做操作，相

我不会啊。 感觉是若干套路的集合。 首先显然有 。对于 的情况下，可以计算所有 的值，用莫反或者子集反演计算 的值。 这里提一下用子集反演替代一部分莫反的情况。当你要求的函数只和质数集合 有关的时候，那么可以使用子集反演代替莫反。核心原理是在 的情况下，一个数不同质数的个数不会超过 个，稍后我们来讲解一下如何用这个解决这个题目。 但这个题目由于有 次幂的影响，我们很难将 暴力展开计

神在哪里。 首先这意味着只有最后一层是不满的，可以散着一些叶子。否则你可以把最深的叶子往上提一层。 然后根据 BST 一个节点对应一个区间的规则，不难想到一个区间 DP。 表示值域在 之间，根节点奇偶性是偶数/奇数的情况。转移是枚举一下最后一层分给左侧几个叶子，右侧几个叶子，算出根节点，然后根据根节点奇偶性做转移。 然后有一个观察，就是你发现给值域整体加上一个 是不会破坏奇偶性要求的。因此后文

感觉远古 和现在 难度差远了。 不妨先考虑没有限制的情况。 首先对于这种问题，可以考虑转化成一个序列上的问题。 其实就是，有长度为 的序列 和长度为 的序列 ，有两种匹配方式： 匹配 ，对应横放的骨牌。 匹配 ，对应竖放的骨牌。 此时可以考虑做一个容斥原理。但是实际上你发现并不是很好容斥。 继续考虑，不妨考虑如何生成一组匹配。可以先考虑进行一些 的匹配，然后对于每个 的匹配，

好题。 首先考虑最简单的区间 DP， 表示在横坐标 ，纵坐标 的最小复杂度，每次转移的时候枚举一下切割线，每次取 即可做到 的复杂度。 你会发现这个复杂度显然不太能接受。 我们考虑优化。不妨分析一下这个复杂度有什么性质。 直觉上来说，肯定是越大的矩形复杂度就越大。形式化的说，如果一个矩形的复杂度为 ，那么在这个矩形的基础上任意增加一行或者一列，新的矩形的复杂度至少是 。 证明比较无脑，直接数

看上去是要维护一个二维数组，支持区间平移。但是仔细观察后你发现向下的平移只会在最后一列出现。 因此我们实际上只需要支持最后一列的向上平移，和行的向左平移即可。 平衡树做法 对于这种区间平移的问题有一种比较无脑的做法就是直接平衡树。 更具体的，我们对于每行的前 个元素和最后一列的 个元素开一颗平衡树。 每次我们删除第 行的平衡树的第 个元素，将最后一列对应的平衡树的第 个元素插入到最后。然