2017-Sp200-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，A和K两个板子题出现了，cjb上机敲板子，然后让yzc上去补全，出了点偏差'''K4y30'''，之后cjb上机敲板子，yzc上机'''A1y51'''，sub上机写I，cjb想到了C，上机C，'''C1y97'''。sub I wa了之后开始拍，'''I4y130'''。cjb苦思G题无果，然后在板子上找到了….于是cjb上机，花了很多时间，'''G1y165'''。期间yzc和sub讨论清楚了E，开始上机写E，cjb想F，sub推B，一个小时过去了，yzc wa了2发之后下来查，sub上机try B，感觉收敛十分垃圾没有什么救，20min过去了，yzc表示自己找到了1个错，fix了之后'''E3y251'''。最后只好开始刚J，sub有了思路，写不完了，最后rk3，MIT 8题rk1，UW1 7题rk2。
== 总结 ==
=== chenjb ===
今天板子题old题太多了，抄到自闭，yzc的模拟题拿得很稳，最后sub没有能从B和J中出一个比较可惜，B的式子其实已经推对了没去试，J大概还需要20min左右。
=== oipotato ===
咕咕咕。(更新楼上关于subB式子推对了没去试的说法，其实sub直觉是对的，题解假了，不过感觉以后遇到这种情况不妨一试，毕竟不会花太多时间）
=== subconscious  ===
gtmcjb。
== 题解 ==
 * A：lct模板题

 * B：[[Image(formula1.jpg,400px)]] [[Image(formula2.jpg,400px)]]

 * C：manacher之后将询问[l,r]拆成[l,mid]和[mid,r]，这样他们的回文半径只会碰到左侧或者右侧，上数据结构维护即可。

 * D：

 * E：模拟。

 * F：

 * G：牛逼大分治，感谢Claris板子 [wiki:2017-team2-dynamicbridge 动态维护桥的个数]

 * H：动态维护平面上的点(x,y)，询问在[1,xi)范围内的y的中位数。树状数组套动态线段树维护，每次询问拿出log棵线段树，在线段树上二分。一次操作O(log^2^n)

 * I：取一个向量一定在边界上，发现可以把其他向量映射到平面上，转一圈即可。

 * J：打一枪分成四块，n^2^m^2^，每只兔子都会跑到顶角，dp时候统计期望和每个顶角兔子数量即可。

 * K：平衡树模板题

流水账

出门各自看题，A和K两个板子题出现了，cjb上机敲板子，然后让yzc上去补全，出了点偏差K4y30，之后cjb上机敲板子，yzc上机A1y51，sub上机写I，cjb想到了C，上机C，C1y97。sub I wa了之后开始拍，I4y130。cjb苦思G题无果，然后在板子上找到了….于是cjb上机，花了很多时间，G1y165。期间yzc和sub讨论清楚了E，开始上机写E，cjb想F，sub推B，一个小时过去了，yzc wa了2发之后下来查，sub上机try B，感觉收敛十分垃圾没有什么救，20min过去了，yzc表示自己找到了1个错，fix了之后E3y251。最后只好开始刚J，sub有了思路，写不完了，最后rk3，MIT 8题rk1，UW1 7题rk2。

总结

chenjb

今天板子题old题太多了，抄到自闭，yzc的模拟题拿得很稳，最后sub没有能从B和J中出一个比较可惜，B的式子其实已经推对了没去试，J大概还需要20min左右。

oipotato

咕咕咕。(更新楼上关于subB式子推对了没去试的说法，其实sub直觉是对的，题解假了，不过感觉以后遇到这种情况不妨一试，毕竟不会花太多时间）

subconscious

gtmcjb。

题解

  • A：lct模板题
  • B：
  • C：manacher之后将询问[l,r]拆成[l,mid]和[mid,r]，这样他们的回文半径只会碰到左侧或者右侧，上数据结构维护即可。
  • D：
  • E：模拟。
  • F：
  • G：牛逼大分治，感谢Claris板子 动态维护桥的个数
  • H：动态维护平面上的点(x,y)，询问在[1,xi)范围内的y的中位数。树状数组套动态线段树维护，每次询问拿出log棵线段树，在线段树上二分。一次操作O(log2n)
  • I：取一个向量一定在边界上，发现可以把其他向量映射到平面上，转一圈即可。
  • J：打一枪分成四块，n2m2，每只兔子都会跑到顶角，dp时候统计期望和每个顶角兔子数量即可。
  • K：平衡树模板题
附加文件