迴夢仙游

初中的时候，曾听人说起过仙剑．见过前排的mm花痴在《仙剑奇侠传》中演李逍遥的胡歌……听过哥们唱着《逍遥叹》装成熟……当时，几乎没机会接触游戏、电视剧的我，对于周围无论以什么原因而成为仙剑粉丝的人都觉得很奇怪，是什么原因让仙剑如此吸引力？

懵懵懂懂的度过了初中三年，我以比统招线高一分的中考分数进入了七中，然后考上了理科实验班，并参加了信息学竞赛。于是从高一到高三，我几乎是每天都要和我的ThinkPad亲密接触n个小时。随着初中的结束，游戏、电影、网络小说等便随着信息学竞赛进入了我的生活。

还记得高一上期那次期末考试，我考了班上倒数第二@_@，和我入学摸底考试第三名的成绩“进步”了不少。在信息学竞赛上投入大量时间是我那次考砸的原因之一，还有个我以往从没告诉别人的原因……每次考试的时候，我都在想着考试结束之后的仙一时间。当年的小机房（我们四五个人专门弄竞赛的小房间），遍地是光盘和垃圾。黄磊、洪骥、冯国栋和我还曾经在漫天漫地的废物中找出了生化危机3三的光盘，并在当时还存在的两台破烂台式机中那台没装rh的机子上玩过。在期末考试前不久，我们几个从网上下了个仙一，然后开始玩，我经常在旁边看他们操作，就像看电影一样。和其他游戏相比，剧情适合青春期的我们，并且蕴含了深厚中华传统文化的仙一，深深的吸引了我。于是我很快把根据仙一剧情改编而成的电视连续剧全集下载下来。在那个寒假参加四川集训队选拔的时候，我还再看曾经红极一时的《仙剑奇侠传》（话说洪骥是刘亦菲的粉丝……）。

高二上期，黄磊在他的电脑上装了个仙二，由于和仙一剧情有紧密的联系，我便也当电影看了，后来还经常把黄磊的电脑霸占了玩。黄磊装的那个仙二有Debug模式，再加上存档修改器……我们很快就翻版了。黄磊在那段时间还把他n年前买的新仙剑（3D版的仙一，加了几个神奇的结局）装了一个来玩。在高二那个寒假我们几个去国家冬令营观摩的路上，我还从黄磊那里copy了一个仙三，然后一直玩到省集训队选拔之前翻版了^_^。

高二下期冲刺竞赛，其中一直激励我的一件事情就是——在NOI期间，8月1日，仙四开始发售！最后，我如愿以偿的拿了个金制“巧克力块”，也拿到了一套正版仙四……

仙剑的剧情，友情、亲情、爱情，前世、今生、来世……无一不在细微之处让我感触万分。回首这三年仙剑伴我走过的时光，我终于知道了中国第一RPG的魅力所在。

p.s. 那张图片是WC2007时的船政景点(像不像锁妖塔？)

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);
  

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

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

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

2.算法的细节优化

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