2017-Sp133-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，sub发现J是个很烦的但是算法明显的题目，cjb发现C是个简单lct，就和yzc交流了起来，之后上机抄lct。之后纷纷有人过A、D、E，sub上机写A，cjb上机写D，yzc上机写E，之后'''E2y44'''，'''D3y53'''，'''A1y73'''。之后cjb继续抄板子，yzc上机'''C1y95'''拿下一血，之后cjb和yzc反复讨论J题，sub此前被丢了个构造题G，上机'''G1y118'''，之后cjb上机写树链剖分，yzc上机写J，sub中间想好了F，上机'''F1y173'''，之后J终于写完，没清0 mle了一发之后'''J2y213'''，又拿下一血。最后sub刚B，1e18的题只能做到1e12，绝望交了几发。最后毛子榜上rk3，15年多校上rk2。
== 总结 ==
=== chenjb ===
今天还行，我和yzc配合很好，sub表现也很稳健。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：dp，f[i][j]代表i j之间的所有情况的结果和，转移的时候分类讨论三种符号，乘上一个组合数即可。

 * B：p,q都没有用。构造(()),()()两种模式串，可以取base^6i^，1<=i<=2500作为自由元，每次取最大的两个相减丢回堆直到出现差为零即可。感觉证明完全口胡。

 * C：显然每个数字只会和自己的约数连边，枚举每个数字的倍数来形成边表，从小到大加入点，lct维护答案。

 * D：显然每个函数的值域必须取满1到n，那么如果有k个不定的函数，则答案是(n!)^k-1^，注意如果没有不定函数要检查判定。

 * E：差分之后找到符合要求的区间，计算贡献即可。

 * F：递归进行查询，对于树并不大的部分记忆化即可。

 * G：两个边长都是偶数的时候要删掉一个(x,y)坐标和是奇数的位置，否则可以全部走到，简单构造方案即可。

 * H：显然好数只需要质因子从小到大均符合定义即可，由n是好数->xn是好数,1<=x<=2*n,可用log18个n与n+2的孪生好数来构造，每个的支配区间是n^2^+2到3n^2^。本题细节和常数令人窒息，目前火车上除了标程好像只有我过了。

 * I：

 * J：答案显然是总的和的平方减去去掉路径后每个连通块的和的平方，用树链剖分维护重链上挂着的轻子树的和的平方，在跳的过程中处理好跳轻链和重链操作即可。

 * [http://bestcoder.hdu.edu.cn/blog/2015-multi-university-training-contest-8-solutions-by-xudyh/ Official]

流水账

出门各自看题，sub发现J是个很烦的但是算法明显的题目，cjb发现C是个简单lct，就和yzc交流了起来，之后上机抄lct。之后纷纷有人过A、D、E，sub上机写A，cjb上机写D，yzc上机写E，之后E2y44，D3y53，A1y73。之后cjb继续抄板子，yzc上机C1y95拿下一血，之后cjb和yzc反复讨论J题，sub此前被丢了个构造题G，上机G1y118，之后cjb上机写树链剖分，yzc上机写J，sub中间想好了F，上机F1y173，之后J终于写完，没清0 mle了一发之后J2y213，又拿下一血。最后sub刚B，1e18的题只能做到1e12，绝望交了几发。最后毛子榜上rk3，15年多校上rk2。

总结

chenjb

今天还行，我和yzc配合很好，sub表现也很稳健。

oipotato

subconscious

题解

A：dp，f[i][j]代表i j之间的所有情况的结果和，转移的时候分类讨论三种符号，乘上一个组合数即可。
B：p,q都没有用。构造(()),()()两种模式串，可以取base⁶ⁱ，1<=i<=2500作为自由元，每次取最大的两个相减丢回堆直到出现差为零即可。感觉证明完全口胡。
C：显然每个数字只会和自己的约数连边，枚举每个数字的倍数来形成边表，从小到大加入点，lct维护答案。
D：显然每个函数的值域必须取满1到n，那么如果有k个不定的函数，则答案是(n!)^k-1，注意如果没有不定函数要检查判定。
E：差分之后找到符合要求的区间，计算贡献即可。
F：递归进行查询，对于树并不大的部分记忆化即可。
G：两个边长都是偶数的时候要删掉一个(x,y)坐标和是奇数的位置，否则可以全部走到，简单构造方案即可。
H：显然好数只需要质因子从小到大均符合定义即可，由n是好数->xn是好数,1<=x<=2*n,可用log18个n与n+2的孪生好数来构造，每个的支配区间是n²+2到3n²。本题细节和常数令人窒息，目前火车上除了标程好像只有我过了。
I：
J：答案显然是总的和的平方减去去掉路径后每个连通块的和的平方，用树链剖分维护重链上挂着的轻子树的和的平方，在跳的过程中处理好跳轻链和重链操作即可。
Official

附加文件

1.png by chenjb