2017-Sp292-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
=== chenjb ===
主要死在这个J上了，还是缺乏直觉啊。。。如果能敏锐地感受到n大的时候一定有解就好了。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：用map模拟。

 * B：

 * C：模拟

 * D：每次由于可以消掉一半，可以手写bitset，复杂度降到n^2^/64。

 * E：

 * F：全部并到一起，可以用剩余的k-1个栈做桶排，复杂度是log(n)/log(k)。

 * G：

 * H：

 * I：把数字按照字典序排序，bfs构造即可。

 * J：显然有一个贪心检查是否合法。当n小于阈值时暴力状压，否则一定能构造解，可暴力枚举前两个人，然后每次贪心取能抬高最多的人来构造。阈值取到20，或者考虑：先把字符串编成数字1~m，然后一开始pos=0，每次对每个集合，求最小的＞pos的，然后所有集合取最大的，更新pos,第i轮pos至少加n-i+1，然后就是n+(n-1)+...+1(阈值取26)

 * K：

流水账

chenjb

主要死在这个J上了，还是缺乏直觉啊。。。如果能敏锐地感受到n大的时候一定有解就好了。

oipotato

subconscious

题解

  • A：用map模拟。
  • B：
  • C：模拟
  • D：每次由于可以消掉一半，可以手写bitset，复杂度降到n2/64。
  • E：
  • F：全部并到一起，可以用剩余的k-1个栈做桶排，复杂度是log(n)/log(k)。
  • G：
  • H：
  • I：把数字按照字典序排序，bfs构造即可。
  • J：显然有一个贪心检查是否合法。当n小于阈值时暴力状压，否则一定能构造解，可暴力枚举前两个人，然后每次贪心取能抬高最多的人来构造。阈值取到20，或者考虑：先把字符串编成数字1~m，然后一开始pos=0，每次对每个集合，求最小的＞pos的，然后所有集合取最大的，更新pos,第i轮pos至少加n-i+1，然后就是n+(n-1)+...+1(阈值取26)
  • K：
附加文件