2017-Sp219-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
sub写C，'''C1y32'''。之后yzc写G，sub写E，cjb帮忙写了个线段树，'''E2y88'''，'''G2y89'''。之后cjb想D，yzc和sub想H，'''D2y146'''，'''H1y167'''。最后sub刚I，因为eps设大了，赛后1min过掉，没有成功提交最后一发。
== 总结 ==
=== chenjb ===
赛后1min过题好难受啊....eps咋回事儿啊，还有这个垃圾218为什么又不能交题了！
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：

 * B：

 * C：没有交答案是4，只有一组顶点交答案是inf，否则是3。

 * D：f[i][x][y]表示长度为i，a匹配到x，b匹配到y的方案数，暴力转移，用set维护等价的状态。

 * E：nlogn求出因子，算出dp范围，用线段树维护f[2][n]代表双方目前走到第i个点的方案数。

 * F：

 * G：把每个点拆成2个，两边各自按度数排序，所有边连的都是另一方的后缀，按序赋值。

 * H：先暴力枚举给定的解当中留下哪些人，留下的人必须是偏序的，然后不在方案中的每个点，一定在选中的点中有个分隔位置，使得分隔前的点都到它，分隔后的点都被它到达。我们只要在没被选中的点当中，选出一些点保证分隔点不递减即可。

 * I：用其他信息可以快速确定当前情况下最小平方和和最大平方和，实际平方和落在两者之间即存在解，枚举数量，逐位二分答案。

流水账

sub写C，C1y32。之后yzc写G，sub写E，cjb帮忙写了个线段树，E2y88，G2y89。之后cjb想D，yzc和sub想H，D2y146，H1y167。最后sub刚I，因为eps设大了，赛后1min过掉，没有成功提交最后一发。

总结

chenjb

赛后1min过题好难受啊....eps咋回事儿啊，还有这个垃圾218为什么又不能交题了！

oipotato

subconscious

题解

  • A：
  • B：
  • C：没有交答案是4，只有一组顶点交答案是inf，否则是3。
  • D：f[i][x][y]表示长度为i，a匹配到x，b匹配到y的方案数，暴力转移，用set维护等价的状态。
  • E：nlogn求出因子，算出dp范围，用线段树维护f[2][n]代表双方目前走到第i个点的方案数。
  • F：
  • G：把每个点拆成2个，两边各自按度数排序，所有边连的都是另一方的后缀，按序赋值。
  • H：先暴力枚举给定的解当中留下哪些人，留下的人必须是偏序的，然后不在方案中的每个点，一定在选中的点中有个分隔位置，使得分隔前的点都到它，分隔后的点都被它到达。我们只要在没被选中的点当中，选出一些点保证分隔点不递减即可。
  • I：用其他信息可以快速确定当前情况下最小平方和和最大平方和，实际平方和落在两者之间即存在解，枚举数量，逐位二分答案。
附加文件