2017-Sp124-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场cjb和yzc想好了H，cjb上机写SAM。sub表示会A，上机写了一段时间换yzc写H，获得ole。sub上机写A获得wa，yzc改成32位+线段树获得wa，只会sub又wa A，yzc继续wa，发现没写多组数据。只会yzc获得tle，sub上机终于'''A3y131'''，yzc改成树状数组，'''H6y142'''。cjb上机'''E1y164'''。sub和yzc开了D，'''D2y205'''。之后sub刚了一万年G，搞不定。yzc在完场前口胡了C，根本写不完。
== 总结 ==
=== chenjb ===
前面代码感觉都不太好....但我感觉这个C我们至少写一个小时，G可能就是搞不定，所以可能也就只能4题了....
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：O(n)找到所有合法的块，大力dp即可，注意一开始一个位置不能变。

 * B：yzc

 * C：sub

 * D：k=1的dp直接f[i][j]代表头是i，尾是j大力dp即可，利用第二类斯特林数展开即可维护k次方。

 * E：f[p][i]表示i开始2^p^个位置的区间点，对于一组新添加的(x,y,l)，则类似于rmq，merge(f[len][x],f[len][y])和merge(f[len][x+l-(1<<len)],f[len][y+l-(1<<len)])。最后从大到小枚举p，每次利用f[p][i]的实际父亲对应的起点j，merge(f[p-1][i],f[p-1][j])和merge(f[p-1][i+(1<<(p-1))]),f[p-1][j+(1<<(p-1))])逐一合并即可。最后扫一遍f[0][i]，答案为2^依然为根的点数量^。

 * F：

 * G：sub

 * H：用后缀自动机求出S+T每个后缀能在S和T中匹配的长度，然后就变成了一个简单的二维区间询问问题。

 * I：

 * J：cjb

 * [https://wiki.icpc.camp/twsf/ICPCCamp%202016%20Day2%20ZhejiangU%20Contest TheWaySoFar]
 * [https://wiki.icpc.camp/dreadnought/ICPCCamp%202016%20Day%202%20-%20ZhejiangU%20Contest Dreadnought]

流水账

开场cjb和yzc想好了H，cjb上机写SAM。sub表示会A，上机写了一段时间换yzc写H，获得ole。sub上机写A获得wa，yzc改成32位+线段树获得wa，只会sub又wa A，yzc继续wa，发现没写多组数据。只会yzc获得tle，sub上机终于A3y131，yzc改成树状数组，H6y142。cjb上机E1y164。sub和yzc开了D，D2y205。之后sub刚了一万年G，搞不定。yzc在完场前口胡了C，根本写不完。

总结

chenjb

前面代码感觉都不太好....但我感觉这个C我们至少写一个小时，G可能就是搞不定，所以可能也就只能4题了....

oipotato

subconscious

题解

• A：O(n)找到所有合法的块，大力dp即可，注意一开始一个位置不能变。
• B：yzc
• C：sub
• D：k=1的dp直接f[i][j]代表头是i，尾是j大力dp即可，利用第二类斯特林数展开即可维护k次方。
• E：f[p][i]表示i开始2^p个位置的区间点，对于一组新添加的(x,y,l)，则类似于rmq，merge(f[len][x],f[len][y])和merge(f[len][x+l-(1<依然为根的点数量。
• F：
• G：sub
• H：用后缀自动机求出S+T每个后缀能在S和T中匹配的长度，然后就变成了一个简单的二维区间询问问题。
• I：
• J：cjb
• TheWaySoFar
• Dreadnought

附加文件

• 1.png by chenjb