差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:2020-nowcoder-multi-1 [2020/07/16 22:15]
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 序列的排名。
-**题解**：由于字符集大小最大为 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}$。
@@ 行 106: / 行 106: @@
 由于每个变量恰好只会在两个不同的方程中出现，考虑解改方程的过程，若选择了一条边，则说明我们用一个变量，盖住了两个方程右边的某个单位 "1"。每个方程右边的每个单位 "1" 只能被一个变量盖到。该过程实际上就和一般图的匹配很像了。
-因此一个建立一般图匹配的方式，即将每个变量看做是匹配中的两个点、每个方程看做是匹配中的 $d_u$ 个点。在第 $i$ 条边不选的情况下，我们让变量 $x_i$ 对应的两个点匹配上，即该两个点之间有一条边；第 $i$ 条边选的情况下，我们让变量 $x_i$ 对应的两个点，分别匹配到两个不同的方程所对应的点上。
+因此一个建立一般图匹配的方式，即将每个变量看做是匹配中的两个点、每个方程看做是匹配中的 $d_u$ 个点。在第 $i$ 条边不选的情况下，我们让变量 $x_i$ 对应的两个点匹配上；第 $i$ 条边选的情况下，我们让变量 $x_i$ 对应的两个点，分别匹配到两个不同的方程所对应的点上。
-为了避免出现变量的两个点均与同一个方程对应的两个点匹配上，在两个方程都=2的情况下，我们强制要求其中一个方程的两个点，只与变量的某个点相连，另一个方程的两个点只与变量另一个点相连。这样就能保证匹配的过程与解前面的方程组的过程是一致的了。
+为了避免出现变量的两个点均与同一个方程对应的两个点匹配上，我们强制要求其中一个方程的两个点，只与变量的某个点相连，另一个方程的两个点只与变量另一个点相连。
+综上，建立的匹配模型为，每条边拆成两个点 $e$, $e'$，每个点拆成 $d_u$ 个点。$e$ 和 $e'$ 建边。对于连接 $u$、$v$ 的边，则让 $u$ 拆的点与 $e$ 建边，$v$ 拆的点与 $e'$ 建边。
+这样该匹配模型有完美匹配的情况下，就等价于前面的方程组有一组合法的解，也就等价于有一种删边的方案满足度数限制。
 ===== 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)!}$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具