2017-Sp126-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场cjb读了A，以为是最签到的题，骗了yzc上去，yzc写啊写终于wa了。之后sub上机写G，又wa了。yzc找到了错误，'''A2y49'''，之后sub '''G2y50'''。cjb终于可以上机写真正的两道签到题了，然后cjb就猛wa F，冷静了一下把代码丢给yzc，继续一发'''B1y100'''，之后终于'''F3y110'''。sub上机写C，之后cjb上机试图乱搞K，wa了3发感觉没救了。sub继续写C，之后获得wa。cjb和yzc读了H后很有想法，讨论了很久，之后终于想到了对称性，sub wa了之后yzc上机写读入，cjb抄tarjan写topsort，之后莫名wa 1，找到了2B错误后'''H2y223'''。之后sub疯狂写C，终于想到了自己问题，'''C5y263'''。之后让sub上机rush E，一发'''E1y294'''。
== 总结 ==
=== chenjb ===
感觉这套题很牛逼，我们一度以为自己只能签到跑路了。另外以后tarjan缩点topsort的话直接rep(i,cnt,1)即可，感觉十分方便嘿嘿。自己写辣鸡签到题有点慢，要打打cf。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：模拟。

 * B：链表模拟。

 * C：答案只有1和2，假意farmland即可，注意图本质可以不连通。

 * D：计算所有情况减掉不严格凸的情况即可。注意答案需要long long。

 * E：区间dp，预处理每一个区间会不会掉下去。

 * F：模拟。

 * G：消元分类讨论即可，注意x确定就可以判断所有人，所以只需要判断一次。

 * H：建出2-sat模型，tarjan缩点，若a和a‘在同一个scc则no，否则若存在一个scc包含两个以上任性点则maybe，因为由对称性可知存在一种方案。再之后对于一个scc至多存在一个任性点，由对称性可知在dag上若a能到b且a和b都包含任性点，则存在一种方案，继续maybe。最后输出yes。

 * I：

 * J：yzc

 * K：乱搞方法应该有很多，这里介绍其中一种：我们设立阈值为8E12/n，只保留不超过阈值的边。为了优化枚举，考虑将平面分块，每块大小为2000*2000，分成大约500*500块，因为随机的原因可以视为均匀分布(大概每块里不超过10个点)，然后从每个点所在点的块一圈圈向外扩散出去找点就好了，如果该块显然整块的点都不太行就break。剩下就跑kruskal即可。本题关键还是在于这个阈值怎么设，但是枚举的姿势很重要，姿势正确了，阈值可以随意调整，似乎也可以用kd-tree或者分治来添加合适的边。
  * jsb科普的牛逼结论：对于欧几里得距离的平面图mst，每个点沿60度划一个象限(小于60度也是对的)，则只需要在每个象限里取最近的点。相似地，如果是曼哈顿距离，则是沿45度划一个象限。


 * [https://wiki.icpc.camp/deep-dark-fantasy/20170301 Deep Dark Fantasy]

流水账

开场cjb读了A，以为是最签到的题，骗了yzc上去，yzc写啊写终于wa了。之后sub上机写G，又wa了。yzc找到了错误，A2y49，之后sub G2y50。cjb终于可以上机写真正的两道签到题了，然后cjb就猛wa F，冷静了一下把代码丢给yzc，继续一发B1y100，之后终于F3y110。sub上机写C，之后cjb上机试图乱搞K，wa了3发感觉没救了。sub继续写C，之后获得wa。cjb和yzc读了H后很有想法，讨论了很久，之后终于想到了对称性，sub wa了之后yzc上机写读入，cjb抄tarjan写topsort，之后莫名wa 1，找到了2B错误后H2y223。之后sub疯狂写C，终于想到了自己问题，C5y263。之后让sub上机rush E，一发E1y294。

总结

chenjb

感觉这套题很牛逼，我们一度以为自己只能签到跑路了。另外以后tarjan缩点topsort的话直接rep(i,cnt,1)即可，感觉十分方便嘿嘿。自己写辣鸡签到题有点慢，要打打cf。

oipotato

subconscious

题解

  • A：模拟。
  • B：链表模拟。
  • C：答案只有1和2，假意farmland即可，注意图本质可以不连通。
  • D：计算所有情况减掉不严格凸的情况即可。注意答案需要long long。
  • E：区间dp，预处理每一个区间会不会掉下去。
  • F：模拟。
  • G：消元分类讨论即可，注意x确定就可以判断所有人，所以只需要判断一次。
  • H：建出2-sat模型，tarjan缩点，若a和a‘在同一个scc则no，否则若存在一个scc包含两个以上任性点则maybe，因为由对称性可知存在一种方案。再之后对于一个scc至多存在一个任性点，由对称性可知在dag上若a能到b且a和b都包含任性点，则存在一种方案，继续maybe。最后输出yes。
  • I：
  • J：yzc
  • K：乱搞方法应该有很多，这里介绍其中一种：我们设立阈值为8E12/n，只保留不超过阈值的边。为了优化枚举，考虑将平面分块，每块大小为2000*2000，分成大约500*500块，因为随机的原因可以视为均匀分布(大概每块里不超过10个点)，然后从每个点所在点的块一圈圈向外扩散出去找点就好了，如果该块显然整块的点都不太行就break。剩下就跑kruskal即可。本题关键还是在于这个阈值怎么设，但是枚举的姿势很重要，姿势正确了，阈值可以随意调整，似乎也可以用kd-tree或者分治来添加合适的边。
    • jsb科普的牛逼结论：对于欧几里得距离的平面图mst，每个点沿60度划一个象限(小于60度也是对的)，则只需要在每个象限里取最近的点。相似地，如果是曼哈顿距离，则是沿45度划一个象限。
  • Deep Dark Fantasy
附加文件