关于HDU 5952的那些事

内容过后再贴，先发表一下心情和感悟。

这个题，我TLE了十多发，后来看了别人的题解，思路是一样的，他做了剪枝的我也做了，为何他的能过的我的超时？后来发现一个不是主要问题的问题：大家的图存储用的都是前向星式的写法，我的代码用的vector式的邻接表法，莫非vector很慢，导致超时？或者是我的代码写法结构和那个人的不一样，所以我的代码存在潜在的bug，说不定卡在哪个数据一直死循环了。然后把代码推倒重写，改成前向星式的写法，写好了，样例一测，直接过，提交一发，直接AC。我就不明白了，vector有这么慢吗？虽然之前也遇到卡vector的题，但vector也不至于慢太多呀，我始终想不明白呀。然后，再重新写了一个用vector存图的版本，dfs部分直接把前向星部分的复制过来，把边的扫描方式稍微改一改就OK了。样例一测，对了，提交一发，仍然AC。这下我就更不明白了，既然vector也能A，那说明不是vector的问题啊，莫非是我的第一个版本有死循环的bug？犹豫了一会，写了个测试数据生成器，生成一波大数据，把两个版本一跑，发现，版本三花了0.4s左右，版本一跑了蛮久，我以为是死递归了，准备关闭黑窗口时，跑完了，花了14s多。然后，我似乎明白了，版本一的某个地方花了太多时间，导致超时。对比一下两个版本，思路一模一样，代码结构略有不同，在保存答案那里，版本一用的是循环搜索得到的一组顶点解，用二进制位存储这些点，放到set集合中，让set自动去重。然后输出set的size。版本三是直接计数器加一，因为不存在重复。于是，我开始怀疑set了。虽说set的增删改查都是logN的时间复杂度，但是常数很大（也是听说的），莫非是这个常数大导致超时？仍然很疑惑啊，为何用set就这么慢。然后，我把版本三的记录答案也用了set，跑一下，花了12s多，差不多，仍然很慢，于是，我明白了，心里得到一个结论，set不要乱用，实在是慢。

———————————————————————————————————分割线——————————————————————————————————

过了几分钟后，发现，我记录答案的时候有个循环，对于每次的搜索结果，都要扫描一遍，最多10个，如果解有几千万个（完全有可能，如果N=32，M=1000，S=10），直接计数器加一可以不到1s完成任务，如果每个解都要循环10个顶点，那就要做几亿次循环，自然需要的时间就多了。所以，别小看这个“小循环”。

另外的话，想发表一下玩ACM的感悟。时间能快则快，哪怕是多一次无用的循环，能优化则优化。怎么快怎么写，速度快就是王道。比如：

;i < n;++i))flag = true;

这就是为了追求代码简介和优雅，牺牲了时间。如果是这种情况，还是要纠正习惯，改为这样，哪怕代码多点。

;i < n;++i){
    ){
        flag = true;
        break;
    }
}

其次，在保证时间足够快的基础上，对于编码来说，怎么快怎么写，不要去考虑变量命名是否规范、代码是否整洁之类的，ACM里面不搞这一套。过了就是王道，否则，没过的话，一切都是瞎扯淡。没用的。当然，能保证代码简介和整洁哪自然最好，保证不了也没关系。比如：

;i = tree[i].next)
while(scanf("%d", &n) != EOF)

直接这样就好了：

for(i = head[root];~i;i = tree[i].next)
while(~scanf("%d", &n))

当然，这种技巧还有很多，哪次找个时间统一做个总结。这里先这样吧。

巴特西

关于HDU 5952的那些事

最新文章

热门文章