2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_1 [2020/07/13 10:32] maxdumbledore |
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_1 [2020/07/16 23:33] (当前版本) mountvoom [A] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| ====== 题解 ====== | ====== 题解 ====== | ||
| + | ===== A ===== | ||
| + | 论文题，题解说最终的顺序是求出B-function以后的后缀数组的顺序，原理不懂。 | ||
| + | |||
| + | 比赛时的想法是快速比较任意两个串的B-function，先把原串的B-function求出来，任意一个后缀的B-function都是原串B-function的一个后缀，再把第一个a和第一个b的位置变成0。 | ||
| + | |||
| + | 而有一个0肯定在第一个位置，那么对原串的B-function求一个后缀数组，利用他们的LCP分类讨论第二个0的位置即可快速比较，最后直接排序即可。 | ||
| + | ===== D ===== | ||
| + | |||
| + | $P^{T}AP=D,D \in diag(n)\\ | ||
| + | x^{T}Ax=y^{T}Dy,y=P^{-1}x,x=Py,利用合同变换求解P,D\\\\ | ||
| + | 原问题变为:\\\\ | ||
| + | \begin{gather*} | ||
| + | & \max:b^{T}P &\\ | ||
| + | & s.t:\sum_{i=1}^{N}e_{i}y_{i}^{2}\leq 1,e_{i}为D对角元 &\\ | ||
| + | \end{gather*}\\ | ||
| + | b^{T}P=d,(\sum_{i=1}^{N}d_{i}y_{i})^{2} | ||
| + | \leq (\sum_{i=1}^{N}\frac{d_{i}^{2}}{e_{i}})(\sum_{i=1}^{N}e_{i}y_{i}^{2})$ | ||
| + | |||
| + | 考虑几何意义:高维椭圆也可以求解 | ||
| + | |||
| + | 更一般的是利用Lagrange对偶与KKT条件 | ||
| + | |||
| + | $L(x,\lambda )=x^{T}bb^{T}x+\lambda(x^{T}Ax-1),\lambda \geq 0, | ||
| + | 显然L(x,\lambda) \leq x^{T}bb^{T}x\\\\ | ||
| + | 由KKT条件,取得极值时,\nabla_{x} L=0,\lambda(x^{T}Ax-1)=0\\\\ | ||
| + | 2bb^{T}x+2\lambda Ax=0,x^{T}Ax=1\\\\ | ||
| + | x^{T}bb^{T}x = -\lambda,(bb^{T}+\lambda A)=0\\\\ | ||
| + | x^{T}bb^{T}x=b^{T}A^{-1}b$ | ||
| + | |||
| + | |||
| + | by Hardict | ||
| + | ===== F ===== | ||
| + | |||
| + | $水题,取3倍maxlen比较,据说2倍就行,不会证明$ | ||
| + | |||
| + | by Hardict | ||
| ===== I. 1 or 2 ===== | ===== I. 1 or 2 ===== | ||
| 行 51: | 行 87: | ||
| by cmx | by cmx | ||
| + | |||
| + | ===== J ===== | ||
| + | |||
| + | $I_{n}=\int_{0}^{1}x^{n}(1-x)^{n}dx \xrightarrow{分部积分} | ||
| + | \frac{1}{n+1}\int_{0}^{1}(1-x)^{n}dx^{n+1}=\frac{n}{n+1}\int_{0}^{1}x^{n+1}(1-x)^{n-1}dx\\\\ | ||
| + | =\frac{n!}{\frac{(2n)!}{n!}}\int_{0}^{1}x^{2n}dx=\frac{(n!)^{2}}{(2n+1)!}$ | ||
| + | |||
| + | 不过这好像是和$gamma$函数相关，有直接的结论 | ||
| + | |||
| + | by Hardict | ||
| + | |||
| ====== 补题 ====== | ====== 补题 ====== | ||
| + | |||
| + | ===== H ===== | ||
| + | |||
| + | 发现每个$\frac{1}{k}$为一个分界点 | ||
| + | |||
| + | $\frac{1}{k} \leq cap < \frac{1}{k+1}$则需要走最优的$k+1$条路径 | ||
| + | |||
| + | 比赛中我每次扩容后求出了所有最优路径并算前缀和,但一直$TLE$ | ||
| + | |||
| + | 后发现不用计算具体路径，保留每次扩容最小费用就行，只要按从扩容顺序选取，路径虽然会变化但扩容时扩容路径就算走反向边改变路径也不会改变整体费用，也一定有对应路径存在(不按顺序可能矛盾) | ||
| + | |||
| + | by Hardict | ||
2020-2021/teams/alchemist/2020_nowcoder_multiuniversity_1.1594607529.txt.gz · 最后更改: 2020/07/13 10:32 由 maxdumbledore
