Contest-Petrozavodsk

从 Trac 迁移的文章

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

原文章内容如下：

[https://codeforces.com/gym/101954 contest]

[wiki:Contest_Information&&Solution go back]
== Summary ==

一套非常好的题目。题目质量很高，并且有一定的思维难度。

需要稳稳的把前中期打好。特别是算法显然的题目。

适合队伍中期（建队20场比赛以后）磨合和提升

== 题解 ==
'''legilimens'''
runespoor补充

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

 * B：求出每对点2*2共4种状态相交时间，二分答案用2-sat判定。（注意线段重合的特判）

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

 * D：

 * E：

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

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

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

 * I：将读入的点构成虚树，每次加入一条链的过程中，把这条链上的所有重链端点拿出来，另外维护树链剖分序的主席树，在主席树上求值。（其实维护一个树上主席树就好了。在虚树上把每个点到根的链的贡献统计一下（就是1 - 儿子个数），然后在主席树上二分就好。O(nlogn)）

 * J：

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

contest

go back

Summary

一套非常好的题目。题目质量很高，并且有一定的思维难度。

需要稳稳的把前中期打好。特别是算法显然的题目。

适合队伍中期（建队20场比赛以后）磨合和提升

题解

legilimens

runespoor补充

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