2018-team8-E08

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(day8.png)]]

== 流水账 ==

zhhhplus: 今天是一场难度不高的场，但是爆炸得很厉害。今天开场看到榜上有人秒过了J题，以为J题是个签到，然后就稍微看了一下，是个多重背包在有向图上跑，大家发现（点数大于1的）scc里面的点能随意取，以及随便log做多层背包，但是停在这个地方发现过A题的人更多，就先放着了。然后cyw去写A题，写了一发之后交上去结果WA1了（历史总是惊人的相似），接着我来一起看A的代码，没找到什么错。lsy读了G题，我一看这个1e12的数字可以减小到2000嘛，然后随便背包一下乘个组合数就行了，和lsy讨论了一下（cyw也在），接着被指出了一个小错误，大家决定让lsy写G题。在lsy写之前，我想着加个assert交一波A题，在提交页面的时候我愣住了，发现是文件目录没有改，然后过掉了A题。接着我们发现B题过的人挺多的，我一看B题，觉得高斯消元很靠谱，之后稍微优化了一下，把复杂度从1000^3^减到了36*36*1000/64，感觉能过并且很稳，于是让cyw写B题。G题因为爆long long和初始化的锅WA了1次（神奇），然后比较顺利地过了。之后想D题，我一开始觉得像是拉格朗日乘数法搞搞就过了，结果果然每次我想到拉格朗日乘数法的时候一定不是拉格朗日乘数法，然后我放弃掉拉格朗日乘数法，稍微推了一下式子，发现在W取定的时候价值函数是个一次函数，随便统计一下转折点的数值就出结果了。lsy去写这一题，cyw则好好想B题的细节。WA了一发D题之后，lsy发现了代码上的一个小bug，改了之后过掉了D题。接着就是cyw长期的调B题时间，我和lsy想F和J和K题。之后我们发现cyw的高斯消元没有从后往前消元的部分……改了之后接着WA2……之后我们又发现高斯消元之后可能会有一行的开关有多个，这时候要输出“？”，改了之后才过掉……cyw和我讲了他K题的思路，枚举14个点的二进制……我觉得可能枚举19位比较靠谱……然后cyw rush了一下，最后没在时间结束之前过掉它。赛后WA2，并且也不知道是为什么错……改了一下写法就过掉了。

== 总结 ==

zhhhplus: 感觉今天的主要问题是B题占用的时间太久了，在某个算法不太懂的情况下应该多询问一下或者换人？以及下次别交错文件了？以及这个爆long long和舒适化希望在写的时候就能考虑周全？然后比如今天的J题其实完全能出……K题也完全能出……别的比如H题是个sb大模拟也没有发现，大概主要是卡在B题调试上了？顺便猜测lsy今天的比赛体验不太好……（怎么想都是B题我说高斯消元的锅？不过听说能暴力但是不太会暴力做法啊？）

== 补题 ==

 * F: LIN452
 * J: LIN452
 * H: Pepcy_Ch
 * K: Pepcy_Ch

流水账

zhhhplus: 今天是一场难度不高的场，但是爆炸得很厉害。今天开场看到榜上有人秒过了J题，以为J题是个签到，然后就稍微看了一下，是个多重背包在有向图上跑，大家发现（点数大于1的）scc里面的点能随意取，以及随便log做多层背包，但是停在这个地方发现过A题的人更多，就先放着了。然后cyw去写A题，写了一发之后交上去结果WA1了（历史总是惊人的相似），接着我来一起看A的代码，没找到什么错。lsy读了G题，我一看这个1e12的数字可以减小到2000嘛，然后随便背包一下乘个组合数就行了，和lsy讨论了一下（cyw也在），接着被指出了一个小错误，大家决定让lsy写G题。在lsy写之前，我想着加个assert交一波A题，在提交页面的时候我愣住了，发现是文件目录没有改，然后过掉了A题。接着我们发现B题过的人挺多的，我一看B题，觉得高斯消元很靠谱，之后稍微优化了一下，把复杂度从10003减到了36*36*1000/64，感觉能过并且很稳，于是让cyw写B题。G题因为爆long long和初始化的锅WA了1次（神奇），然后比较顺利地过了。之后想D题，我一开始觉得像是拉格朗日乘数法搞搞就过了，结果果然每次我想到拉格朗日乘数法的时候一定不是拉格朗日乘数法，然后我放弃掉拉格朗日乘数法，稍微推了一下式子，发现在W取定的时候价值函数是个一次函数，随便统计一下转折点的数值就出结果了。lsy去写这一题，cyw则好好想B题的细节。WA了一发D题之后，lsy发现了代码上的一个小bug，改了之后过掉了D题。接着就是cyw长期的调B题时间，我和lsy想F和J和K题。之后我们发现cyw的高斯消元没有从后往前消元的部分……改了之后接着WA2……之后我们又发现高斯消元之后可能会有一行的开关有多个，这时候要输出“？”，改了之后才过掉……cyw和我讲了他K题的思路，枚举14个点的二进制……我觉得可能枚举19位比较靠谱……然后cyw rush了一下，最后没在时间结束之前过掉它。赛后WA2，并且也不知道是为什么错……改了一下写法就过掉了。

总结

zhhhplus: 感觉今天的主要问题是B题占用的时间太久了，在某个算法不太懂的情况下应该多询问一下或者换人？以及下次别交错文件了？以及这个爆long long和舒适化希望在写的时候就能考虑周全？然后比如今天的J题其实完全能出……K题也完全能出……别的比如H题是个sb大模拟也没有发现，大概主要是卡在B题调试上了？顺便猜测lsy今天的比赛体验不太好……（怎么想都是B题我说高斯消元的锅？不过听说能暴力但是不太会暴力做法啊？）

补题

  • F: LIN452
  • J: LIN452
  • H: Pepcy_Ch
  • K: Pepcy_Ch
附加文件