2017-Sp76-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，有人过了F，cjb读了就上机写F，sub给yzc讲了D，yzc上机wa了一发，cjb之后'''F1y49'''。yzc修正了D的做法，'''D2y59'''。紧接着sub上机写J，cjb和yzc讨论K，sub中途出现了问题，cjb上机写后缀数组，之后sub调整了做法，'''J1y120'''。cjb和yzc很快把K搞完了，之后获得tle，调整了之后还是tle，决定换成dc3，之后就在wa和tle中疯狂来回，sub多次上机写B。cjb感觉I可以随机过，就让yzc上机写I，'''I1y222'''。cjb上机敲Pollard_Rho，sub上机又获得tle，之后sub先调B，终于'''B1y268'''。三个人迅速调C，wa了几发后终于'''C4y288'''。最后cjb和yzc坚持搞K，依然爆炸。最后发现是dc3板子错了，改成zju板子就过了....
== 总结 ==
=== chenjb ===
fuck，辣鸡dc3，下次还是得相信ZJU板子啊....另外今天sub可能状态一般，需要休息，md真开学了fuck！
=== oipotato ===

=== subconscious  ===
== 题解 ==
 * K：
  * 题意：给定一个关于S的子串的左右端点的函数，求S中每一个在T中出现的子串的函数的最大值。
  * cjb题解：可以用后缀数组把两个串连起来后，考虑一定会取极大值，直接在sa数组上找到向前向后最近的B串后缀，算下lcp就能维护2-point了，注意要用dc3，不然会tle。
  *  yzc题解：观察可得函数在l确定，r增加时不减，故只需要知道对于每一个起点l，最远的T中出现的子串对应的r在哪。考虑对T建SAM，移动右端点时，只需查看是否存在此后继即可，左端点移动时，由于右端点不动，则新子串在SAM上对应的点，要么不变，要么就是原来点的parent树的父亲，判断长度之后更新即可。
 * [https://wiki.icpc-camp.org/twsf/ICPCCamp%202016%20Day6%20SPb%20SU%20and%20SPb%20AU%20Contest The Way So Far]
 * [https://wiki.icpc-camp.org/dreadnought/ICPCCamp%202016%20Day%205%20-%20SPb%20SU%20and%20SPb%20AU%20Contest Dreadnought]
 * [http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20SPb%20SU%20SPb%20AU%20Contest Heynihao]
== 补题 ==
 * ~~K~~ by yzc
 * ~~L~~ by sub

流水账

开场各自看题，有人过了F，cjb读了就上机写F，sub给yzc讲了D，yzc上机wa了一发，cjb之后F1y49。yzc修正了D的做法，D2y59。紧接着sub上机写J，cjb和yzc讨论K，sub中途出现了问题，cjb上机写后缀数组，之后sub调整了做法，J1y120。cjb和yzc很快把K搞完了，之后获得tle，调整了之后还是tle，决定换成dc3，之后就在wa和tle中疯狂来回，sub多次上机写B。cjb感觉I可以随机过，就让yzc上机写I，I1y222。cjb上机敲Pollard_Rho，sub上机又获得tle，之后sub先调B，终于B1y268。三个人迅速调C，wa了几发后终于C4y288。最后cjb和yzc坚持搞K，依然爆炸。最后发现是dc3板子错了，改成zju板子就过了....

总结

chenjb

fuck，辣鸡dc3，下次还是得相信ZJU板子啊....另外今天sub可能状态一般，需要休息，md真开学了fuck！

oipotato

subconscious

题解

  • K：
    • 题意：给定一个关于S的子串的左右端点的函数，求S中每一个在T中出现的子串的函数的最大值。
    • cjb题解：可以用后缀数组把两个串连起来后，考虑一定会取极大值，直接在sa数组上找到向前向后最近的B串后缀，算下lcp就能维护2-point了，注意要用dc3，不然会tle。
    • yzc题解：观察可得函数在l确定，r增加时不减，故只需要知道对于每一个起点l，最远的T中出现的子串对应的r在哪。考虑对T建SAM，移动右端点时，只需查看是否存在此后继即可，左端点移动时，由于右端点不动，则新子串在SAM上对应的点，要么不变，要么就是原来点的parent树的父亲，判断长度之后更新即可。
  • The Way So Far
  • Dreadnought
  • Heynihao

补题

  • K by yzc
  • L by sub
附加文件