星期二, 十月 31, 2006

A题细节

  • 更新最值的时候注意要将最开始的值和最后可能更新的值计算在内。
  • 注意重复的东西 e.g.求最短路,最大流时注意处理重边 坐标的重复
  • 运算符的优先级问题 e.g.(...&&...||...) 还是 (...&&(...||...)) ?
  • 使用STL时应注意其特性 e.g.priority_queue是大根堆,容器为空时注意.top() *xxx.begin()等可能会出问题
  • 函数最后该返回值的不要忘记了
  • 0,-1,1之类很牛的数注意特殊处理 e.g.高精度时候的0,整数被0除,表达式处理时的1,-1
  • const东西的时候不要弄丢了 e.g.pow2[]={...}
  • 局部变量和全局变量重名时不要搞混了
  • 变量,常量名不要写错 e.g.i j, 1 2
  • ++和--,==和=不要写混了 e.g.for(i=n-1;i>=0;i--).../*AC*/ for(i=n-1;i>=0;i++).../*TLE RE WA*/
  • 注意非法询问等特殊数据 e.g. LCA不存在结点
  • 数组开足够大
  • 不同语言默认或常用数组起始下标可能不一样,如Pascal是1,C是0,这样读入输出是否加减1容易出错 e.g. for(int i=0;i<n;i++)printf("%d\n",order[i]+1);

星期三, 十月 04, 2006

某些算法及程序常数的细节优化

有的时候,当两个算法一样的程序,看着别人能够很快地通过,而自己却总是卡着通过或者直接TLE,心中总是十分不爽。近段时间经多次TLE的教训后,我将一些经验写在这里。
1.程序常数的细节优化

  • 系统分配内存的时间往往为我们所忽略,当你为你的程序超过总时限而郁闷时,试着减少内存使用吧。比如DP时使用滚动数组……
  • 数组寻址所用的时间在维数较高时会使常数较大(乘法造成的),在部分情况下可以用“指针行走”来优化常数。
  • 除法运算也是常数很大的操作,能减少时就减少。
  • 递归时call,ret会很耗费时间,适当时可以考虑非递归。

2.算法的细节优化

  • 最小生成树的Krusckal算法当树的个数合并到只有一个时及时跳出枚举边的循环
  • Bellman-Ford算法当没有距离更新时跳出,并且最多只用进行点数-1次枚举边的松弛操作

星期日, 九月 24, 2006

Introduce to My Blog :)

经过长时间的考虑,我最终决定用blogspot的博客。它看起来很清爽,而且操作起来也不麻烦。这个博客取名Dream Segments,就当我把我大脑中的碎片丢在了这里,让它们自己发芽。

下面是我的Blog的大体结构:

  • Vertex (学习note)
  • -Report : 报告
  • -Summary : 总结
  • Edge (我大脑里面的一些东西)
  • -Segment : 胡思乱想
  • -Literature : 文字
  • Face (生活里的事情)
  • -Life : 生活流水账
  • -Others : 杂文