2017-Sp175-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门sub表示会做J，上机wa了，cjb和yzc讨论了一下A，yzc上机也wa了，之后cjb读了真签到题G，让yzc上了一下'''G1y29'''，之后拍了下A，'''A1y41'''，之前cjb读了C，让sub准备了一下，'''C1y54'''，sub此前也想好了J，'''J1y68'''。cjb开出了I，'''I1y77'''。yzc和sub在cjb写I的时候搞出了D。cjb上机搞定点分治和FFT，sub和yzc继续讨论B，之后yzc上机写B，cjb检查代码，'''B1y113'''。之后sub上机写D，cjb和yzc误会了题意试了一下E获得wa，之后sub '''D1y154'''。cjb此前就提出了F关于偶数的构造，在sub的带领下打表找到构造方法，'''F1y195'''，之后一起讨论E，yzc上机写E，不时和sub讨论细节。sub独自想H的细节，之后'''E1y270'''，sub上机rush H，获得wa，发现题意有点偏差。
== 总结 ==
=== chenjb ===
Dreamoon真牛逼，AK大失败，gtmwoodcube。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：二分答案，然后把<=x的标记为0，反之为1，线段树模拟然后看中位数是否为0。

 * B：题意给出的关系可得到严格偏序，sort之后贪心得到答案。

 * C：从x0枚举到x1，每次判定与竖线的交点，大力for这一竖线所有矩形。

 * D：式子为n!*sigma(1/i..j的点数)(I range in[1..n],j range in[1..n]，点分治后FFT合并得到每种长度路径的条数。

 * E：考虑分治，对区间左一半维护以原来id为下标，P递减的序列，同时将序列中存在的元素丢进以P为下标的线段树中，对于右一半，考虑以插入的元素中id在你之前的最大的P，记为x，则可以转移给你的P的取值范围为(x,当前的P)。

 * F：偶数的时候前一半的位置和自己+n/2匹配，奇数的时候有一半的边是i和i+n/2，另一半是i和i+n/2+1，其中前一半的边多一条，故删去最小的一条，然后从删去的边的一端遍历即可。

 * G：用堆维护。

 * H：旋转扫描线即可，边的端点插入事件，在点上插入特殊事件，边视为开区间比较好写，无需考虑穿过原点的情况。注意题意。

 * I：从叶子往上贪心，维护每个子树留下1/2的点未匹配的返回值，贪心两两结合即可。

 * J：优化式子，最后变成求s[i]-s[j]<=k的情况下，max(j-2*s[j]-(i-2*s[I]))，单调队列扫一遍。

流水账

出门sub表示会做J，上机wa了，cjb和yzc讨论了一下A，yzc上机也wa了，之后cjb读了真签到题G，让yzc上了一下G1y29，之后拍了下A，A1y41，之前cjb读了C，让sub准备了一下，C1y54，sub此前也想好了J，J1y68。cjb开出了I，I1y77。yzc和sub在cjb写I的时候搞出了D。cjb上机搞定点分治和FFT，sub和yzc继续讨论B，之后yzc上机写B，cjb检查代码，B1y113。之后sub上机写D，cjb和yzc误会了题意试了一下E获得wa，之后sub D1y154。cjb此前就提出了F关于偶数的构造，在sub的带领下打表找到构造方法，F1y195，之后一起讨论E，yzc上机写E，不时和sub讨论细节。sub独自想H的细节，之后E1y270，sub上机rush H，获得wa，发现题意有点偏差。

总结

chenjb

Dreamoon真牛逼，AK大失败，gtmwoodcube。

oipotato

subconscious

题解

• A：二分答案，然后把<=x的标记为0，反之为1，线段树模拟然后看中位数是否为0。
• B：题意给出的关系可得到严格偏序，sort之后贪心得到答案。
• C：从x0枚举到x1，每次判定与竖线的交点，大力for这一竖线所有矩形。
• D：式子为n!*sigma(1/i..j的点数)(I range in[1..n],j range in[1..n]，点分治后FFT合并得到每种长度路径的条数。
• E：考虑分治，对区间左一半维护以原来id为下标，P递减的序列，同时将序列中存在的元素丢进以P为下标的线段树中，对于右一半，考虑以插入的元素中id在你之前的最大的P，记为x，则可以转移给你的P的取值范围为(x,当前的P)。
• F：偶数的时候前一半的位置和自己+n/2匹配，奇数的时候有一半的边是i和i+n/2，另一半是i和i+n/2+1，其中前一半的边多一条，故删去最小的一条，然后从删去的边的一端遍历即可。
• G：用堆维护。
• H：旋转扫描线即可，边的端点插入事件，在点上插入特殊事件，边视为开区间比较好写，无需考虑穿过原点的情况。注意题意。
• I：从叶子往上贪心，维护每个子树留下1/2的点未匹配的返回值，贪心两两结合即可。
• J：优化式子，最后变成求s[i]-s[j]<=k的情况下，max(j-2*s[j]-(i-2*s[I]))，单调队列扫一遍。

附加文件

• 1.png by chenjb