UVA小结

总结一下最近在uva和spoj上做的题目。很少,反正就是挑最简单的开始做。

uva上只做了3道题目。

100 - The 3n + 1 problem

没任何难度的入门题,完全就是适应下如何使用这个系统。按照题目所写的,反复循环即可。

102 - Ecological Bin Packing

穷举所有可能性即可。

  struct Check{
    const char* name;
    unsigned char pos[9];
  };

  //B1 G1 C1 B2 G2 C2 B3 G3 C3                                                                                                      
  const static Check checks[]={
    {"BCG",{1,0,0,0,0,1,0,1,0}},
    {"BGC",{1,0,0,0,1,0,0,0,1}},
    {"CBG",{0,0,1,1,0,0,0,1,0}},
    {"CGB",{0,0,1,0,1,0,1,0,0}},
    {"GBC",{0,1,0,1,0,0,0,0,1}},
    {"GCB",{0,1,0,0,0,1,1,0,0}},
    {NULL,{0,0,0,0,0,0,0,0,0}}
  };

但是我花了0.055秒才完成。

112 - Tree Summing

先解析成一棵树,然后做二叉树遍历,把所有叶子都找出来,然后从叶子到根回溯一遍。写完,提交,运行时间0.089秒。

然后我想,我为什么非得做二叉树遍历呢?我在解析这个二叉树的时候,需要构造Node,那么这个时候,我把所有的leaf Node都放在一个容器(vector或者list)里,到时候直接遍历这个容器不就行了?好吧,改代码,提交。运行时间0.132毫秒,更长了啊!为什么?

我发现花了大量的时间在vector的push_back方法里。我并不知道最多会有多少Node,所以就不能给这个vector一次性预留足够的内存。

然后我想了一下,给每个Node加了一个next指针。然后用这个next指针把他们串起来。运行时间0.085。与优化前完全一样啊… 后来我想是这样,在parse的时候,我不能准确的判断一个node是不是leaf node,我只能在遇到)的时候,判断这个node是不是有right child,然后把没有right child的都串起来。于是我几乎把一半的node都串起来了。和之前做二叉树遍历差不多。而我60%-70%的时间都花在了parse tree上。

然后我看,啊,好多时间都花在new Node()上了啊 。于是我就做了一个对象池。在我本机测试,确实速度快了很多。但是在uva系统上跑,花费时间反而增加到1.279秒。经我测试,如果在程序中使用了大的静态数组,那么在uva的系统上会显著的增加运行时间。虽然这个数组只占几MB内存。

然后spoj上就做了一道题,PRIME1

生成指定范围内的质数。第一次我用除法的方式挨个test是不是质数,然后时间就超了。稍微想了想,以前课本里讲过晒法。试了一下,果然快了很多倍。

接下来想多做点动态规划的问题。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥