2017-C02-team3
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(Screenshot from 2017-08-18 22-14-42.png)]]
= 流水账 =
今天Johann学长继续鸽，reku和lzw参加了比赛。
开场lzw过掉水题ABC，reku过掉水题G，然后reku和lzw讨论了一下水题D，提出了一个O(N*N*K)的做法，lzw感觉过不了，reku说一定可以过的，然后欣喜的过了。
之后二人开始讨论网络流题目J，lzw学长给出了费用只有X和X-1两种，reku想了个正确性不是很显然的网络流乱搞，想让lzw学长证一下，lzw学长还没证完，reku就写完了，意外的过了J。
前六题过得还算比较顺畅，六题之后我们是第二名，然后两人讨论了I和E都表示没什么思路。然后lzw学长思考了一下大模拟F，觉得还行，开始上机写F。
reku在lzw写F的时候，一直在撕纸玩，试图得出一些结论，然后感觉4、2和0是完全一样的，撕纸翻了翻，好像的确完全一样，于是感觉题目意义飘渺，难以理解。实际上是reku拓扑理论没有学过，智力也不够，动手能力还差导致的。
lzw很快过了样例，然后交了一发，wa了。两人debug好久，感觉可能要用到高精度，后来又感觉这种大模拟还要高精度，出题人是狗吗？，就放弃了高精度的想法。看了看E，看了看I，又没什么思路。然后决定还是弄个高精度吧，改了十分钟，比赛结束，后两小时一动不动，打出GG。
= 总结 =
== reku ==
前期表现尚可，后期有点糟糕。E和I都不是那种很难的题目，全力去想感觉应该都是很有希望的。F如果在看题的时候就意识到高精度的话，直接上py，也是很有希望过的。虽然只有两个人打比赛，但是感觉7——8题应该是一个比较合理的题目数。两人对高精度都表现出了逃避，这个很糟糕，也是一个很大的失误。E和I赛后仔细想了一下，感觉真的都不难，为什么比赛时候想不到呢？H题比赛的时候没有碰，不做评论了。K和L就是能力不够。
== lzw4896s ==
前面签到题做的还算比较顺利，C题题目没看仔细贡献了一发WA，需要吸取教训，签到题要看清题目再写。D题看到题目很快想到了解法，但是感觉复杂度有点玄，没敢写，reku学长让我去试一试，而且没别的题可做才写了这题，最后竟然过了，说明对运行时间的估计还是略有欠缺，还是要通过练习积累经验。之后的表现就有些糟糕，网络流题给reku学长提供了一个小性质后就一直在E，I两题之间徘徊。 E题题目看了很多遍还是不能理解，内心就有点抵触，应该自己动手去撕一下纸带的，而不该直接甩锅给队友。 I题最后想到的乱搞方法其实和标算有些接近了，但是看到 2^n^ 个点就一口咬定是用什么分治递归来解决的，就一直往这方面靠，思路过于狭隘了。 最后策略上还是有些问题，去入坑F题的时候猜测出题人不会这么丧病要高精度，写好调出样例交上去WA了的时候大概还有一个多小时。 如果当时果断换python写说不定最后还能过掉这题。 当时还是抱着侥幸心理骗自己不会要用高精度的，于是人工构造了十来个小数据来查错，把最后的时间浪费掉了。 第一次和reku学长配合，reku学长帮我看出了代码的错误，我发现reku学长交错了题（好在是交到已经AC的题目里去了），签到题各自做，合作完成了D和G题，但是后面卡题的时候双方并没有给对方提供什么有用的思路，基本上是各想各的，之后还有待磨合。
= 教训 =
写题不能侥幸
注意不要交错题目
= 题解 =
* I:贪心。 假设已经决定选2k+1个点连边，按坐标从左到右依次是1-2k+1号点。 那么连边<1, k + 1, 2k + 1, k, 2k, k - 1, 2k - 1, k - 2, 2k - 2 .....2, k + 1, 1>，这样得到的解是最优的。证明：可以发现这样构造的解的答案是min(dist<1, k + 1>, dist<2, k + 2> .... dist<k, 2k>, dist<k + 1, 2k + 1>). 假设最近的是点对<i, i + k>. 如果存在某个解比dist<i, i + k>更优, 那么这个解中，对于 i 和 i + k之间的k - 1个点，它们连出去的2k-2条边必须连到1...k - 1 和 i + k + 1...2k + 1这k个点上,否则最小值就比dist<i, i + k>小了. 但是当k > 1 的 时候 2 * (k - 1) > k。 根据这个性质就可以贪心了。 最左最右边各选一半，枚举最中间的点即可。
* E: 发现对于奇数，环变成了n和2n+2，对于偶数，变成两个n。那就记录一下每个旋转对应的值，然后对着找一找就好了，如果没有这个奇数的话，那怎样都没有，如果没有这个偶数，看看之前的奇数能不能产生这个偶数就好了
* F: 每次先找到最长的分数线来确定baseline,如果没有分数线找到最左边的数字所在的行就是baseline. 然后根据加和乘号左右分治，以及考虑分数线上下分治。用python实现高精度。
* L: 首先，这个图一定要是个强联通图。然后，所有简单环一定要互质。然后就tarjan一下，染色随便找个环，对所有的因子染色就好了
* H 待补
* K 尽力补
流水账
今天Johann学长继续鸽，reku和lzw参加了比赛。
开场lzw过掉水题ABC，reku过掉水题G，然后reku和lzw讨论了一下水题D，提出了一个O(N*N*K)的做法，lzw感觉过不了，reku说一定可以过的，然后欣喜的过了。
之后二人开始讨论网络流题目J，lzw学长给出了费用只有X和X-1两种，reku想了个正确性不是很显然的网络流乱搞，想让lzw学长证一下，lzw学长还没证完，reku就写完了，意外的过了J。
前六题过得还算比较顺畅，六题之后我们是第二名，然后两人讨论了I和E都表示没什么思路。然后lzw学长思考了一下大模拟F，觉得还行，开始上机写F。
reku在lzw写F的时候，一直在撕纸玩，试图得出一些结论，然后感觉4、2和0是完全一样的，撕纸翻了翻，好像的确完全一样，于是感觉题目意义飘渺，难以理解。实际上是reku拓扑理论没有学过，智力也不够，动手能力还差导致的。
lzw很快过了样例，然后交了一发，wa了。两人debug好久，感觉可能要用到高精度，后来又感觉这种大模拟还要高精度，出题人是狗吗？，就放弃了高精度的想法。看了看E，看了看I，又没什么思路。然后决定还是弄个高精度吧，改了十分钟，比赛结束，后两小时一动不动，打出GG。
总结
reku
前期表现尚可，后期有点糟糕。E和I都不是那种很难的题目，全力去想感觉应该都是很有希望的。F如果在看题的时候就意识到高精度的话，直接上py，也是很有希望过的。虽然只有两个人打比赛，但是感觉7——8题应该是一个比较合理的题目数。两人对高精度都表现出了逃避，这个很糟糕，也是一个很大的失误。E和I赛后仔细想了一下，感觉真的都不难，为什么比赛时候想不到呢？H题比赛的时候没有碰，不做评论了。K和L就是能力不够。
lzw4896s
前面签到题做的还算比较顺利，C题题目没看仔细贡献了一发WA，需要吸取教训，签到题要看清题目再写。D题看到题目很快想到了解法，但是感觉复杂度有点玄，没敢写，reku学长让我去试一试，而且没别的题可做才写了这题，最后竟然过了，说明对运行时间的估计还是略有欠缺，还是要通过练习积累经验。之后的表现就有些糟糕，网络流题给reku学长提供了一个小性质后就一直在E，I两题之间徘徊。 E题题目看了很多遍还是不能理解，内心就有点抵触，应该自己动手去撕一下纸带的，而不该直接甩锅给队友。 I题最后想到的乱搞方法其实和标算有些接近了，但是看到 2n 个点就一口咬定是用什么分治递归来解决的，就一直往这方面靠，思路过于狭隘了。 最后策略上还是有些问题，去入坑F题的时候猜测出题人不会这么丧病要高精度，写好调出样例交上去WA了的时候大概还有一个多小时。 如果当时果断换python写说不定最后还能过掉这题。 当时还是抱着侥幸心理骗自己不会要用高精度的，于是人工构造了十来个小数据来查错，把最后的时间浪费掉了。 第一次和reku学长配合，reku学长帮我看出了代码的错误，我发现reku学长交错了题（好在是交到已经AC的题目里去了），签到题各自做，合作完成了D和G题，但是后面卡题的时候双方并没有给对方提供什么有用的思路，基本上是各想各的，之后还有待磨合。
教训
写题不能侥幸
注意不要交错题目
题解
- I:贪心。 假设已经决定选2k+1个点连边，按坐标从左到右依次是1-2k+1号点。 那么连边<1, k + 1, 2k + 1, k, 2k, k - 1, 2k - 1, k - 2, 2k - 2 .....2, k + 1, 1>，这样得到的解是最优的。证明：可以发现这样构造的解的答案是min(dist<1, k + 1>, dist<2, k + 2> .... dist
). 假设最近的是点对 - E: 发现对于奇数，环变成了n和2n+2，对于偶数，变成两个n。那就记录一下每个旋转对应的值，然后对着找一找就好了，如果没有这个奇数的话，那怎样都没有，如果没有这个偶数，看看之前的奇数能不能产生这个偶数就好了
- F: 每次先找到最长的分数线来确定baseline,如果没有分数线找到最左边的数字所在的行就是baseline. 然后根据加和乘号左右分治，以及考虑分数线上下分治。用python实现高精度。
- L: 首先，这个图一定要是个强联通图。然后，所有简单环一定要互质。然后就tarjan一下，染色随便找个环，对所有的因子染色就好了
- H 待补
- K 尽力补
附加文件
- Screenshot from 2017-08-18 22-14-42.png by ruiker