2017-Sp254-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：要么是sqrt(2)*d，要么是下取整斜过来放，答案是下取整+1。

 * B：f[l][r][k]代表第l到第r串后k位满足偏序的方案数，打横过来dp，注意要用前缀和优化。

 * C：尽量取前面的点用过的点，但是在一个地方只能取一次，模拟。特判5个3和4个3一个2的情况(感觉是瞎jb搞过去的....)

 * D：对于一根横轴，两边本应跨过它的i和j，如果取掉之后，可以视为交换身份，所以按照从上往下逐次swap，然后从答案反推回去对应的位置即可，具体只需要实现一个函数求出从终点反推回去的起点即可。

 * E：'''牛逼构造？'''

 * F：最小值或者他的对面一定在答案里，只用3或4根，扫一遍取最小值即可。

 * G：对于每个点，一定需要存在一条线，分割开之前节点构成的凸包和之后节点构成的凸包，逐个判定。

 * H：可以证明，重心一定向着新加入的点移动，而且一定是移动到最后一个在加入这个点之前答案相等的点，这件事在虚树上只用移动一步，用树链剖分维护虚树上找儿子和找父亲的操作，注意细节。

 * I：'''牛逼计数?'''

 * J：假设每维都没有最大值，答案是s^d^，容斥，用dp处理方案数。

流水账

chenjb

oipotato

subconscious

题解

• A：要么是sqrt(2)*d，要么是下取整斜过来放，答案是下取整+1。
• B：f[l][r][k]代表第l到第r串后k位满足偏序的方案数，打横过来dp，注意要用前缀和优化。
• C：尽量取前面的点用过的点，但是在一个地方只能取一次，模拟。特判5个3和4个3一个2的情况(感觉是瞎jb搞过去的....)
• D：对于一根横轴，两边本应跨过它的i和j，如果取掉之后，可以视为交换身份，所以按照从上往下逐次swap，然后从答案反推回去对应的位置即可，具体只需要实现一个函数求出从终点反推回去的起点即可。
• E：牛逼构造？
• F：最小值或者他的对面一定在答案里，只用3或4根，扫一遍取最小值即可。
• G：对于每个点，一定需要存在一条线，分割开之前节点构成的凸包和之后节点构成的凸包，逐个判定。
• H：可以证明，重心一定向着新加入的点移动，而且一定是移动到最后一个在加入这个点之前答案相等的点，这件事在虚树上只用移动一步，用树链剖分维护虚树上找儿子和找父亲的操作，注意细节。
• I：牛逼计数?
• J：假设每维都没有最大值，答案是s^d，容斥，用dp处理方案数。

附加文件

• 1.png by chenjb