2021-team8-0224

从 Trac 迁移的文章

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

原文章内容如下：

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

一开始签到题都过的挺迅速，除了C，后来szy和zhw一起把C的锅补了好久才过，期间szy出了E，cy上机写完了，最后cy A没调出来，zhw B差最后一个优化，szy应该想到的，状态没有调整好。

== 个人总结 ==

Szy:调整身体状态

cy:最后上机前犹豫太久，没来的及写完

zhw:

== 题解 ==

A:

B:f[x][y]表示x个位置用y种数字的方案数，考虑枚举最后一个不合法的位置t，这个位置上前缀max为m后缀min为m,f[x][y]=y^x-sigma(f[x-t][y-m]-f[x-t][y-m-1])*(m^t-(m-1)^t)，这样是n^4的，然后考虑枚举y,m，f[x]=sigma(f[x-t]*m^t)=m^x*simga(f[x-t]/m^(x-t)),然后就是n^3的了

C:f[x]表示最后一个数字是x的答案，f[x]=sigma(f[y](y<x))-sigma(f[x^y](x^y<y<x)，因为f[x^y]必然全都向f[y]贡献了，否则x^y^y>y，这样可以发现f[x^y]分log段。

D:f[x]表示最后一个是x最大的答案，对于每个i,f[x]只会从x之前第一个有2^i位的地方转移，证明考虑如果最高位为2^i,则如果不向第一个转移,则一定可以取两个第一位均为2^i，这样贡献可以达到2^(i+1)

E:按位考虑，每一位相当于有若干限制，1:L-R=1 2:L-R不全是1，考虑每一对L,R只能控制只被它覆盖的点，可以先暴力处理出不合法的第二类限制，然后删除第一类限制的时候查看一下有没有第二类限制跨过控制点。

F:

G:

H:

I:

J:

K:

L:

M:

N:建出笛卡尔树，从上往下dp，算出每个人要打到根需要多少能力值，然后往下算即可

流水账

一开始签到题都过的挺迅速，除了C，后来szy和zhw一起把C的锅补了好久才过，期间szy出了E，cy上机写完了，最后cy A没调出来，zhw B差最后一个优化，szy应该想到的，状态没有调整好。

个人总结

Szy:调整身体状态

cy:最后上机前犹豫太久，没来的及写完

zhw:

题解

A:

B:f[x][y]表示x个位置用y种数字的方案数，考虑枚举最后一个不合法的位置t，这个位置上前缀max为m后缀min为m,f[x][y]=yx-sigma(f[x-t][y-m]-f[x-t][y-m-1])*(mt-(m-1)t)，这样是n4的，然后考虑枚举y,m，f[x]=sigma(f[x-t]*mt)=mx*simga(f[x-t]/m(x-t)),然后就是n3的了

C:f[x]表示最后一个数字是x的答案，f[x]=sigma(f[y](yy](xyy]必然全都向f[y]贡献了，否则xyy>y，这样可以发现f[xy]分log段。

D:f[x]表示最后一个是x最大的答案，对于每个i,f[x]只会从x之前第一个有2i位的地方转移，证明考虑如果最高位为2i,则如果不向第一个转移,则一定可以取两个第一位均为2i，这样贡献可以达到2(i+1)

E:按位考虑，每一位相当于有若干限制，1:L-R=1 2:L-R不全是1，考虑每一对L,R只能控制只被它覆盖的点，可以先暴力处理出不合法的第二类限制，然后删除第一类限制的时候查看一下有没有第二类限制跨过控制点。

F:

G:

H:

I:

J:

K:

L:

M:

N:建出笛卡尔树，从上往下dp，算出每个人要打到根需要多少能力值，然后往下算即可

附加文件