备战NOIP2010复赛经验总结分享.doc
4页
[推荐]比赛技巧有些技巧 大家分享关于调试和测试：1.下面是几种比较常见的错误：1．输入输出格式错误2．数据类型错误（在不超内存限制的前提下尽量用大的类型）3．范围检查错误（可以稍稍加大上下界）4．变量名称错误5．漏语句（看事先设计好的变量是否都用上了，然后看每个模块是否实现了应有的功能，是否完成了接口）2.我们应对于每道题设计充分的测试数据,并保留那些比较具有代表性的测试数据,以便于优化的时候比对.3.一定要记住删除屏幕输出！4.最后一定要记住关闭程序中用于临时调试的特殊设置和语句！5.输出数据的每一行（包括最后一行）必须以一个换行符结束，行末不要保留多余空格对于每一道试题，在相应的目录中都有一个格式检查程序来检查输出文件格式的合法性该程序的文件名是：
7.调试的时候，一定要钻输入文件的牛角尖，考虑到各种情况8.调试的时候，常常可以编一个非常非常易编的程序，采用算两次的方法，不过前提是必须保证正确9.Writeln是Fp中最笨但又是最准确的调试方法10.调试时每发现一个错误，都最好浏览一下整个程序，看是否有类似错误，这样非常有效！11.在每一处可以中止程序的地方，都要看一看是否需要close file.12.程序出现不确定性的问题，如对于同样数据，有时死机，有时不死机，但多半都是随机模块有误！13.指针出错常常是出现了Nil^.Next14.递归程序的调试应该使用F7(F8)+Call Stack，尽量不要用F415.不要只顾埋头拉车，要抬头看路当被一两个子程莫名其妙的错误弄得晕头转向的时候，记住：很可能错误在其他地方16.读写文件之前才打开文件，操作完毕立即关闭17.每改完一个错误要想想是否改正确了，是否改彻底了，程序中（特别是有Paste的地方）是否有相同错误18.很多题目最易忽视的就是初状态=末状态的情况，还有初状态和末状态存在可操作的决策如Mars Explorer）19.多考虑一些特例，在这方面认真些，全面些，仔细些，常比多考虑些时空上限划算得多。
20.编函数的时候千万别忘了给函数赋返回值，否则会引起随机性错误21.调试语句一般和上下文保留一空行，最好加上注释，并且一定记住在最后删除22.中途输出后结束一定要记住Halt23.Byte,Shortint调试会以String类型出现，第一位以字符串长处理，遇到#0中止FP和RHIDE中皆如此24.FP中的Extended类型有时候变量值未改变25.调试和测试的时候一定要充分考虑到各种边界和特殊情况26.自测时千万不要忘测数据上限，主要是看是否会超界大半错误均源于此！之后仔细察看Const中的数27.大数组处理很容易出错，所以尽量避免开过大的数组及其调试28.多维数组的调试RHIDE比FP Bug还多，而大数组多元素的查看可考虑使用RHIDE关于算法1．关于复杂度涉及logN的算法.logN常常是因为二分,树,Heap,排序等造成的，而且有一点应该注意到,logN更接近一个常数，而不是N.2．涉及矩阵的统计问题，通常而言，降维策略是非常有效的，而且常常是在外层枚举用土方法，内层枚举使用优化过的方法另外，用O(N*N)枚举出Y1,Y2,然后考察之间夹的矩形是非常常用的方法3．涉及01串的问题，都不要忘记位运算和压缩，同时也要小心。
4．对于判重问题，关注最小表示5．有序化的处理常常比无序的简单，所以，对于想不出算法的题目，先有序化！6．对于涉及子序列之和的问题，如NOI Sequence ,CEOI Parity,B&W,常常化为第一位到某一位的和7．大数据量的题目，有时候分多次读入数据会非常有效8．对于一边明显长于另外一边的矩形问题，常常是基于短边的指数化或者是阶乘算法，而基于长边的O(N)或者O(N*N)的算法9．我们应该注意，许多求割点的题目是求给定两点间的割点，而不是普遍意义上的割点10．没有回溯的搜索是最成功的搜索11．如果你的算法在最大规模的时候要爆，但是最大规模的数据非常难设计，那么就不要管他，设计一个稍次一点的算法就行了12．尽量让程序不做已做过的事和显然没有必要的事，也不要解决无用的子问题和对结果进行无意义的引用13．A*算法的估价函数一般而言要保守些，不要为了速度的一点提升丢失了最优解14．一般情况下，根据数据规模猜算法是非常有效的15．聚焦边界！16．对于流量不超过给定值的最大流问题，注意取流值的时候17．Qsort算法要注意应该先存储选为基点的那个数以后再比较，比较函数一定要保证Compare(A,A)=False!18．我们不仅关心算法的时间复杂度，还要关注最内层的循环到底在干什么。
19．在只涉及乘除的高精度运算中，按因数存储的效率远高于按位存储的效率20．动态规划和递推更多应考虑本问题由哪些已解决子问题构成，而不是考虑本问题对将来哪些问题有贡献21．深度优先搜索候（如求割顶、桥、强连通分支），一定要记住常常题中不止一棵搜索树，也常常有重边！22．优化的时候不要去考虑最坏的情况下是否有太大的意义，只要在大多数情况下有比较明显的作用就行23．对于大规模的Dijkstra算法，如果数据不容易出得很刁的话，用迭代代替堆也是不错的选择用可更新队列实现也不错24．很多图论模型中都要考虑到重边，即使是自己建的图中也有可能出现重边（Knights）25．很多情况下，“不超前”属性的引入可以使复杂度降低一个数量级26．很多时候，由于DP空间开销很大，我们只能保留一个阶段，这时候从大到小的规划时常收效颇佳27．对于数学味较浓的问题，变量的取值范围与计算公式同等重要28．博弈问题从残局或结局出发分析往往会有惊人的发现29．博弈问题胜负局面的相加运算符合Xor（也就是和mod 2）关于数据结构1．涉及单词的问题，常常因为单词的数目多，而且长短不一，出现存储问题，我们可以读入整个数据文件，然后对每个单词记录起止点，这样就充分利用了空间。
2．事实上，链表的速度并不比有序数组高多少，虽然具有O(1)的插入删除复杂度，但是他的查找是O(N)的，而有序数组虽然插入删除是O(N)的，但是查找是O(logN)的而且后者好编些3．多用Longint,少用Integer,反正闲着也是闲着4．传统数据结构的创新性珠联璧合是现代数据结构试题的发展方向比如邻接矩阵+邻接链表5．Joseph类问题中，如果采用静态数组，删除节点可能导致指针错误6．并查集Combine时切记看两个Fa是否相同，否则可能引入圈7．Bignum有时应注意[0]不止256位8．有时候，将链表和数组珠联璧合，如在大规模约瑟夫环中，会受到很好的效果9．在处理小规模链表的问题中，采用静态指针（数组）效果比较理想，便于调试比如多维背包）todo关于FP及程序实现1．有时候要有意采用ln,exp变*为+2．有时与其追求非常精炼代码，还不如笨拙的枚举各种情况，只是注意在Copy&Paste的时候不要出错3．涉及坐标的问题，常常要考虑坐标的定义是基于最小区间的还是基于点的4．Linux中虽然FP IDE中Ctrl失效，但执行程序的时候，Ctrl+Pause或者Ctrl+Z(C)是可以用的5．对于涉及时间的问题，我们必须注意题目中所说的时间是指时间段还是指时间点。
6．凡是分母为变量的除法、Div、Mod都需要想一想是否要判07．永远不要忘记在程序调试完以后改大Const!8．双向搜索与其在精炼的代码上挣扎，还不如就两边分别写过程，只是注意不要乱Copy&Paste.9．链表的实现常常可以采用虚节点的方法，但不要生搬硬套，有时候采用虚节点不一定更好.10．非等差循环用while不用for.11．实数运算永远记住用Zero!（要除了计算几何的一些经典算法，如Graham）12．Gcd，路经压缩，二分查找等很短的递归最好化为非递归形式13．记住，测试数据只是用来发现错误，而不是用来改正错误的，依靠测试数据改正错误，越改越糊涂！14．注意计算几何中Infinite的引入15．很多时候，输入的两个数据并没有说明两者的大小关系！16．注意FillWord和FillDWord分别是Div2,Div4,而后者类型为Dword，可正可负17．枚举的时候不要忘记想一想是用To还是Downto更好18．编写DFS之前一定要先考虑最坏的情况下栈空间是否够用19．Int64不能用Read,也不能直接赋给一个大于Longint的值20．Gcd中，我们不用if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b)，而用if b=0 then gcd:=a else gcd:=(b,a mod b)，因为前者用了两个Mod.21．Gcd,Mod,Div的使用都应该注意正负。
22．交互问题一定要注意接口23．开大数组相当花时间24．A mod 8=A and 725．编之前应该想好需要变的子程，不要做无用功，同时也为反复调用提供思路26．重要结论：a,b取值为{0，1}，则a xor b=(a+b) mod 227．FP中不要使用集合28．对于取余输出，我们用(a-b+c) mod c而不是(a-b) mod c29．一定不要忘记初始化30．在很多情况下，Xor运算可以使代码更简洁高效其它1．在竞赛开始的一个小时之内，参赛选手可以就试题中模糊不清的内容提出疑问提问应使用专用表格，一题一表回答内容应是“是”、“否”、或“无可奉告”等待答案的时间计算在选手竞赛时间之内2．在竞赛期间，参赛选手应及时将自己的文件备份，以便当出现设备故障时迅速恢复文件文件备份应放在/tmp目录之下3．理解题意的时候千万不要想当然，只去做题目说的东西，不要假设任何题目没有提及到的条件4．表达式处理中注意形如(a+b)*(c+d)的括号5．有少数题目不是按照先行后列的方式组织数据的，这一点要格外注意6．记住：非明文禁止者，皆不无可能7．比赛不要轻易删文件，尤其不要加通配符8．文件名切记要使用小写！9．Settextbuf在Linux下面同样有用。
10．要小心，10^8有9位，不是8位9E14是指9*10^14,不是 9^14 !11．Waste memory when it makes your life easier .12．Keep all working versions!13．USE Precomputation !14．Pay attention to Symmetries!常见运行错误002 File not found 005 File access denied 102-105 （检查assign,reset,rewrite）106 Invalid numeric format 200 Division by zero 201 。
