2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_1 [2020/07/13 10:02] 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 ===== | ||
| + | |||
| + | I是我认为相当精彩的一道题。赛场上是用了一个网络流假算法，结果因为数据太水侥幸通过。 | ||
| + | |||
| + | 首先d=1 or d=2意味着残存图是由线段和环组成的。网络流/费用流的想法其实在这题来说相当自然。我赛场上的想法是每个点拆出入两点，源点连向左奇数点，右奇数点连向汇点，再按照读入的边，左往右连边。最后d=2的点右往左连cap=2的边。到达一个点的边被赋予-1的费用。我以为只要求出最小费用最大流，一单位流就可以代表了线段，费用取反，看和度数之和是否相等，就能判断了。 | ||
| + | |||
| + | 事实上这个想法漏洞百出，首先根本没有解决好d=2成环的问题。另外仔细想想，如果一条流量路径从a到b，那么反映在网络上就是有左a到右b的一条路径，那么一定就意味着有左b到右边a的一条流量吗？恰恰是不一定的，有可能最大流的对应的图是不对称的。利用三点环，每个点的d为1，就可以否定了（当然赛场上特判了这类奇数个d=1的情况，不过也会有其他反例）。 | ||
| + | |||
| + | 另外一种比较简单的构图，是直接源点连左边，右边连汇点，cap=度数。这种的话也是这样，虽然原图是对称的，可能最大流对应的图是不对称的（情况不多，所以大概都没被卡掉）。 | ||
| + | |||
| + | 接下来介绍一下正解。 | ||
| + | |||
| + | 首先，如果所有d=1，那么相当于求一个一般图的最大匹配，看是否和总点数相等。这里有一个现成的，我没学过的带花树算法。那么存在d=2的点怎么处理呢？ | ||
| + | |||
| + | 我们把d=2的点拆分成两个点，同时对于哪些两头都是d=2的点（x,y）的边，引入点e和e' | ||
| + | |||
| + | 引入边： | ||
| + | (x, e) (x', e) | ||
| + | (y, e') (y', e') | ||
| + | (e, e') | ||
| + | |||
| + | 对于一头是d=1（x）,一头是d=2(y)的边 | ||
| + | |||
| + | 引入边 | ||
| + | (x,y')(x,y) | ||
| + | |||
| + | 如果都是d=1，则直接连。 | ||
| + | |||
| + | 这样构造出来的新图，我们在上面跑一般图的最大匹配，看是否每个点都参与匹配，即可。 | ||
| + | |||
| + | 真的是一种很神仙的构图方式，对于(x, e) (x', e)(y, e') (y', e')(e, e')五条边，如果e和e'匹配，对应该边没有在残图中。反之，e和e'和两头各自的点匹配，对应该边在残图中。其他的d=1点和d=2点的匹配之类，也都能在原图上找到完全对应的连接方式。 | ||
| + | |||
| + | 而如果不是完全匹配，那么对应在原图也就找不到方案。 | ||
| + | |||
| + | 感觉这个构图，真的很神仙，可以当做一种特别的技巧记住。 | ||
| + | |||
| + | 以后这类问题，基本都是带花树算法，千千万万不要往网络流的巨坑里面走。一定要仔细思考！ | ||
| 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.1594605764.txt.gz · 最后更改: 2020/07/13 10:02 由 maxdumbledore
