2017-Sp197-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb上机签E，发现和样例对不上，搁置。sub上机写K，tle了，调整了几次都没过。cjb和yzc开了好几个题，yzc先上机写D，'''D2y85'''。之后cjb上机写G，pe了之后很难受，sub帮忙看代码。yzc上机搞E，搞了好几发之后感觉原来题意可能是对的，改回去之后发现了corner case，'''E5y107'''。cjb发现自己退出条件写错了，'''G2y108'''，sub又上机重写K，又t了，加了卡时'''K6y136'''。yzc和sub搞F，发现之前做法假了，cjb就先上机抄L的KD树，yzc和sub继续研究F，之后重写之后'''F3y172'''。sub上机补了几个东西'''L1y189'''。之后cjb和yzc写C，wa了对拍，tle了之后把SA换成了SAM还是t，之后只能让sub先上机写A，sub wa了A之后cjb和yzc决定优化下遍历过程，'''C8y283'''。sub继续调A，'''A3y288'''，之后sub乱搞H没有通过。最后8题rk10，rk1是搞笑网友，9题，咖啡鸡rk2也是8题。今天dls、jls还有UW1、MSU1都没来。


== 总结 ==
=== chenjb ===
太久没有训练，再加上签到卡了题意，前面非常拖沓。树Dp和SAM遍历的这种小经验值得积累，sub今天完成拖后中场的任务完成得很好，不过K的小经验也值得总结。我自己犯了n==0&&m==0写成n==0 or m==0这种低级错误实在是太sb了...
=== oipotato ===
没啥想说的。
=== subconscious  ===
gtm精度。
== 题解 ==
 * A：去掉自己模拟得到序列，将没有出现在序列中的加到序列末尾，reverse序列就是你的操作序列。

 * B：yzc

 * C：在SAM上按字典序遍历，取出所有本质不同子串的位置和出现次数，过程中记录当前字母总量，离线处理询问。

 * D：f[l,r]表示以[l,r]子串作为当前最大值的方案数，二分+hash找到r+1之后最远匹配位置，维护前缀和即可。

 * E：用bitset存储临接表，暴力枚举即可，注意答案可能是两个相同数字，而且给定的矩阵似乎是上三角?

 * F：f[i][j]表示i这个子树最近一个棋子的距离是j，将f[i][j]和f[son][k]转移给f[i][min(j,k+1)] (j+1+k>=c)，两个都只枚举数值到深度大小。

 * G：Segment Tree Beats，线段树暴力维护最大最小值，如果可以整段修改就打覆盖标记即可。

 * H：cjb

 * I：'''出题人的NB暴搜'''

 * J：sub

 * K：枚举上下边界，二分答案可以nlogn，卡时用迭代可以过。

 * L：KD树模板题。

流水账

出门各自看题，cjb上机签E，发现和样例对不上，搁置。sub上机写K，tle了，调整了几次都没过。cjb和yzc开了好几个题，yzc先上机写D，D2y85。之后cjb上机写G，pe了之后很难受，sub帮忙看代码。yzc上机搞E，搞了好几发之后感觉原来题意可能是对的，改回去之后发现了corner case，E5y107。cjb发现自己退出条件写错了，G2y108，sub又上机重写K，又t了，加了卡时K6y136。yzc和sub搞F，发现之前做法假了，cjb就先上机抄L的KD树，yzc和sub继续研究F，之后重写之后F3y172。sub上机补了几个东西L1y189。之后cjb和yzc写C，wa了对拍，tle了之后把SA换成了SAM还是t，之后只能让sub先上机写A，sub wa了A之后cjb和yzc决定优化下遍历过程，C8y283。sub继续调A，A3y288，之后sub乱搞H没有通过。最后8题rk10，rk1是搞笑网友，9题，咖啡鸡rk2也是8题。今天dls、jls还有UW1、MSU1都没来。

总结

chenjb

太久没有训练，再加上签到卡了题意，前面非常拖沓。树Dp和SAM遍历的这种小经验值得积累，sub今天完成拖后中场的任务完成得很好，不过K的小经验也值得总结。我自己犯了n==0&&m==0写成n==0 or m==0这种低级错误实在是太sb了...

oipotato

没啥想说的。

subconscious

gtm精度。

题解

  • A：去掉自己模拟得到序列，将没有出现在序列中的加到序列末尾，reverse序列就是你的操作序列。
  • B：yzc
  • C：在SAM上按字典序遍历，取出所有本质不同子串的位置和出现次数，过程中记录当前字母总量，离线处理询问。
  • D：f[l,r]表示以[l,r]子串作为当前最大值的方案数，二分+hash找到r+1之后最远匹配位置，维护前缀和即可。
  • E：用bitset存储临接表，暴力枚举即可，注意答案可能是两个相同数字，而且给定的矩阵似乎是上三角?
  • F：f[i][j]表示i这个子树最近一个棋子的距离是j，将f[i][j]和f[son][k]转移给f[i][min(j,k+1)] (j+1+k>=c)，两个都只枚举数值到深度大小。
  • G：Segment Tree Beats，线段树暴力维护最大最小值，如果可以整段修改就打覆盖标记即可。
  • H：cjb
  • I：出题人的NB暴搜
  • J：sub
  • K：枚举上下边界，二分答案可以nlogn，卡时用迭代可以过。
  • L：KD树模板题。
附加文件