2012-C16-team4

从 Trac 迁移的文章

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

原文章内容如下：

 = 比赛流水 =

这场比赛我们开场有些太紧张了... 我看得1009, 1010, 1011三题其实除了1009都是简单题... 1011是搜索, 我写完之后不确定复杂度, 不过问了搞学长之后表示是原题, 于是果断交了. 然后是搞学长在1002上花了一段时间... 由于开场不顺, 于是搞学长一直比较紧张的样子, 弄得我也有一些紧张了 (不过我本场的问题倒不是在紧张, 毕竟这种情况也经历过几次了). 之后1001是个水题. 随便拿一个树状数组/线段树之类的可以区间统计数据结构统计一下增加的部分就可以了. 但是我们想出正确的算法就花了很久, 虽然这道题是我的问题, 但是也暴露出我们队这方面不够强的问题. 之后我们开了3个坑: 1006, 1008, 1010. 1006学姐交了一个贪心错了之后, 我想出了反例把她的程序给cha了. 于是我们开始考虑其他做法, 我的想法是爆搜, 感觉状态空间会坍缩得非常快, 可以一试, 但是还是觉得不够扎实, 于是没有写. 学姐赛后说她那时其实想到了状态压缩的dp, 但是因为我们在1008和1010两道扎实题上面卡题了, 于是也没仔细想转移方程. 1008搞学长想出差分约束的算法, 学姐推了一下约束, 但是前面一直TLE, 后面加了各种奇奇怪怪的优化之后还是WA. 于是搞学长最后时刻在乱交了, 这点不好. 1010是我土了, 我和学姐认为100*500*500可能会超时, 又想当然地觉得可以类似之前训练过的某一题(Wealthy Family)一样优化到100*500, 于是我就上去各种写. 结果WA了一次之后我发现我们的算法是错的, 这次和Wealthy Family那题不一样, 不能用那种方法来优化. 于是到最后我们都跳出这三个坑.

 = 赛后总结 =
 1. 开场太紧张, 出题慢, 不够自信.
 2. 算法太想当然, 还是要想清楚了再上去写. 不能感觉和之前的某题很像, 然后就稀里糊涂地上去写了, 要求是一下是不是可以那么做.
 3. 1008我觉得在差分约束对SPFA优化之后还是TLE的时候, 我们应该考虑到换一个算法, 因为这道题很明显可以做一个树形dp, 而搞学长和学姐也是应该看出来的.
 4. 还是要提高实力.

by 与星独白

比赛流水

这场比赛我们开场有些太紧张了... 我看得1009, 1010, 1011三题其实除了1009都是简单题... 1011是搜索, 我写完之后不确定复杂度, 不过问了搞学长之后表示是原题, 于是果断交了. 然后是搞学长在1002上花了一段时间... 由于开场不顺, 于是搞学长一直比较紧张的样子, 弄得我也有一些紧张了 (不过我本场的问题倒不是在紧张, 毕竟这种情况也经历过几次了). 之后1001是个水题. 随便拿一个树状数组/线段树之类的可以区间统计数据结构统计一下增加的部分就可以了. 但是我们想出正确的算法就花了很久, 虽然这道题是我的问题, 但是也暴露出我们队这方面不够强的问题. 之后我们开了3个坑: 1006, 1008, 1010. 1006学姐交了一个贪心错了之后, 我想出了反例把她的程序给cha了. 于是我们开始考虑其他做法, 我的想法是爆搜, 感觉状态空间会坍缩得非常快, 可以一试, 但是还是觉得不够扎实, 于是没有写. 学姐赛后说她那时其实想到了状态压缩的dp, 但是因为我们在1008和1010两道扎实题上面卡题了, 于是也没仔细想转移方程. 1008搞学长想出差分约束的算法, 学姐推了一下约束, 但是前面一直TLE, 后面加了各种奇奇怪怪的优化之后还是WA. 于是搞学长最后时刻在乱交了, 这点不好. 1010是我土了, 我和学姐认为100*500*500可能会超时, 又想当然地觉得可以类似之前训练过的某一题(Wealthy Family)一样优化到100*500, 于是我就上去各种写. 结果WA了一次之后我发现我们的算法是错的, 这次和Wealthy Family那题不一样, 不能用那种方法来优化. 于是到最后我们都跳出这三个坑.

赛后总结

1. 开场太紧张, 出题慢, 不够自信.

2. 算法太想当然, 还是要想清楚了再上去写. 不能感觉和之前的某题很像, 然后就稀里糊涂地上去写了, 要求是一下是不是可以那么做.

3. 1008我觉得在差分约束对SPFA优化之后还是TLE的时候, 我们应该考虑到换一个算法, 因为这道题很明显可以做一个树形dp, 而搞学长和学姐也是应该看出来的.

4. 还是要提高实力.

by 与星独白

附加文件