2014-C02-team2

从 Trac 迁移的文章

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

原文章内容如下:

T_T

=== 流水账 ===

{{{
By Magica
开场上来我从前往后看,这次题目难度比较有顺序,所以上来大概半个小时就按顺序1A了A,B,C三题。D题和数学有关并且看到ZYC队7分钟AC了,一度以为有某些很屌的结论,就没有再坑下去。
看到E后发现是错排,思路比较直接,我和Soda开始想,大概10分钟左右,Soda想了个递推做法,我给出了容斥的做法,我对自己做法比较有信心就开始搞了,可是由于边界条件没判(K == 0的时候)并且修改的时候忘记加上数据组数,导致最后3A。
接着朱稼乐觉得D暴力可过就上来搞了一发,1A。F是博弈,我不太擅长,Soda开始想F,我和朱稼乐在想H。Soda做完F后WA了一次,改了后2A。朱稼乐发现H的范围比较小,用比较暴力的方法搞过了。
这时剩G和I,我和Soda看当时I还没人过,所以打算抢救一下G。想了各种姿势都觉得不靠谱,吃完饭开始搞爆搜。搞了大概40分钟,交一发发现是WA不是TLE,觉得有救开始拍数据Debug。
最后没调出来。
错误的原因是我们使用Multiset来限制枚举边的上界的时候,对删除的操作使用了Multiset.erase(int)方法,这种方法会删除所有的相同的值导致限制被取消产生交叉边的情况,应该使用Multiset.erase(iterator)可以删除单个元素。
}}}
{{{
by sodabeta

开场之后,magi从前往后看,zqf从中间看,我看了最后的3题。不久magi就发现A,B,C都是水题,然后7min A 1Y, 12 min B 1Y, 37 min C 1Y。我看了最后三题后没什么太好的思路,就和zqf学长讨论了

一下E的做法,但是我推公式的时候一直没理的太清楚,之后magi和我说了他容斥的做法,觉得靠谱就去写了,之后wa了2次,66 min E 3Y。

在此期间我和zqf一直在讨论D的做法,fibonacci数模m的循环节问题,我之前看到过这种题目也知道有公式,但是记不清了,所以一直在尝试去推一推回忆起来。之后发现很多队伍都过了D,zqf学长说肯定不会

那么复杂就去写了暴力然后76min D 1Y。然后我就去看F,非常简单的有O(n^4)的dp的解法,但是复杂度可能会有1亿,所以一开始我没敢写就一直在考虑怎么简化状态,后来一直没好的思路就去写了最直接的

记忆化搜索然后发现跑的很快就交了,然后返回了wrong answer。打印下来后我去查错,zqf和magi在讨论H的做法。之后我一直找不到错在哪里,看到机器空着我就去又测了几组数据,然后找到了错误,

138 min F 2Y。之后zqf学长就去写H, 非常靠谱的166 min H 1Y。

在这之后就是悲剧的开始,我们一致认定G应该可以搞出来,就没有管I全力搞G。我和magi一开始一直在考虑一些奇怪的做法,推导出一些性质之后转化成了图论的问题,尝试用网络流构图解决但一直没有靠谱的做法,

于是决定搜!讨论了怎样搜比较靠谱之后magi就去写了搜索部分,我写了输出答案部分,写完之后调过了样例,交了返回了wa, 我们就一起去debug,造了不少数据,也找到了一些bug,但是交了还是wa, 这之后的两

小时里就一直在重复这个过程,最后的两分钟里magi问我multiset要erase一个元素的值的时候是删除一个还是删除所有,我说只会删除一个。而这个就是程序的最后一个bug了。。。因为我的锅没有抢救回来T_T,

 赛后一改就过了。

最后rank4, 这场打的比较土,我今天状态也非常差,脑袋一直都不是很清楚,最后还坑了队友没有过了G,学会了一些做人的道理。
}}}

=== 总结 ===
{{{
By Magica
乱搞很重要。
虽然提交速度很重要,但是稍微拍一些边界数据、极端情况还是必不可少的。
STL中有很多函数重载,每个方法的行为可能不一样,要注意。
}}}
{{{
By sodabeta

1 开场后谁看到水题应该果断去写,昨天开场有点不科学,今天好了很多

2 过了样例之后不要急着就交提,多测几组数据,特别是边界情况的数据,尽量避免罚时

3 在比赛的最后一个小时里,应该要更用力,不能想着守住第几名,毕竟自己队伍能出更多的题才是王道

4 有一些我们三个人都不会的算法应该赶紧抢救; 每一块部分最好有至少两个人都懂,这样可以多讨论一些
}}}
{{{
by 朱稼乐
昨天晚上没有睡足, 导致今天状态比较糟糕, 做H题时候连矩阵乘法也写错了, 浪费了不少时间. 今后比赛前一定要早点睡觉.
}}}

T_T

流水账

By Magica
开场上来我从前往后看,这次题目难度比较有顺序,所以上来大概半个小时就按顺序1A了A,B,C三题。D题和数学有关并且看到ZYC队7分钟AC了,一度以为有某些很屌的结论,就没有再坑下去。
看到E后发现是错排,思路比较直接,我和Soda开始想,大概10分钟左右,Soda想了个递推做法,我给出了容斥的做法,我对自己做法比较有信心就开始搞了,可是由于边界条件没判(K == 0的时候)并且修改的时候忘记加上数据组数,导致最后3A。
接着朱稼乐觉得D暴力可过就上来搞了一发,1A。F是博弈,我不太擅长,Soda开始想F,我和朱稼乐在想H。Soda做完F后WA了一次,改了后2A。朱稼乐发现H的范围比较小,用比较暴力的方法搞过了。
这时剩G和I,我和Soda看当时I还没人过,所以打算抢救一下G。想了各种姿势都觉得不靠谱,吃完饭开始搞爆搜。搞了大概40分钟,交一发发现是WA不是TLE,觉得有救开始拍数据Debug。
最后没调出来。
错误的原因是我们使用Multiset来限制枚举边的上界的时候,对删除的操作使用了Multiset.erase(int)方法,这种方法会删除所有的相同的值导致限制被取消产生交叉边的情况,应该使用Multiset.erase(iterator)可以删除单个元素。
by sodabeta
开场之后,magi从前往后看,zqf从中间看,我看了最后的3题。不久magi就发现A,B,C都是水题,然后7min A 1Y, 12 min B 1Y, 37 min C 1Y。我看了最后三题后没什么太好的思路,就和zqf学长讨论了
一下E的做法,但是我推公式的时候一直没理的太清楚,之后magi和我说了他容斥的做法,觉得靠谱就去写了,之后wa了2次,66 min E 3Y。
在此期间我和zqf一直在讨论D的做法,fibonacci数模m的循环节问题,我之前看到过这种题目也知道有公式,但是记不清了,所以一直在尝试去推一推回忆起来。之后发现很多队伍都过了D,zqf学长说肯定不会
那么复杂就去写了暴力然后76min D 1Y。然后我就去看F,非常简单的有O(n^4)的dp的解法,但是复杂度可能会有1亿,所以一开始我没敢写就一直在考虑怎么简化状态,后来一直没好的思路就去写了最直接的
记忆化搜索然后发现跑的很快就交了,然后返回了wrong answer。打印下来后我去查错,zqf和magi在讨论H的做法。之后我一直找不到错在哪里,看到机器空着我就去又测了几组数据,然后找到了错误,
138 min F 2Y。之后zqf学长就去写H, 非常靠谱的166 min H 1Y。
在这之后就是悲剧的开始,我们一致认定G应该可以搞出来,就没有管I全力搞G。我和magi一开始一直在考虑一些奇怪的做法,推导出一些性质之后转化成了图论的问题,尝试用网络流构图解决但一直没有靠谱的做法,
于是决定搜!讨论了怎样搜比较靠谱之后magi就去写了搜索部分,我写了输出答案部分,写完之后调过了样例,交了返回了wa, 我们就一起去debug,造了不少数据,也找到了一些bug,但是交了还是wa, 这之后的两
小时里就一直在重复这个过程,最后的两分钟里magi问我multiset要erase一个元素的值的时候是删除一个还是删除所有,我说只会删除一个。而这个就是程序的最后一个bug了。。。因为我的锅没有抢救回来T_T,
 赛后一改就过了。
最后rank4, 这场打的比较土,我今天状态也非常差,脑袋一直都不是很清楚,最后还坑了队友没有过了G,学会了一些做人的道理。

总结

By Magica
乱搞很重要。
虽然提交速度很重要,但是稍微拍一些边界数据、极端情况还是必不可少的。
STL中有很多函数重载,每个方法的行为可能不一样,要注意。
By sodabeta
1 开场后谁看到水题应该果断去写,昨天开场有点不科学,今天好了很多
2 过了样例之后不要急着就交提,多测几组数据,特别是边界情况的数据,尽量避免罚时
3 在比赛的最后一个小时里,应该要更用力,不能想着守住第几名,毕竟自己队伍能出更多的题才是王道
4 有一些我们三个人都不会的算法应该赶紧抢救; 每一块部分最好有至少两个人都懂,这样可以多讨论一些
by 朱稼乐
昨天晚上没有睡足, 导致今天状态比较糟糕, 做H题时候连矩阵乘法也写错了, 浪费了不少时间. 今后比赛前一定要早点睡觉.
附加文件