2021-team8-0208

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Standings.png,1000px)]]
[[Image(Submissions.png,1000px)]]
== 流水账 ==

开场Szy签了D，zhw会了A，cy写，但是Wa了，随后zhw和szy讨论，出了L，zhw上机过了L，zhw和szy秒了F，zhw上机出了F，szy机下想C，推了推式子，会了C，但是cyA调不出来，szy，C一开始Wa了，后来发现有个地方没排序，排序后过了，cy表示会了I，但是A仍然调不出来，szy让cy上机先写I，szy和zhw调cy的A，cy很快过了I，A看了1h，zhw发现离散化有个地方有问题，改完过了，随后zhw开出了G，cy上机，szy也开出了E，但是最终G没有写出来。

== 个人总结 ==

Szy:交之前先检查一遍，少犯低级错误，送罚时。

== 题解 ==

A:扫描线

B:

C:考虑每条路径必然从最容易坏的开始考虑，设di为第i调路径开始检查的期望花费,ai为这条路径的畅通概率，则可以证明，设pi=di/ai，按pi从小到大检查最优，证明可以考虑如果交换相邻两个。

D:签到题

E:设一个点的控制点表示这个点是被控制节点的最远点，每个点控制的点都是一个区间，加入点可以直接二分控制区间，删除某一点，则被其控制的点必然被其左右两点控制，修改一下控制区间即可。

F:状压DP

G:先随便找一颗生成树，LCT维护，然后对于每个点强行把相邻的边往里加，计算树边权值和

H:

I:考虑贡献的增量为2x+1，用lct维护sam，链+和链求和即可，注意边上不止一个字符

J:

K:

L:i次变换之后每个位置的值是ax^a(x+2^i)^a(x+2*2^i)....^a(x+(k-1)*2^i),考虑每次+2^i会形成若干个环，每个点的值是环上连续一段，对每个环处理一下前缀和和即可。

流水账

开场Szy签了D，zhw会了A，cy写，但是Wa了，随后zhw和szy讨论，出了L，zhw上机过了L，zhw和szy秒了F，zhw上机出了F，szy机下想C，推了推式子，会了C，但是cyA调不出来，szy，C一开始Wa了，后来发现有个地方没排序，排序后过了，cy表示会了I，但是A仍然调不出来，szy让cy上机先写I，szy和zhw调cy的A，cy很快过了I，A看了1h，zhw发现离散化有个地方有问题，改完过了，随后zhw开出了G，cy上机，szy也开出了E，但是最终G没有写出来。

个人总结

Szy:交之前先检查一遍，少犯低级错误，送罚时。

题解

A:扫描线

B:

C:考虑每条路径必然从最容易坏的开始考虑，设di为第i调路径开始检查的期望花费,ai为这条路径的畅通概率，则可以证明，设pi=di/ai，按pi从小到大检查最优，证明可以考虑如果交换相邻两个。

D:签到题

E:设一个点的控制点表示这个点是被控制节点的最远点，每个点控制的点都是一个区间，加入点可以直接二分控制区间，删除某一点，则被其控制的点必然被其左右两点控制，修改一下控制区间即可。

F:状压DP

G:先随便找一颗生成树，LCT维护，然后对于每个点强行把相邻的边往里加，计算树边权值和

H:

I:考虑贡献的增量为2x+1，用lct维护sam，链+和链求和即可，注意边上不止一个字符

J:

K:

L:i次变换之后每个位置的值是axa(x+2i)a(x+2*2i)....a(x+(k-1)*2i),考虑每次+2^i会形成若干个环，每个点的值是环上连续一段，对每个环处理一下前缀和和即可。

附加文件