2016-E34-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Time||Problem||Result||
||03:31:17||H||Accepted||
||03:15:59||H||Time Limit Exceeded !#2||
||03:10:57||G||Accepted||
||03:02:01||G||Wrong Answer !#2||
||01:19:15||C||Accepted||
||01:11:23||B||Accepted||
||00:54:50||F||Accepted||
||00:49:10||F||Wrong Answer !#2||
||00:39:47||A||Accepted||
||00:19:04||I||Accepted||
||00:08:49||L||Accepted||
比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day4.htm
start at 10:00
== 流水账 ==
== 总结 ==
== 题解 ==
IL略去不表。
=== A. The Catcher in the Rye [sfiction] ===
光路最短，三分入射角即可。
=== B. Dissertation [sfiction] ===
dp(i,j)表示B串[1..i]在A串中长为j的公共子序列的最早结束位置。则dp(i,j)可以从dp(i-1,j)或者dp(i-1,j-1)转移过来。后者需要查询A串中dp(i-1,j-1)后B[i]的最早出现位置。根据预处理和查询的方式不同可以做到O(n+m!^2logm)或者O(nS+m!^2)。如果对所有dp(i,j)按照值的大小像最短路一样处理，则可以做到O(n+m!^2)。
=== C. Dominoes [JTJL, Akalm] ===
数字视为点，多米诺牌视为边。相当于求Kn的平面表示。n>=5时不存在。
=== D. Endgame ===
TBD
=== E. Evacuation [sfiction] ===
用set动态维护可达区间即可，区间增长lazy，区间相交作为一个合并事件，与闪电同步处理。O(nlogn)。
=== F. Factory [JTJL] ===
三分套三分或者模拟退火解费马点。
=== G. Grasshoppers [JTJL, sficiton] ===
xi=2x_{i+1}-1，用幂次代替下标得到多项式f(n)=f(n-1)*(2n-1)。快速幂+FFT求出多项式幂（循环意义下）。O(nlognlogt)。
=== H. Education Nightmare [JTJL, Akalm] ===
最大代价是所选s-m路径长度加上m到未经过点的最大距离。于是可以枚举最大深度d，维护访问所有深度大于d的点所需的最短路径长度。O(nlogn)。
=== J. Spoonerisms [Akalm, sfiction] ===
对所有非空前后缀去重，然后视为点，根据字符串在前后缀之间连边（长为l的字符串即有l-1个连接关系），得到一个二分图。在二分图上找四元环。O(n!^1.5)。
这个就是Trie树拼2016E30的G，赛场上居然想到别的地方去了……
=== K. A Text Problem [Akalm, JTJL] ===
TBD???| Time | Problem | Result |
| 03:31:17 | H | Accepted |
| 03:15:59 | H | Time Limit Exceeded !#2 |
| 03:10:57 | G | Accepted |
| 03:02:01 | G | Wrong Answer !#2 |
| 01:19:15 | C | Accepted |
| 01:11:23 | B | Accepted |
| 00:54:50 | F | Accepted |
| 00:49:10 | F | Wrong Answer !#2 |
| 00:39:47 | A | Accepted |
| 00:19:04 | I | Accepted |
| 00:08:49 | L | Accepted |
比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day4.htm
start at 10:00
流水账
总结
题解
IL略去不表。
A. The Catcher in the Rye [sfiction]
光路最短，三分入射角即可。
B. Dissertation [sfiction]
dp(i,j)表示B串[1..i]在A串中长为j的公共子序列的最早结束位置。则dp(i,j)可以从dp(i-1,j)或者dp(i-1,j-1)转移过来。后者需要查询A串中dp(i-1,j-1)后B[i]的最早出现位置。根据预处理和查询的方式不同可以做到O(n+m!2logm)或者O(nS+m!2)。如果对所有dp(i,j)按照值的大小像最短路一样处理，则可以做到O(n+m!^2)。
C. Dominoes [JTJL, Akalm]
数字视为点，多米诺牌视为边。相当于求Kn的平面表示。n>=5时不存在。
D. Endgame
TBD
E. Evacuation [sfiction]
用set动态维护可达区间即可，区间增长lazy，区间相交作为一个合并事件，与闪电同步处理。O(nlogn)。
F. Factory [JTJL]
三分套三分或者模拟退火解费马点。
G. Grasshoppers [JTJL, sficiton]
xi=2x_{i+1}-1，用幂次代替下标得到多项式f(n)=f(n-1)*(2n-1)。快速幂+FFT求出多项式幂（循环意义下）。O(nlognlogt)。
H. Education Nightmare [JTJL, Akalm]
最大代价是所选s-m路径长度加上m到未经过点的最大距离。于是可以枚举最大深度d，维护访问所有深度大于d的点所需的最短路径长度。O(nlogn)。
J. Spoonerisms [Akalm, sfiction]
对所有非空前后缀去重，然后视为点，根据字符串在前后缀之间连边（长为l的字符串即有l-1个连接关系），得到一个二分图。在二分图上找四元环。O(n!^1.5)。
这个就是Trie树拼2016E30的G，赛场上居然想到别的地方去了……
K. A Text Problem [Akalm, JTJL]
TBD???