2020-2021:teams:intrepidsword:2020-nowcoder-multi-1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020-nowcoder-multi-1 [2020/07/16 21:48] chielo [H. Minimum-cost Flow] |
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}$。 | ||
| 行 92: | 行 92: | ||
| 那既然每次增广跑走的流量也是相同的，而且等于边的容量，那我们直接以 1 为容量跑跑费用流，记录一下每次增广时的费用。 | 那既然每次增广跑走的流量也是相同的，而且等于边的容量，那我们直接以 1 为容量跑跑费用流，记录一下每次增广时的费用。 | ||
| - | 对于询问 $u_i / v_i$，若大于或等于 $1$ 那我们直接用第一次增广时的费用回答就好；如果为 $0$，那没得跑；如果小于 $1$，那么我们肯定得先增广 $\lfloor v_i / u_i \rfloor$ | + | |
| + | 对于询问 $u_i / v_i$，若大于或等于 $1$ 那我们直接用第一次增广时的费用回答就好；如果为 $0$，那没得跑；如果小于 $1$，那么我们肯定得先增广 $\lfloor v_i / u_i \rfloor$ 次，需要求前面这些增广时的费用和，然后剩下的一点点流量再用劣一点的增广路跑完流量即可。 | ||
| ===== I. 1 or 2 ===== | ===== I. 1 or 2 ===== | ||
| + | |||
| + | **题目大意**：给一个无向图，然后每个点给一个 $1$ 或 $2$ 的数 $d_u$，问有没有办法能干掉若干条边，使得新的图中，每个点的度数和给的数相同。 | ||
| + | |||
| + | **题解**： | ||
| + | 最后的图必然是一些链和一些环，链的两端的 $d_u$ 必然都是 $1$，剩下的都是 $2$。 | ||
| + | |||
| + | 考虑第 $i$ 条边选或不选，即变量 $x_i \in \{0, 1\}$，对于每个点 $u$，我们有 $\sum_{e_i\text{ incident to }u}{x_i} = d_u$。 | ||
| + | 该方程组有 0/1 的解则意味着原图能有一个方案满足度数的限制。 | ||
| + | |||
| + | 由于每个变量恰好只会在两个不同的方程中出现，考虑解改方程的过程，若选择了一条边，则说明我们用一个变量，盖住了两个方程右边的某个单位 "1"。每个方程右边的每个单位 "1" 只能被一个变量盖到。该过程实际上就和一般图的匹配很像了。 | ||
| + | |||
| + | 因此一个建立一般图匹配的方式，即将每个变量看做是匹配中的两个点、每个方程看做是匹配中的 $d_u$ 个点。在第 $i$ 条边不选的情况下，我们让变量 $x_i$ 对应的两个点匹配上；第 $i$ 条边选的情况下，我们让变量 $x_i$ 对应的两个点，分别匹配到两个不同的方程所对应的点上。 | ||
| + | |||
| + | 为了避免出现变量的两个点均与同一个方程对应的两个点匹配上，我们强制要求其中一个方程的两个点，只与变量的某个点相连，另一个方程的两个点只与变量另一个点相连。 | ||
| + | |||
| + | 综上，建立的匹配模型为，每条边拆成两个点 $e$, $e'$，每个点拆成 $d_u$ 个点。$e$ 和 $e'$ 建边。对于连接 $u$、$v$ 的边，则让 $u$ 拆的点与 $e$ 建边，$v$ 拆的点与 $e'$ 建边。 | ||
| + | |||
| + | 这样该匹配模型有完美匹配的情况下，就等价于前面的方程组有一组合法的解，也就等价于有一种删边的方案满足度数限制。 | ||
| ===== 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.1594907333.txt.gz · 最后更改: 2020/07/16 21:48 由 chielo
