Contest-Petrozavodsk-Camp-2013-1

从 Trac 迁移的文章

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

原文章内容如下：

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

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

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

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

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

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

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

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

 * D：

 * E：by zqq (口胡）：直接看中间的字符：如果n为奇数，直接删去递归。n为偶数，可能出现长度为n / 2的前后缀相等，那么判断一下可能性，再减去不合法情况（在最大长度的不合法处减去，则不会多算）。重叠不用考虑，因为一定有更小长度的不合法情况。这里只考虑长度<= n / 2的前后缀。复杂度O(N^2^)不要被n为200骗了！其实不难

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

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

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

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

 * J：相当于分治排序的方法，在每一层进行nth_element,在分治排序。这样显然也可以O(nlogn)排序。这里我们需要用reverse操作实现它。我们可以用另一个函数模拟这个过程。操作次数O(nlogn),时间复杂度O(nlog^2^n),因为暴力reverse了相应的区间。'''主要难想的部分用nth_element也可以排序'''

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

go back

Summary

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

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

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

题解

legilimens

runespoor补充

  • A：按照球坐标排序，同向量按时间顺序模拟。
  • B：求出每对点2*2共4种状态相交时间，二分答案用2-sat判定。（注意线段重合的特判）
  • C：注意到偶数时答案是对半分的，如果是奇数，需要特判奇数那一位是什么，即所有维的值的bit的异或和，dp+高精度即可。
  • D：
  • E：by zqq (口胡）：直接看中间的字符：如果n为奇数，直接删去递归。n为偶数，可能出现长度为n / 2的前后缀相等，那么判断一下可能性，再减去不合法情况（在最大长度的不合法处减去，则不会多算）。重叠不用考虑，因为一定有更小长度的不合法情况。这里只考虑长度<= n / 2的前后缀。复杂度O(N2)不要被n为200骗了！其实不难
  • F：按度数分成大小点，维护大点周围颜色情况，小点直接做。
  • G：循环节不是很长，模拟即可。
  • H：在dag上直接暴力dp，f[i][j][k]表示i这个点出发，有j个大，k个小的最优解，直接转移是正确的。
  • I：将读入的点构成虚树，每次加入一条链的过程中，把这条链上的所有重链端点拿出来，另外维护树链剖分序的主席树，在主席树上求值。（其实维护一个树上主席树就好了。在虚树上把每个点到根的链的贡献统计一下（就是1 - 儿子个数），然后在主席树上二分就好。O(nlogn)）
  • J：相当于分治排序的方法，在每一层进行nth_element,在分治排序。这样显然也可以O(nlogn)排序。这里我们需要用reverse操作实现它。我们可以用另一个函数模拟这个过程。操作次数O(nlogn),时间复杂度O(nlog2n),因为暴力reverse了相应的区间。主要难想的部分用nth_element也可以排序
  • K：逐位确定，从高位每次写一个1，对答案贡献是之前位1的数量+之后0的数量/2，放置在当前位上，因此快速比较，直接nlogn即可。
附加文件