2017-Sp58-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(51562CED-F97D-46B2-A78F-EFB8C7B699AE.png,500px)]]
== 流水账 ==
开场各自看题，cjb重新负责了登陆和准备工作，yzc很快判断B是签到题，上机'''B1y7'''，sub读了K，让cjb上机写K，'''K1y15'''，yzc在场下推J，上机'''J1y18'''。大家各自看题，之后讨论了一下D和E，让yzc上机写E，cjb和sub研究D，yzc上机忘记文件读写wa了，改了还是wa，下机检查，cjb上机写D，不久也获得了wa。yzc和sub研究了下代码，之后上机尝试了一下，发现了问题，cjb发现自己写错了，修改后'''D2y68'''，yzc修正了做法后上机'''E3y72'''. sub读了H，和cjb讲了H的做法，跑去看A。cjb把做法和yzc讲了，yzc上机写H，之后'''H1y93'''. cjb上机写A，变量名写错wa了两发，'''A3y116'''. 之后三个人一起讨论C和G，没有什么太好的想法。一段时间后cjb给出了一个卡时空的bitset做法，三个人感觉时间勉强够，空间不够，讨论了一下之后惊讶地发现分块做竟然不会影响时间复杂度，yzc上机分了n/64块，结果tle了，把queue改掉还是tle，最后分成10块用bitset，然后卡过去了，'''C4y212'''. sub此前想出了G，把做法给了yzc，跑出结果之后，一起研究了很久如何输出方案，最后'''G1y271'''.
== 总结 ==
=== chenjb ===
还行，变量名写错逗比wa了两发。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * C：显然naive的做法就是把一类边加进来，然后判二类边是否成立。然后我们考虑用bitset来判断，时空复杂度都是n*n/64，时间还能支撑，空间不太行，然后我们惊讶地发现如果考虑分块，时间复杂度是不变的，因为k*n*(n/k)/64还是n*n/64，但是空间复杂度就降低了，但实际运用的时候还是要考虑别的常数，本题做的时候尝试分成n/64结果不太理想，因为边的遍历的原因，最后分成10块就卡过去了，这个思想也非常漂亮，可以用在很多题上。
 * [https://wiki.icpc-camp.org/dreadnought/XVI%20Open%20Cup%20named%20after%20E.V.%20Pankratiev.%20Grand%20Prix%20of%20Siberia.html Dreadnought]
== 补题 ==

流水账

开场各自看题，cjb重新负责了登陆和准备工作，yzc很快判断B是签到题，上机B1y7，sub读了K，让cjb上机写K，K1y15，yzc在场下推J，上机J1y18。大家各自看题，之后讨论了一下D和E，让yzc上机写E，cjb和sub研究D，yzc上机忘记文件读写wa了，改了还是wa，下机检查，cjb上机写D，不久也获得了wa。yzc和sub研究了下代码，之后上机尝试了一下，发现了问题，cjb发现自己写错了，修改后D2y68，yzc修正了做法后上机E3y72. sub读了H，和cjb讲了H的做法，跑去看A。cjb把做法和yzc讲了，yzc上机写H，之后H1y93. cjb上机写A，变量名写错wa了两发，A3y116. 之后三个人一起讨论C和G，没有什么太好的想法。一段时间后cjb给出了一个卡时空的bitset做法，三个人感觉时间勉强够，空间不够，讨论了一下之后惊讶地发现分块做竟然不会影响时间复杂度，yzc上机分了n/64块，结果tle了，把queue改掉还是tle，最后分成10块用bitset，然后卡过去了，C4y212. sub此前想出了G，把做法给了yzc，跑出结果之后，一起研究了很久如何输出方案，最后G1y271.

总结

chenjb

还行，变量名写错逗比wa了两发。

oipotato

subconscious

题解

  • C：显然naive的做法就是把一类边加进来，然后判二类边是否成立。然后我们考虑用bitset来判断，时空复杂度都是n*n/64，时间还能支撑，空间不太行，然后我们惊讶地发现如果考虑分块，时间复杂度是不变的，因为k*n*(n/k)/64还是n*n/64，但是空间复杂度就降低了，但实际运用的时候还是要考虑别的常数，本题做的时候尝试分成n/64结果不太理想，因为边的遍历的原因，最后分成10块就卡过去了，这个思想也非常漂亮，可以用在很多题上。
  • Dreadnought

补题

附加文件