为什么我会在凌晨一点钟写这个题解。 非常好题目！ 考察什么图案是合法的。 首先你注意到对于每行每列，我们只需要保留最后一次在这一行或列的元素即可。 不妨给每个行/列都钦定一个优先级，优先级底的在上面，这样每个格子的颜色就是行和列中优先级较低的那个对应的颜色。考虑一组优先级何时可以实现。 首先，最上面一层一定是一个十字。这意味着一定有一行一列优先级都是 。这个显然是必要的。然后你发现，这个也是充分的

非常好题目。 和 P4707 类似的，假设 表示第 种物品满足条件的时间，那么我们就是要求 。 通常来说可以考虑枚举一个时间 ，求 并相加。但是问题在于这个 可以很大。因为可能出现一直抽到同一个元素，导致其余元素迟迟不能满足条件的情况。 因此直接求 的做法是比较困难的。此时的一个常见思路就是考虑使用 反演将 转化成 来计算。 具体的，我们有以下式子。 对于外层套一个期望的情况下也

省流：啊宝宝你是一个 P4117 + P4119 + P5611（所以这题题号为什么不是 P13847）。 模拟赛看到了这玩意，想了依托做法，随便写了个常数巨大的代码然后跑的飞慢，最后喜提暴力分。 不妨先假设 同阶，然后扔掉修改。 来想想暴力咋做。 首先你可以从前往后扫描，维护最后一个 出现的位置和 出现的位置。每次遇到 或者 就更新一下答案，然后更新位置。这样就是 做法。以防你不知道

我不懂主席树，但是我会整体二分。 不妨先考虑没有修改的情况怎么做。 看到中位数有个著名的 trcik 就是二分转 。 不妨考虑二分 ，对于询问 判断是否存在一条中位数大于等于 的路径。 判断方法就是将小于 的数点权设置为 ,大于的权值设置成 。如果一条路径和的权值小于 ，那么这条路径的中位数一定大于 。 自然的，我们就会想要查询经过 且权值最小的路径。注意到 互相不为祖先，因此两个端点一

本质推式子题目。 不妨考虑什么时候应该停止，什么时候应该继续往下走。 不妨将四种卡片分别记作 。 分别表示分数是 的卡片， 表示直接结束游戏的卡片。 首先一个观察是 卡片没有用。不妨考虑暴力 DP，枚举下一种可能。你可以将“第一次抛的结果”替换成”第一次抛到非 卡片的概率“，这样就变成了一个条件概率，并且这个条件概率和剩下的 卡片数量无关。 另外一个观察就是 的卡片在没有被淘汰的时候一定

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

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

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

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

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