典型的反转 ，整理一下此类题思路。 题意简述 你现在要按照如下方式生成一个长度为 的数组： 对于 ，有 的概率设 ，有 的概率设 。 对于一个长度为 的数组，计算 。特别地，。此时 数组的最大前缀和 。现在给定 个正整数 。该数组最大前缀和为 时，该数组的分数为 。 要求对于所有 ，求出生成出的数组的期望分数对 取模的结果。 。 思路分析 正向考虑困...

题意简述 有 个人在数轴上等速移动，每个人有一个初始方向，两人相遇时，有 的概率左边的人会消失， 的概率右边的人会消失，求最终恰有 个人抵达数轴最左端， 个人抵达数轴最右端的概率。 复杂度要求 。 题解 首先，我们找到最靠右的抵达数轴左端点的人 ，那么最靠左的抵达数轴右端点的人一定在他的右边，且一定恰是 。简单分类讨论易证。 接下来，我们枚举 所在的位置，分别求其左...

结论题可爱 题意简述 给出一个字符串 ，你可以使用一个印章，每次能印出一个相同的字符串 ，印章印过的地方可以重叠，但是重叠部分的字符必须相同。求最小的印章长度，。 思路分析及证明 首先可以想到 。设 代表恰好覆盖 的长度为 的前缀 所需要的最小的印章长度。 通过尝试，我们容易发现如下引理。 引理0：若 能够恰好覆盖 ， 能够恰好覆盖 ，则 能恰好覆盖 。 证明：...

爹级思维题。为什么是 T0 啊 nmd 题意简述 给出一个栈，你需要向其中按顺序投入 个弹珠，弹珠有 种不同颜色，你可以投入任意颜色的弹珠。如果栈顶部 颗弹珠颜色是相同的，你需要将它们取出。现在，要求求出能够使所有弹珠都被取出的投入方案数。 数据范围：。 思路分析 分析个头。分析不出来。直接讲做法。 考虑如果采用传统的方法，会发现状态与状态之间的重复极其难以处理。也就是...

题意简述 给定 个城市，第 个城市收集到了高度为 的水，要求通过使用 次地下连通系统，每次使用可以使若干个城市的水箱相连通，然后使它们的水位变为它们的平均值。要求求出 次操作后， 号城市水箱中的水位的最大值。 策略选择及最优性证明 引理0：我们一定不会对初始水位不高于 号的水箱操作，操作与操作之间选择的水箱一定不会有重叠。 证明：显然。 引理1：对于初始水位...