2017-Sp35-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，一段时间后cjb上机试图写A的java，写到后来不知道怎么搞，遂放弃。yzc和sub讨论了已经有人过的C，yzc上机，'''C1y36'''. cjb和sub讨论了一下D，yzc写完C后就让他继续写D，'''D3y52'''. cjb和yzc传达J题意的时候发现自己理解的题意有点偏差，思考一会儿后就想到了费用流，cjb上机敲了板子，yzc让cjb去想G，自己来写建图，不久后'''J1y88'''. 接下来的时间，sub尝试做A或G，yzc和cjb尝试做E，一直都不能做。三个小时的时候cjb终于想到了大概的G的思路，和sub讨论，yzc也加入讨论，但是三个人都没想清楚，cjb打算先去写个暴力，尝试优化之后调参。后来yzc和sub加入战斗，找到了很多bug，也进行了很多尝试，但是一直wa，最后无奈之下和暴力对拍找到了一个非常隐蔽的错误，最后终于'''G9y298'''. 一队做了5题，我们只做了4题收尾，不太理想，需要继续努力
== 总结 ==
=== chenjb ===
感觉我们队需要在做莽的题上多总结多训练，要坚定信心，有些时候对拍非常有用。还有就是，我们要考虑互相有没有判断错题目研究的方向，有些时候需要换个角度思考。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：
   * 题意：给出两个整数部分是0，小数部分不超过100000位的循环节的两个实数，有q个询问，询问第i位的数值。
   * 解法：对于所问的位置，只需要考虑是否会被进位，而进位则与该数字之后第一个和不为9的位置p有关，若a[p]+b[p]>9则进位，否则进位。对两个串作哈希，然后倍增预处理其某一位开始2^p^次方的哈希值，再预处理9999.....的哈希值，这样直接将两个串同一段相加再和其比较就能判断是否全为9了，虽然如果存在该不为9的位置，则该位置肯定位于lcm(n,m)之内，但是二分答案则需要两个log会超时，我们可以类似于像求lca那样，从大到小枚举2^p^，每当该段与999....哈希值相同，就累计到答案并且跳跃，这样就是一个log的了，注意位置变换后要通过取模找到其在循环节中实际对应的位置。另外要特判一些corner case，比如0.999999...约等于0，以及和为0.99999999....则视为0这些情况。
 * [https://wiki.icpc-camp.org/twsf/Andrew%20Stankevich%20Contest%2048 TheWaySoFar]
 * [https://wiki.icpc-camp.org/dreadnought/Andrew%20Stankevich%20Contest%2048 Dreadnought]
== 补题 ==
 * ~~A~~ by cjb
 * B
 * E
 * H
 * I

流水账

开场各自看题，一段时间后cjb上机试图写A的java，写到后来不知道怎么搞，遂放弃。yzc和sub讨论了已经有人过的C，yzc上机，C1y36. cjb和sub讨论了一下D，yzc写完C后就让他继续写D，D3y52. cjb和yzc传达J题意的时候发现自己理解的题意有点偏差，思考一会儿后就想到了费用流，cjb上机敲了板子，yzc让cjb去想G，自己来写建图，不久后J1y88. 接下来的时间，sub尝试做A或G，yzc和cjb尝试做E，一直都不能做。三个小时的时候cjb终于想到了大概的G的思路，和sub讨论，yzc也加入讨论，但是三个人都没想清楚，cjb打算先去写个暴力，尝试优化之后调参。后来yzc和sub加入战斗，找到了很多bug，也进行了很多尝试，但是一直wa，最后无奈之下和暴力对拍找到了一个非常隐蔽的错误，最后终于G9y298. 一队做了5题，我们只做了4题收尾，不太理想，需要继续努力

总结

chenjb

感觉我们队需要在做莽的题上多总结多训练，要坚定信心，有些时候对拍非常有用。还有就是，我们要考虑互相有没有判断错题目研究的方向，有些时候需要换个角度思考。

oipotato

subconscious

题解

• A：
  • 题意：给出两个整数部分是0，小数部分不超过100000位的循环节的两个实数，有q个询问，询问第i位的数值。
  • 解法：对于所问的位置，只需要考虑是否会被进位，而进位则与该数字之后第一个和不为9的位置p有关，若a[p]+b[p]>9则进位，否则进位。对两个串作哈希，然后倍增预处理其某一位开始2^p次方的哈希值，再预处理9999.....的哈希值，这样直接将两个串同一段相加再和其比较就能判断是否全为9了，虽然如果存在该不为9的位置，则该位置肯定位于lcm(n,m)之内，但是二分答案则需要两个log会超时，我们可以类似于像求lca那样，从大到小枚举2^p，每当该段与999....哈希值相同，就累计到答案并且跳跃，这样就是一个log的了，注意位置变换后要通过取模找到其在循环节中实际对应的位置。另外要特判一些corner case，比如0.999999...约等于0，以及和为0.99999999....则视为0这些情况。
• TheWaySoFar
• Dreadnought

补题

• A by cjb
• B
• E
• H
• I

附加文件

• 1.png by chenjb
• F.cpp by chenjb