2016-C10-team2

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||
||270||4:59:56||3224||D||g++0x||Wrong answer||
||269||4:54:41||2994||D||g++0x||Wrong answer||
||268||4:53:06||3008||D||g++0x||Wrong answer||
||265||4:47:53||3060||D||g++0x||Wrong answer||
||263||4:44:30||3041||D||g++0x||Wrong answer||
||239||3:41:09||872||B||gcc||OK||
||234||3:26:16||1023||E||g++0x||Wrong answer||
||232||3:20:10||722||B||gcc||Run-time error||
||230||3:11:02||711||E||g++0x||Wrong answer||
||227||3:06:41||670||E||g++0x||Wrong answer||
||207||2:12:36||823||B||gcc||Memory limit exceeded||
||198||1:33:30||1558||A||gcc||OK||

== 流水账 ==
=== TsReaper ===
今天题目比较困难，不过学长们还是尽量答对了能力范围内的题目。开场因为没看到简单题，我们就互相交流了题意，Starve学长觉得D可能比较可做，但是因为是几何题比较麻烦，决定先放一下。再看了看ranklist决定试一下ABE。一开始我们一起思考E，但是没有想出什么做法。之后Starve学长转战A，想到了大致的做法，告诉我之后我就思考A，两位学长思考B。一段时间后我想清楚了A的做法，'''A1y93'''。

学长们想了B的一个公式，但简单验证后发现不正确。hzf学长得到了一个带组合数和两个求和号的公式，我简单优化后写B，没想到交上去MLE了~~一下子没有把持住~~。出现了意料之外的问题我有点慌张，影响了队友的士气...好在Starve学长想了E的一个做法，我就和hzf学长思考B如何降低空间消耗。但Starve学长的做法貌似不正确，我和hzf学长也在滚动数组等方面出现了问题，卡得比较久。最后终于'''B1y221'''。练习结束后与其他队的学长交流发现其实有更简单的式子，应该多化简一下...最后一小时多我们思考E未果，Starve学长决定尝试D，并没有答对。

=== hzf ===
开场看F,G,H,不仅题难读，而且根本不会做...不久学长们说有队过E和B，于是我们先开始看E，看了一会儿无果...这时候starve学长发现了A的解法，和tsr学长讨论了一番，即上机写。这段时间我转战B，感觉和以前见过的概率题有点像...于是考虑了一个做法，starve学长上机帮我写了一发，结果过不了样例...进而发现公式有一部分考虑错了...期间我还怀疑过一些事件的独立性...幸而starve学长及时帮我纠正回正确的道路上...不久推出了一个正确的公式...然而硬求复杂度比较高，在优化的过程中我们遇到了预处理MLE，递推精度不行（赛后jtjl学长告诉我们分母上2的幂次可以先记下来，只在分子大于1时进行除法，同时分母的幂次如果大于某个数则令答案为0，而非将全部除法立刻进行，这样就能防止精度丢失导致答案始终0），滚动数组初始化错误等问题，卡了非常久...赛后发现了学长们的递推式非常简洁，今后在无法找到简介的表达式解，可以尝试递推式解。

之后大家开始想E，基本没思路...最后starve学长决定写D，思路很正确，可惜最后没能调试出来...有一部分是我的锅...B占用太长时间..


== 总结 ==
=== TsReaper ===
 * 对各种问题应该都有一个准备，今天第一次碰到MLE比较慌乱...
 * 今天做出了百度之星~~yandex之星~~复赛的效果，对比较困难的比赛实力还不行。

=== hzf ===
 * 学习避免精度丢失的方法...
 * 滚动数组需要注意初始化
 * 在找不到简洁的closed-form时应该考虑递推

=== 3z ===
 * 模板不可信啊。。在抄模板的时候要加上自己的思考啊。。
 * 暴露了实力，真正难题的时候并不能帮上队友什么忙
 * 要大胆猜测

== 题解 ==
=== E - Game ===
有一个比较重要的结论：一个数整除很多数，最后得到的结果与整除的顺序无关。所以我们枚举使用哪些卡片，把这些卡片上的数乘起来排个序，就把L~R分成了很多个区间。对于同一区间内的两个数A,B，由于它们的sg函数转移图是相同的，所以A和B要么全部先手必胜，要么全部先手必败。

可以简单地反证一下。如果A和B的sg函数转移图相同，那么对于每一套恰好把A变成0的卡片，也要恰好把B变成0. 如果有一套卡片可以把A变成0，但是不能把B变成0，则这一套卡片的乘积位于A和B之间，这样A和B就会被分开，不可能在同一区间里了。

== 补题 ==
=== TsReaper ===
C, ~~E~~, F, H

=== hzf ===
~~E~~
Run IDTimeSizeProblemLanguageResult
2704:59:563224Dg++0xWrong answer
2694:54:412994Dg++0xWrong answer
2684:53:063008Dg++0xWrong answer
2654:47:533060Dg++0xWrong answer
2634:44:303041Dg++0xWrong answer
2393:41:09872BgccOK
2343:26:161023Eg++0xWrong answer
2323:20:10722BgccRun-time error
2303:11:02711Eg++0xWrong answer
2273:06:41670Eg++0xWrong answer
2072:12:36823BgccMemory limit exceeded
1981:33:301558AgccOK

流水账

TsReaper

今天题目比较困难，不过学长们还是尽量答对了能力范围内的题目。开场因为没看到简单题，我们就互相交流了题意，Starve学长觉得D可能比较可做，但是因为是几何题比较麻烦，决定先放一下。再看了看ranklist决定试一下ABE。一开始我们一起思考E，但是没有想出什么做法。之后Starve学长转战A，想到了大致的做法，告诉我之后我就思考A，两位学长思考B。一段时间后我想清楚了A的做法，A1y93。

学长们想了B的一个公式，但简单验证后发现不正确。hzf学长得到了一个带组合数和两个求和号的公式，我简单优化后写B，没想到交上去MLE了一下子没有把持住。出现了意料之外的问题我有点慌张，影响了队友的士气...好在Starve学长想了E的一个做法，我就和hzf学长思考B如何降低空间消耗。但Starve学长的做法貌似不正确，我和hzf学长也在滚动数组等方面出现了问题，卡得比较久。最后终于B1y221。练习结束后与其他队的学长交流发现其实有更简单的式子，应该多化简一下...最后一小时多我们思考E未果，Starve学长决定尝试D，并没有答对。

hzf

开场看F,G,H,不仅题难读，而且根本不会做...不久学长们说有队过E和B，于是我们先开始看E，看了一会儿无果...这时候starve学长发现了A的解法，和tsr学长讨论了一番，即上机写。这段时间我转战B，感觉和以前见过的概率题有点像...于是考虑了一个做法，starve学长上机帮我写了一发，结果过不了样例...进而发现公式有一部分考虑错了...期间我还怀疑过一些事件的独立性...幸而starve学长及时帮我纠正回正确的道路上...不久推出了一个正确的公式...然而硬求复杂度比较高，在优化的过程中我们遇到了预处理MLE，递推精度不行（赛后jtjl学长告诉我们分母上2的幂次可以先记下来，只在分子大于1时进行除法，同时分母的幂次如果大于某个数则令答案为0，而非将全部除法立刻进行，这样就能防止精度丢失导致答案始终0），滚动数组初始化错误等问题，卡了非常久...赛后发现了学长们的递推式非常简洁，今后在无法找到简介的表达式解，可以尝试递推式解。

之后大家开始想E，基本没思路...最后starve学长决定写D，思路很正确，可惜最后没能调试出来...有一部分是我的锅...B占用太长时间..

总结

TsReaper

  • 对各种问题应该都有一个准备，今天第一次碰到MLE比较慌乱...
  • 今天做出了百度之星yandex之星复赛的效果，对比较困难的比赛实力还不行。

hzf

  • 学习避免精度丢失的方法...
  • 滚动数组需要注意初始化
  • 在找不到简洁的closed-form时应该考虑递推

3z

  • 模板不可信啊。。在抄模板的时候要加上自己的思考啊。。
  • 暴露了实力，真正难题的时候并不能帮上队友什么忙
  • 要大胆猜测

题解

E - Game

有一个比较重要的结论：一个数整除很多数，最后得到的结果与整除的顺序无关。所以我们枚举使用哪些卡片，把这些卡片上的数乘起来排个序，就把L~R分成了很多个区间。对于同一区间内的两个数A,B，由于它们的sg函数转移图是相同的，所以A和B要么全部先手必胜，要么全部先手必败。

可以简单地反证一下。如果A和B的sg函数转移图相同，那么对于每一套恰好把A变成0的卡片，也要恰好把B变成0. 如果有一套卡片可以把A变成0，但是不能把B变成0，则这一套卡片的乘积位于A和B之间，这样A和B就会被分开，不可能在同一区间里了。

补题

TsReaper

C, E, F, H

hzf

E

附加文件