2021-team8-0307

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Standings.png,1000px)]]

== 流水账 ==

开场szy签到A，zhw看M，cy看E。结果zhw发现大部分M都T了，于是否决了自己的n^2logn的做法。因为忘看了i<j<k的条件，于是想了一个假的单调写法，后来才发现问题，szy提了一个大力模数Hash的想法然后过了。cy也写出了E过了。后来szy去开I，zhw开了J，都过了，szy和cy一起写B，zhw去写K的模拟题，结果因为细节错误wa了三次。后来szy想出了L的解法让cy上机写，zhw想出了D的解法并和szy一起写出了D


== 个人总结 ==

Szy:

cy:

zhw:签到题还是签到不够熟练

== 题解 ==

A:签到

B:

C:

D:设f[i]表示枚举任意一个断点，长度为i的概率，考虑重复情况，有一个结论就是会有多个断点的一定是由多个双回文串重复组成的，那么考虑g[i]表示长度为i的不能由多个回文串分割的情况，那么就不会重复计算，g[i]=f[i]-sigma j|i g[j]

E:签到

F:

G:

H:暴力枚举，复杂度nlognlogn

I:固定45°角的平面，两边往中间推，直到碰到柱子为止

J:考虑i->j有没有直接连边，如果没有，那么全部是间接到达，i->k->j,枚举k，看sum p[k][j]的末尾是不是等于p[i][j]

K:模拟题

流水账

开场szy签到A，zhw看M，cy看E。结果zhw发现大部分M都T了，于是否决了自己的n^2logn的做法。因为忘看了i

个人总结

Szy:

cy:

zhw:签到题还是签到不够熟练

题解

A:签到

B:

C:

D:设f[i]表示枚举任意一个断点，长度为i的概率，考虑重复情况，有一个结论就是会有多个断点的一定是由多个双回文串重复组成的，那么考虑g[i]表示长度为i的不能由多个回文串分割的情况，那么就不会重复计算，g[i]=f[i]-sigma j|i g[j]

E:签到

F:

G:

H:暴力枚举，复杂度nlognlogn

I:固定45°角的平面，两边往中间推，直到碰到柱子为止

J:考虑i->j有没有直接连边，如果没有，那么全部是间接到达，i->k->j,枚举k，看sum p[k][j]的末尾是不是等于p[i][j]

K:模拟题

附加文件