2020-2021:teams:intrepidsword:2020-nowcoder-multi-1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020-nowcoder-multi-1 [2020/07/16 22:27] chielo [I. 1 or 2] |
2020-2021:teams:intrepidsword:2020-nowcoder-multi-1 [2020/07/16 23:07] (当前版本) chielo [A. B-Suffix Array] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| **题目大意**：定义一个字符串的 B 函数为字符串到相同长度非负整数序列的映射，第 $i$ 个整数表示字符串中在 $i$ 前面与 $i$ 字符相同的字符之间的最小距离，如果前面没有和自己一样的字符则记为 0。求每个后缀的 B 序列的排名。 | **题目大意**：定义一个字符串的 B 函数为字符串到相同长度非负整数序列的映射，第 $i$ 个整数表示字符串中在 $i$ 前面与 $i$ 字符相同的字符之间的最小距离，如果前面没有和自己一样的字符则记为 0。求每个后缀的 B 序列的排名。 | ||
| - | **题解**：由于字符集大小最大为 2，会发现经过函数 B 计算后，最多只会有俩 0，第一个字符对应的 B 必然是 0，接下来与第一个字符不同的位置上对应的 B 也是 0。 | + | **题解**：由于字符集大小最大为 2，会发现经过函数 B 计算后，最多只会有俩 0。第一个字符对应的 B 必然是 0，接下来与第一个字符不同的位置上对应的 B 也是 0。而且这两个 0 之间也必然都是 1，因为前面只有一种字符。 |
| - | 那么在所有的后缀中，函数值的两个 0 靠的越近，排名越靠前；如果没有第二个零，那可以假装末尾有个零，但是排名的时候要尽可能靠前。 | + | 因此在所有的后缀中，函数值的两个 0 靠的越近，排名越靠前；如果没有第二个零，那可以假装末尾有个零，但是排名的时候要尽可能靠前。 |
| 而对于两个 0 之后的序列的字典序大小关系，容易发现由于两个字符都出现过了，那么 0 之后的 B、即相应位置上前面与自己相同的字符的距离，不再会有变化。所以记后缀 $s_{a\ldots n}$ 的 B 序列中两个 0 的距离为 $l$，那么后面的 B 序列与原串的 B 对应的后缀是相同的，即 $B(s_{a\ldots n})_{l+1\ldots n-a} = B(s)_{a+l+1\ldots n}$。 | 而对于两个 0 之后的序列的字典序大小关系，容易发现由于两个字符都出现过了，那么 0 之后的 B、即相应位置上前面与自己相同的字符的距离，不再会有变化。所以记后缀 $s_{a\ldots n}$ 的 B 序列中两个 0 的距离为 $l$，那么后面的 B 序列与原串的 B 对应的后缀是相同的，即 $B(s_{a\ldots n})_{l+1\ldots n-a} = B(s)_{a+l+1\ldots n}$。 | ||
| 行 114: | 行 114: | ||
| 这样该匹配模型有完美匹配的情况下，就等价于前面的方程组有一组合法的解，也就等价于有一种删边的方案满足度数限制。 | 这样该匹配模型有完美匹配的情况下，就等价于前面的方程组有一组合法的解，也就等价于有一种删边的方案满足度数限制。 | ||
| ===== J. Easy Integration ===== | ===== J. Easy Integration ===== | ||
| + | |||
| + | **题目大意**：求 $\int_{0}^{1} \left(x - x^2\right)^n \mathrm{d}x$。是个有理数，给出模意义下的值。 | ||
| + | |||
| + | **题解**： | ||
| + | $\left(x - x^2\right)^n = x^n (1-x)^n$。那我们记 $v_{a,b} = \int_{0}^{1} x^a (1-x)^b \mathrm{d}x$。 | ||
| + | |||
| + | $v_{a,0} = \int_{0}^{1} x^a \mathrm{d}x = 1 / (a + 1)$。 | ||
| + | |||
| + | \begin{array}{rcl} | ||
| + | v_{a,b} &=& \int_{0}^{1} x^a (1-x)^b \mathrm{d}x \\\\ | ||
| + | &=& \left(\frac{1}{a+1} x^{a+1} (1-x)^b\right)\mid_0^1 + \frac{b}{a+1} \int_{0}^{1} x^{a+1} (1-x)^{b-1} \mathrm{d}x \\\\ | ||
| + | &=& \frac{b}{a+1} v_{a+1,b-1} \\\\ | ||
| + | &=& \frac{b! a!}{(a+b)!} v_{a+b,0} \\\\ | ||
| + | &=& \frac{b! a!}{(a+b+1)!} | ||
| + | \end{array} | ||
| + | |||
| + | 答案即为 $\frac{(n!)^2}{(2n+1)!}$。 | ||
2020-2021/teams/intrepidsword/2020-nowcoder-multi-1.1594909636.txt.gz · 最后更改: 2020/07/16 22:27 由 chielo
