2020-2021:teams:intrepidsword:2020-nowcoder-multi-1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020-nowcoder-multi-1 [2020/07/15 01:06] admin 创建 |
2020-2021:teams:intrepidsword:2020-nowcoder-multi-1 [2020/07/16 23:07] (当前版本) chielo [A. B-Suffix Array] |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| ====== Solutions ====== | ====== Solutions ====== | ||
| + | |||
| + | ===== A. B-Suffix Array ===== | ||
| + | |||
| + | **题目大意**：定义一个字符串的 B 函数为字符串到相同长度非负整数序列的映射，第 $i$ 个整数表示字符串中在 $i$ 前面与 $i$ 字符相同的字符之间的最小距离，如果前面没有和自己一样的字符则记为 0。求每个后缀的 B 序列的排名。 | ||
| + | |||
| + | **题解**：由于字符集大小最大为 2，会发现经过函数 B 计算后，最多只会有俩 0。第一个字符对应的 B 必然是 0，接下来与第一个字符不同的位置上对应的 B 也是 0。而且这两个 0 之间也必然都是 1，因为前面只有一种字符。 | ||
| + | |||
| + | 因此在所有的后缀中，函数值的两个 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}$。 | ||
| + | |||
| + | 综上，我们首先计算一下原串的 B，然后用后缀数组对 B 序列的后缀进行排序。接下来对于每个后缀 $s_{a\ldots n}$，第一关键字为该后缀中最靠前的两个不同的字符的距离（即对应 B 序列中两个 0 的距离）；第二关键字当后缀全是相同的字符时为 0，否则为 1，用来保证 B 序列实际没有第二个 0 的情况下，让较短的该后缀排名尽量靠前；第三关键字即为 $B(s)_{a+l+1\ldots n}$ 在原串 B 序列的后缀中的排名。排序。 | ||
| + | ===== B. Infinite Tree ===== | ||
| + | |||
| + | **题目大意**：在 $N^{+}$ 上定义一棵树，$n$ 的父亲为 $\frac{n}{\min n}$。有一个权值数组 $w$，求 $\min_{u}\sum_{i=1}^{m}w_{i}\cdot\text{dis}(u,i!)$。 | ||
| + | |||
| + | **题解**：$\text{dis}(u,v)=\text{dep}(u)+\text{dep}(v)-2\text{dep}(u,v)$。如果能建出虚树，那么一次 ''%%dfs%%'' 就能求解。 | ||
| + | |||
| + | 考虑建虚树的过程，与普通虚树唯一不同的地方在于求 $(i-1)!$ 和 $i!$ 的 ''%%lca%%''。将 $i$ 分解，考虑其中最大的质因子，易见在该质因子之后 $(i-1)!$ 和 $i!$ 就分岔了。这样一来，可以用树状数组维护每个质因子的数量，而 ''%%lca%%'' 的深度即为 $(i-1)!$ 中大于等于 $i$ 最大质因子的数量。 | ||
| + | |||
| + | ===== C. Domino ===== | ||
| + | |||
| + | [[http://math.uni.lu/parlier/Papers/domino2016-08-25.pdf|论文]]题。 | ||
| + | |||
| + | ===== D. Quadratic Form ===== | ||
| + | |||
| + | **题目大意**：给出正定矩阵 $A$，求满足 $\boldsymbol{x}^{T}A\boldsymbol{x}\le1$ 的条件下，$\max_{\boldsymbol{x}}\boldsymbol{b}^{T}\boldsymbol{x}$。 | ||
| + | |||
| + | **题解**：注意原问题对称，将其转化为最小值，直接 KKT 条件暴解。需要满足的条件是： | ||
| + | |||
| + | $$ | ||
| + | \begin{cases} | ||
| + | \nabla f(\boldsymbol{x})+\mu\nabla g(\boldsymbol{x})=\boldsymbol{0}\\ | ||
| + | \mu g(\boldsymbol{x})=\boldsymbol{0}\\ | ||
| + | \mu\ge0\\ | ||
| + | g(\boldsymbol{x})\le0\\ | ||
| + | \end{cases} | ||
| + | $$ | ||
| + | |||
| + | 其中 $f(\boldsymbol{x})=\boldsymbol{b}^{T}\boldsymbol{x}$，$g(\boldsymbol{x})=\boldsymbol{x}^{T}A\boldsymbol{x}-1$。 | ||
| + | |||
| + | $$ | ||
| + | \begin{aligned} | ||
| + | \text{tr}(\mathrm{d}g)&=\text{tr}(\mathrm{d}(\boldsymbol{x}^{T}A\boldsymbol{x}))\\ | ||
| + | &=\text{tr}(\mathrm{d}(\boldsymbol{x}^{T})A\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ | ||
| + | &=\text{tr}((\mathrm{d}\boldsymbol{x})^{T}A\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ | ||
| + | &=\text{tr}((A\boldsymbol{x})^{T}\mathrm{d}\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ | ||
| + | &=\text{tr}(\boldsymbol{x}^{T}A^{T}\mathrm{d}\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ | ||
| + | &=\text{tr}(\boldsymbol{x}^{T}(A^{T}+A)\mathrm{d}\boldsymbol{x}) | ||
| + | \end{aligned} | ||
| + | $$ | ||
| + | |||
| + | 而 $\mathrm{d}g=\text{tr}\left(\left(\frac{\mathrm{d}g}{\mathrm{d}\boldsymbol{x}}\right)^{T}\mathrm{d}\boldsymbol{x}\right)$，对比系数有 $\frac{\mathrm{d}g}{\mathrm{d}\boldsymbol{x}}=2A\boldsymbol{x}$。可得 $\boldsymbol{b}+2\mu A\boldsymbol{x}=\boldsymbol{0}$。若 $\mu=0$，那么必然有 $\boldsymbol{b}=\boldsymbol{0}$。除此以外，$\mu>0$。因而 $g(\boldsymbol{x})=\boldsymbol{0}$。又有 $\boldsymbol{x}=-\frac{1}{2\mu}A^{-1}\boldsymbol{b}$。可得 | ||
| + | |||
| + | $$ | ||
| + | \begin{aligned} | ||
| + | &\boldsymbol{x}^{T}A\boldsymbol{x}\\ | ||
| + | =&\frac{1}{4\mu^{2}}\boldsymbol{b}^{T}A^{-1}AA^{-1}\boldsymbol{b}\\ | ||
| + | =&\frac{1}{4\mu^{2}}\boldsymbol{b}^{T}A^{-1}\boldsymbol{b}=1 | ||
| + | \end{aligned} | ||
| + | $$ | ||
| + | |||
| + | 因而，$\mu=\frac{1}{2}\sqrt{\boldsymbol{b}^{T}A^{-1}\boldsymbol{b}}$。代入得极小值为 $-\sqrt{\boldsymbol{b}^{T}A^{-1}\boldsymbol{b}}$。 | ||
| + | |||
| + | ===== E. Counting Spanning Trees ===== | ||
| + | |||
| + | [[https://arxiv.org/pdf/0706.2918.pdf|论文]]题。 | ||
| + | |||
| + | ===== F. Infinite String Comparision ===== | ||
| + | |||
| + | **题目大意**：给两个字符串，问它们分别无限循环后是否相等。 | ||
| + | |||
| + | **题解**：考虑前 $|a|+|b|$ 个字符，若无失配，显然 $|a|,|b|$ 分别是它的周期，根据弱周期引理，$\gcd(|a|,|b|)$ 也是它的周期，显然永远相等。 | ||
| + | |||
| + | ===== G. BaXianGuoHai, GeXianShenTong ===== | ||
| + | |||
| + | $(\text{mod}+1)(\text{mod}-1)$ 似乎是周期，但是不会证。然后卡常就过了。 | ||
| + | |||
| + | ===== H. Minimum-cost Flow ===== | ||
| + | |||
| + | **题目大意**：给个费用流的图，费用知道但是边的容量不知道，不过边的容量都一样。多次询问，问如果边的容量变成了分数 $u_i / v_i$，从源到汇跑一个单位的流量的最小费用是多少。 | ||
| + | |||
| + | **题解**： | ||
| + | 由于边的容量是相同的，考虑边的容量确定为 $a$ 后，在图上进行多次增广。容易发现只要能找到一条增广路，必然能跑出恰好 $a$ 份的流量，且是当前能走的增广路中，费用最小的。图没有负边权所以不用担心负环。 | ||
| + | |||
| + | 那既然每次增广跑走的流量也是相同的，而且等于边的容量，那我们直接以 1 为容量跑跑费用流，记录一下每次增广时的费用。 | ||
| + | |||
| + | 对于询问 $u_i / v_i$，若大于或等于 $1$ 那我们直接用第一次增广时的费用回答就好；如果为 $0$，那没得跑；如果小于 $1$，那么我们肯定得先增广 $\lfloor v_i / u_i \rfloor$ 次，需要求前面这些增广时的费用和，然后剩下的一点点流量再用劣一点的增广路跑完流量即可。 | ||
| + | ===== 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 ===== | ||
| + | |||
| + | **题目大意**：求 $\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.1594746400.txt.gz · 最后更改: 2020/07/15 01:06 由 admin
