2017-Sp198-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，大家都在刚J，罚时疯狂上升。MIPT过了K之后让sub去搞K，cjb和yzc搞E，之后sub上机tle，yzc上机写讨论出来的一个假算法，之后发现假了。sub想好怎么优化K，'''K2y78'''。sub下机帮忙证明了E的新做法复杂度是正确的，'''E2y133'''。sub期间开始搞J，先让cjb抄了个PollardRho，然后tle了，此前解决了G的复杂度问题，所以只要有空就让yzc上机写G，之后sub想好了J，上机'''J2y212'''。yzc继续写G，sub推D的积分，cjb翻了个积分表，一切似乎都很美好。之后sub '''D1y267'''，yzc继续写G，发现少了一维状态，最后讨论B，似乎得到了一点思路，4题收尾，全场rk7，敦老师6题rk1，2-6名都是5题，分别是学军、MIT、MIPT、UW和搞笑网友。

== 总结 ==
=== chenjb ===
今天非常偏数学和几何，而且很多题都比较臃肿，要输出方案。我们今天罚时还算可以，主要是没有出门就上去扑J，比较谨慎(当然也是sub表现不错)，最后B题可能也差不多(?)，花了大力气去写G的这个操作存在一些争议，但是也问题不大。
=== oipotato ===
没有。
=== subconscious  ===
不知道。
== 题解 ==
 * A：

 * B：物体当成方块，按高度排序，一定存在中间的长度为一半的区间，使得面积也是一半，二分即可。

 * C：在周长上每次找到非法点删掉，直到合法，可以简单地把删掉的点依次加回去。

 * D：每条边都独立，作垂线将边拆成两个直角三角形，积分是secθ，直接计算即可。

 * E：所有串插入trie树，按照trie的dfs序做dp，f[i][j]表示前i个分成j份的方案数，j可以转移给i当且仅当j+1到i的lca不是j或i+1的祖先，转移的系数是从lca往上有多少个满足条件的点，因为转移只会发生在分叉点，所以只有n次转移。

 * F：

 * G：

 * H：固定原点，可以确定其他10个点的可能位置（55*约10个左右？），预处理两两间的距离是否存在，删除一定不可能的点，shuffle一下暴力枚举即可。

 * I：

 * J：1e6内质因子直接分解，剩下的只有可能是p*(p-1)的因子，枚举倍数可在1000内求得p，随后直接枚举答案包含哪些质因子即可。

 * K：取反，两种情况，只经过一条边的答案是内部点数*外部点数，经过两条边的情况要枚举线和只有单点的一侧，然后枚举统计，bitset优化。

流水账

出门各自看题，大家都在刚J，罚时疯狂上升。MIPT过了K之后让sub去搞K，cjb和yzc搞E，之后sub上机tle，yzc上机写讨论出来的一个假算法，之后发现假了。sub想好怎么优化K，K2y78。sub下机帮忙证明了E的新做法复杂度是正确的，E2y133。sub期间开始搞J，先让cjb抄了个PollardRho，然后tle了，此前解决了G的复杂度问题，所以只要有空就让yzc上机写G，之后sub想好了J，上机J2y212。yzc继续写G，sub推D的积分，cjb翻了个积分表，一切似乎都很美好。之后sub D1y267，yzc继续写G，发现少了一维状态，最后讨论B，似乎得到了一点思路，4题收尾，全场rk7，敦老师6题rk1，2-6名都是5题，分别是学军、MIT、MIPT、UW和搞笑网友。

总结

chenjb

今天非常偏数学和几何，而且很多题都比较臃肿，要输出方案。我们今天罚时还算可以，主要是没有出门就上去扑J，比较谨慎(当然也是sub表现不错)，最后B题可能也差不多(?)，花了大力气去写G的这个操作存在一些争议，但是也问题不大。

oipotato

没有。

subconscious

不知道。

题解

  • A：
  • B：物体当成方块，按高度排序，一定存在中间的长度为一半的区间，使得面积也是一半，二分即可。
  • C：在周长上每次找到非法点删掉，直到合法，可以简单地把删掉的点依次加回去。
  • D：每条边都独立，作垂线将边拆成两个直角三角形，积分是secθ，直接计算即可。
  • E：所有串插入trie树，按照trie的dfs序做dp，f[i][j]表示前i个分成j份的方案数，j可以转移给i当且仅当j+1到i的lca不是j或i+1的祖先，转移的系数是从lca往上有多少个满足条件的点，因为转移只会发生在分叉点，所以只有n次转移。
  • F：
  • G：
  • H：固定原点，可以确定其他10个点的可能位置（55*约10个左右？），预处理两两间的距离是否存在，删除一定不可能的点，shuffle一下暴力枚举即可。
  • I：
  • J：1e6内质因子直接分解，剩下的只有可能是p*(p-1)的因子，枚举倍数可在1000内求得p，随后直接枚举答案包含哪些质因子即可。
  • K：取反，两种情况，只经过一条边的答案是内部点数*外部点数，经过两条边的情况要枚举线和只有单点的一侧，然后枚举统计，bitset优化。
附加文件