2017-Sp14-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,600px)]]
== 流水账 ==
开场各自看题，yzc判断A题的前半部分是kruskal，就先上机写了，cjb去看A的剩下部分，发现是简单算贡献题，就跟yzc说了，yzc不久后就A掉，'''A1y15'''. sub觉得自己会G，上机写了一点发现不太对，yzc给cjb讲了B题，cjb觉得B很傻逼，就换下sub去写B，很快写完过了样例，提交wa了...cjb读了遍题发现yzc讲的题意有偏差，修改后变成tle，cjb很恼火，就改了个比较快的求mex方法，然后'''B3y49'''. yzc和sub讨论出了D，yzc上机写D，wa了两发后找到了bug，'''D3y78'''. 接下来，三人先后开了G、K、I，cjb也提出了H应该是个分治+NTT，G很多人过，但一直不大会做，I前半部分打表应该没什么问题，打算让cjb去敲。cjb把C题意告诉了yzc，yzc提出了一个听起来很靠谱的假设，三个人都觉得很科学，就让yzc去写C了，C先后花了接近一个小时的时间，交了4发，从tle变成wa，最后cjb提出了一个可以叉掉做法的东西，很无奈只好放弃. 幸好sub想出了G，'''G1y198'''. 三人停了一会儿，cjb打算去写I，然后sub想好了K，就让sub先写K，'''K1y230'''. 此前cjb和yzc基本开出了E，结合过题人数很多，感觉很稳，yzc上机写E，然后一直tle到了最后，最后一段时间交题十分艰难，要发邮件到yzc手提电脑再提交，十分麻烦. 最后也没有再过题，看题解发现E的做法比dp暴力得多，但是感觉跑起来会很快，另外I也是因为时间问题，如果没有去做C估计能过掉I. 三个人还是需要再适应一下这种题目，才能做出正确的决策，事实上Siunaus的7题是在能力范围之内的，实际上H题的正确做法早早就提出来了，甚至应该有能力8题的....这套题还是蛮有启发的。
== 总结 ==
=== chenjb ===
常数卡得十分难受，hdu真的好慢....这个I和E没过是比较可惜的，都是能力范围里的题，不过E确实应该及时去换做法，感觉暴力+二分图可能更符合oi选手出题?（误） 这套题里有很多题是把几个模型强行合在了一起，虽然不太喜欢，但是也许在区域赛就会遇到这样的没营养题呢，如何快速提取模型，把经典做法修改完善，确实需要不断去总结(老子tm怎么变回oi选手了)..... GTM的H题！！！！我其实都想出来了啊，没有和yzc和sub讨论&克服心虚去做实在是太亏了！
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：kruskal+枚举边的贡献
 * B：辣鸡SG函数，开个bool数组求mex，不然会tle...
 * C：emmmm脑力风暴一下好了
 * D：gcd...一个数字不断gcd，gcd只会向下变小log次.......
 * E：全排列枚举阴珠子的排列， 然后对于一种排列， 给每一个位置对应的不会褪色的阳珠子建边， 跑出的最大匹配就是最多的不褪色阳珠子个数(状压dp会t掉...)
 * F：数论二合一...
 * G：提取判定模型+dp(??）
 * H：cdq分治+FFT
 *  I：状压dp经典题+类似容斥的dp求方案数
 * J：树hash
 * K：三维几何题
== 补题 ==

流水账

开场各自看题，yzc判断A题的前半部分是kruskal，就先上机写了，cjb去看A的剩下部分，发现是简单算贡献题，就跟yzc说了，yzc不久后就A掉，A1y15. sub觉得自己会G，上机写了一点发现不太对，yzc给cjb讲了B题，cjb觉得B很傻逼，就换下sub去写B，很快写完过了样例，提交wa了...cjb读了遍题发现yzc讲的题意有偏差，修改后变成tle，cjb很恼火，就改了个比较快的求mex方法，然后B3y49. yzc和sub讨论出了D，yzc上机写D，wa了两发后找到了bug，D3y78. 接下来，三人先后开了G、K、I，cjb也提出了H应该是个分治+NTT，G很多人过，但一直不大会做，I前半部分打表应该没什么问题，打算让cjb去敲。cjb把C题意告诉了yzc，yzc提出了一个听起来很靠谱的假设，三个人都觉得很科学，就让yzc去写C了，C先后花了接近一个小时的时间，交了4发，从tle变成wa，最后cjb提出了一个可以叉掉做法的东西，很无奈只好放弃. 幸好sub想出了G，G1y198. 三人停了一会儿，cjb打算去写I，然后sub想好了K，就让sub先写K，K1y230. 此前cjb和yzc基本开出了E，结合过题人数很多，感觉很稳，yzc上机写E，然后一直tle到了最后，最后一段时间交题十分艰难，要发邮件到yzc手提电脑再提交，十分麻烦. 最后也没有再过题，看题解发现E的做法比dp暴力得多，但是感觉跑起来会很快，另外I也是因为时间问题，如果没有去做C估计能过掉I. 三个人还是需要再适应一下这种题目，才能做出正确的决策，事实上Siunaus的7题是在能力范围之内的，实际上H题的正确做法早早就提出来了，甚至应该有能力8题的....这套题还是蛮有启发的。

总结

chenjb

常数卡得十分难受，hdu真的好慢....这个I和E没过是比较可惜的，都是能力范围里的题，不过E确实应该及时去换做法，感觉暴力+二分图可能更符合oi选手出题?（误） 这套题里有很多题是把几个模型强行合在了一起，虽然不太喜欢，但是也许在区域赛就会遇到这样的没营养题呢，如何快速提取模型，把经典做法修改完善，确实需要不断去总结(老子tm怎么变回oi选手了)..... GTM的H题！！！！我其实都想出来了啊，没有和yzc和sub讨论&克服心虚去做实在是太亏了！

oipotato

subconscious

题解

  • A：kruskal+枚举边的贡献
  • B：辣鸡SG函数，开个bool数组求mex，不然会tle...
  • C：emmmm脑力风暴一下好了
  • D：gcd...一个数字不断gcd，gcd只会向下变小log次.......
  • E：全排列枚举阴珠子的排列， 然后对于一种排列， 给每一个位置对应的不会褪色的阳珠子建边， 跑出的最大匹配就是最多的不褪色阳珠子个数(状压dp会t掉...)
  • F：数论二合一...
  • G：提取判定模型+dp(??）
  • H：cdq分治+FFT
  • I：状压dp经典题+类似容斥的dp求方案数
  • J：树hash
  • K：三维几何题

补题

附加文件