2020-team0x06-0020

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team0x06 返回]

[[Image(Standings.png, 1000px)]][[BR]][[Image(Submissions.png, 600px)]]

== 概述 ==

== 流水账 ==

开场各自看题，没发现有签到。lmh看见积分题，拿笔开始算。fx看到榜上dls过了B，开始看。czyh读了I，上机打表。fx拉过lmh讨论B，czyh在OEIS上找不到什么有用的信息，胡了个结论但是WA了。fx跟lmh讨论了几种情况，上机写B。czyh弃I读其他题，lmh继续对着抛物线画画。fx写完B，交上去WA了，换lmh写D。lmh抄了个simpson积分，测了测发现很有规律，于是'''D1Y126'''。

czyh上机对着F先写暴力，lmh帮fx查代码，查出了若干小错误，但改完还是WA。czyh的暴力T飞了，lmh让他加个记忆化，于是'''F2Y168'''。fx上机写dmk，发现了少讨论的case并改对，'''B4Y205'''。期间czyh捡起I，握着lucas开始大力推柿子，'''I3Y216'''。

三人看C，lmh猜了个结论，fx推出了柿子，czyh上机。写完提交WA了，lmh一看用的是double，吸取经验教训让他改成int128。改完还是WA，lmh查了查代码，发现czyh竟然没有习惯性地写上define int ll，果然查到了爆int的地方，于是'''C3Y263'''。三个人尝试在线学差值，弄了份板子但看不懂，lmh大力改了改，但比赛已经结束了。

赛后30min，lmh过了H。

== 总结 ==

=== ntwbvdbl_oe ===

=== Orange_User ===

=== functionendless ===
这个人很懒,什么都没有留下...
== 题解 ==

A: 

B: 1. 线段树扫描线blahblah反正没听懂. 2. 虚树,超级方便的做法,但fx太菜忘掉了. 3. RMQLCA+模拟.核心是求出一个点到一个点集的最深LCA,分四种情况讨论即可,同时删和加可对称操作. 

C: step1. 对于给定的度数序列,答案与树的形态无关. step2. 考虑切每个点连出去的每条边,得到每个点对答案的贡献,推一推发现不确定点之间线性等价,然后直接平均标号做即可

D: 先求出方程的4个根，根据对称性求出2个，牛顿迭代求出一个，韦达定理再求出一个，在用4个根将区域分成3块，分别跑simpson积分，求出来发现答案是4n-(1/3)

E:

F:

G: 参见jsb题解，注意求gcd时去负号，要手写hash才能过，推荐mod=9999991

H: 能插值出来的多项式是唯一的，抄板子

I:

J:

[/wiki/2020-team0x06 返回]


概述

流水账

开场各自看题，没发现有签到。lmh看见积分题，拿笔开始算。fx看到榜上dls过了B，开始看。czyh读了I，上机打表。fx拉过lmh讨论B，czyh在OEIS上找不到什么有用的信息，胡了个结论但是WA了。fx跟lmh讨论了几种情况，上机写B。czyh弃I读其他题，lmh继续对着抛物线画画。fx写完B，交上去WA了，换lmh写D。lmh抄了个simpson积分，测了测发现很有规律，于是D1Y126。

czyh上机对着F先写暴力，lmh帮fx查代码，查出了若干小错误，但改完还是WA。czyh的暴力T飞了，lmh让他加个记忆化，于是F2Y168。fx上机写dmk，发现了少讨论的case并改对，B4Y205。期间czyh捡起I，握着lucas开始大力推柿子，I3Y216。

三人看C，lmh猜了个结论，fx推出了柿子，czyh上机。写完提交WA了，lmh一看用的是double，吸取经验教训让他改成int128。改完还是WA，lmh查了查代码，发现czyh竟然没有习惯性地写上define int ll，果然查到了爆int的地方，于是C3Y263。三个人尝试在线学差值，弄了份板子但看不懂，lmh大力改了改，但比赛已经结束了。

赛后30min，lmh过了H。

总结

ntwbvdbl_oe

Orange_User

functionendless

这个人很懒,什么都没有留下...

题解

A:

B: 1. 线段树扫描线blahblah反正没听懂. 2. 虚树,超级方便的做法,但fx太菜忘掉了. 3. RMQLCA+模拟.核心是求出一个点到一个点集的最深LCA,分四种情况讨论即可,同时删和加可对称操作.

C: step1. 对于给定的度数序列,答案与树的形态无关. step2. 考虑切每个点连出去的每条边,得到每个点对答案的贡献,推一推发现不确定点之间线性等价,然后直接平均标号做即可

D: 先求出方程的4个根，根据对称性求出2个，牛顿迭代求出一个，韦达定理再求出一个，在用4个根将区域分成3块，分别跑simpson积分，求出来发现答案是4n-(1/3)

E:

F:

G: 参见jsb题解，注意求gcd时去负号，要手写hash才能过，推荐mod=9999991

H: 能插值出来的多项式是唯一的，抄板子

I:

J:

附加文件