2017-Sp231-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
== 总结 ==
=== chenjb ===
今天这个A主要责任在我这里，下标用反了，然后还用重了。不过总体来说完成度还是不错的，如果一切顺利，应该还有40分钟左右的空闲才对。yzc的I虽然很棒，但是还是有无效时间，还是需要想好先。自己再一次对于能写的题估计悲观，我的H和sub的C都是15min能搞定的题目，与其背着罚时想签A，还是应该更果断地弃掉才对(虽然今天确实弃掉了，比赛都过半了...)。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：按照球坐标排序，同向量按时间顺序模拟。

 * B：求出每对点2*2共4种状态相交时间，二分答案用2-sat判定。

 * C：注意到偶数时答案是对半分的，如果是奇数，需要特判奇数那一位是什么，即所有维的值的bit的异或和，dp+高精度即可。

 * D：

 * E：cjb

 * F：按度数分成大小点，维护大点周围颜色情况，小点直接做。

 * G：环不是很长，模拟即可。

 * H：在dag上直接暴力dp，f[i][j][k]表示i这个点出发，有j个大，k个小的最优解，直接转移是正确的。

 * I：将读入的点构成虚树，每次加入一条链的过程中，把这条链上的所有重链端点拿出来，另外维护树链剖分序的主席树，在主席树上求值。

 * J：sub

 * K：逐位确定，从高位每次写一个1，对答案贡献是之前位1的数量+之后0的数量/2，放置在当前位上，因此快速比较，直接nlogn即可。

流水账

总结

chenjb

今天这个A主要责任在我这里，下标用反了，然后还用重了。不过总体来说完成度还是不错的，如果一切顺利，应该还有40分钟左右的空闲才对。yzc的I虽然很棒，但是还是有无效时间，还是需要想好先。自己再一次对于能写的题估计悲观，我的H和sub的C都是15min能搞定的题目，与其背着罚时想签A，还是应该更果断地弃掉才对(虽然今天确实弃掉了，比赛都过半了...)。

oipotato

subconscious

题解

  • A：按照球坐标排序，同向量按时间顺序模拟。
  • B：求出每对点2*2共4种状态相交时间，二分答案用2-sat判定。
  • C：注意到偶数时答案是对半分的，如果是奇数，需要特判奇数那一位是什么，即所有维的值的bit的异或和，dp+高精度即可。
  • D：
  • E：cjb
  • F：按度数分成大小点，维护大点周围颜色情况，小点直接做。
  • G：环不是很长，模拟即可。
  • H：在dag上直接暴力dp，f[i][j][k]表示i这个点出发，有j个大，k个小的最优解，直接转移是正确的。
  • I：将读入的点构成虚树，每次加入一条链的过程中，把这条链上的所有重链端点拿出来，另外维护树链剖分序的主席树，在主席树上求值。
  • J：sub
  • K：逐位确定，从高位每次写一个1，对答案贡献是之前位1的数量+之后0的数量/2，放置在当前位上，因此快速比较，直接nlogn即可。
附加文件