2017-Sp269-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
出门cjb瞎jb搞了条链，J wa了，给了个假题意给yzc，又wa了，演技拉满。然后终于搞了个对的猜想，'''J2y64'''，然后帮sub抄了个费用流，'''A3y105'''。cjb开了E，丢给sub，sub上机'''E1y122'''。之后cjb丢了G科学做法给yzc，'''G3y146'''。sub很牛逼地推出了F，'''F1y170'''。之后开始搞B，tle成傻逼，一直卡到'''B15y296'''。
=== chenjb ===
感觉这个Btle得还是我们水平问题，long double和double之间使用还是要谨慎，另外就是大家怎么都看出来是二次函数了啊...不过好像早点过也没开出D，有时候分块维护，特别是维护操作序列，要多去考虑暴力重构这个思想。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：差分后费用流。

 * B：二分答案，枚举中心点在哪两个点之间，内部是三分，卡常。(实际上是二次函数，直接取，或者二分导数都可以)。

 * C：

 * D：把操作分块，称一块里会被修改的点为关键点，每块处理之前暴力重构一些信息，包括被/不被关键点支配的点的归属/值，还有关键点之间的关系等。修改操作暴力dfs整棵关键点子树，询问在每个关键点管辖的点集里二分。

 * E：对于每个点，先根据现有度数算出删去的边的奇偶，然后考虑异色边值为1，同色边值为0，可以对于每个点列出异或方程，高斯消元即可。

 * F：显然方差转换成平方和和方案数，然后最主要是要统计Σai^2^，这个每次额外贡献是(Σai)^2^*2n。

 * G：先询问出每种字母的个数，然后考虑每次取当前最小的两个串合并，合并的时候逐一找到每个字母的位置，插进去即可。

 * H：分类讨论。

 * I：

 * J：100个点的团，然后连出去一条100个点的链。

 * [https://icpc.camp/twsf/Petrozavodsk%20Winter-2015.%20Michael%20Tikhomirov%20Contest%201 TheWaySoFar]

 * [https://icpc.camp/new-meta/2017/3/22%20Petrozavodsk%20Winter-2015.%20Michael%20Tikhomirov%20Contest%201 NewMeta]

流水账

出门cjb瞎jb搞了条链，J wa了，给了个假题意给yzc，又wa了，演技拉满。然后终于搞了个对的猜想，J2y64，然后帮sub抄了个费用流，A3y105。cjb开了E，丢给sub，sub上机E1y122。之后cjb丢了G科学做法给yzc，G3y146。sub很牛逼地推出了F，F1y170。之后开始搞B，tle成傻逼，一直卡到B15y296。

chenjb

感觉这个Btle得还是我们水平问题，long double和double之间使用还是要谨慎，另外就是大家怎么都看出来是二次函数了啊...不过好像早点过也没开出D，有时候分块维护，特别是维护操作序列，要多去考虑暴力重构这个思想。

oipotato

subconscious

题解

• A：差分后费用流。
• B：二分答案，枚举中心点在哪两个点之间，内部是三分，卡常。(实际上是二次函数，直接取，或者二分导数都可以)。
• C：
• D：把操作分块，称一块里会被修改的点为关键点，每块处理之前暴力重构一些信息，包括被/不被关键点支配的点的归属/值，还有关键点之间的关系等。修改操作暴力dfs整棵关键点子树，询问在每个关键点管辖的点集里二分。
• E：对于每个点，先根据现有度数算出删去的边的奇偶，然后考虑异色边值为1，同色边值为0，可以对于每个点列出异或方程，高斯消元即可。
• F：显然方差转换成平方和和方案数，然后最主要是要统计Σai²，这个每次额外贡献是(Σai)²*2n。
• G：先询问出每种字母的个数，然后考虑每次取当前最小的两个串合并，合并的时候逐一找到每个字母的位置，插进去即可。
• H：分类讨论。
• I：
• J：100个点的团，然后连出去一条100个点的链。
• TheWaySoFar
• NewMeta

附加文件

• 1.png by chenjb