荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: [参赛经验]1
发信站: 荔园晨风BBS站 (Thu Mar 18 15:33:45 2004), 站内信件
设计获胜策略
一个好的取胜之道是制定在竞赛中指导你行动的策略。无论是在好的情况下还是在坏的
情况下，它将帮助你决定你的行动。用这种方法你可以在竞赛中将时间花费在解决编程
问题上而不是试图决定下一步该干什么…这有点像预先计算好你面对各种情况的反应。
心理上的准备也很重要。
竞赛中的策略
首先通读所有的题目；草拟出算法，复杂度，数量，数据结构，微妙的细节，…
集体讨论所有可能的算法 —— 然后选择最“笨”但却可行的算法。（注：请注意这一
点，对参赛选手来说获奖就是唯一目的）
进行计算！（空间和时间复杂度，并且加上实际期望和最坏情况下的数量）
试图证明该算法错误——使用特殊的（退化的）测试数据。
将问题排序：根据你所需付出的努力，将能够最快解决的问题排在前面。（答题的次序
为：以前做过的，容易的，不熟悉的，难的）
编写程序解决一个问题 —— 对每一道题而言，一次一道题
确定算法
构造特殊情况的测试数据
写出数据结构
编写并测试输入子程序（编写额外的子程序来显示数据输入的正确性）
编写并测试输出子程序
逐步细化：通过写注释来刻划程序的逻辑轮廓
一个部分一个部分地填充并调试代码
完成代码使其正常运转，并验证代码的正确性（使用一般情况的测试数据）
试图证明代码错误——使用特殊情况的测试数据来验证代码正确性
逐渐优化——但足够了即可，并且保存所有的版本（使用最坏情况的（即运行时间长的）
测试数据来计算出实际运行时间）
时间安排策略和“故障控制”方案
制定一个计划决定在各种（可预测的）故障发生时的行动；想象你可能遇到的问题并
计算出你所希望做出的反应。核心问题是：“你何时花费更多的时间在调试程序上，你
何时放弃并继续做下一题？”。考虑以下问题：
你已经花费了多长时间来调试它？
你可能有什么样的BUG？
你的算法有错吗？
你的数据结构需要改变吗？
你是否对什么地方可能会出错有一些头绪？
花费较短的时间（20分钟）在调试上比切换去做其他别的事要好；但是你或许能够在45
分钟内解决另一个问题（A short amount (20 mins) of debugging is better than
switching to anything else; but you might be able to solve another from
scratch in 45 mins.）
你何时返回到一个你先前放弃的问题？
你何时花费较多的时间优化一个程序，你何时放弃当前优化工作而切换去作其他事？
从这点考虑出去（Consider from here out）——忘记先前的努力，着眼于将来：你如
何才能就你目前所有的抓住下一个小时。
在你上交你的答案之前列出一个校验表：
在竞赛结束前五分钟结束编写代码（Code freeze five minutes before end of contest
）。
将所有的声明关闭。
将调试输出关闭。
确认输入输出文件名正确。
确认输入输出格式正确。
重新编译并再测试一次。
将文件以正确的文件名复制到正确的位置（软盘）。
提示和技巧
如果可以就用暴力法（即穷举法）解决 （注：居然将这条作为技巧，可见竞赛的目的就
是获奖，为此要“不择手段”。）
KISS(=Keep It Simple, Stupid)：简单就好！（KISS: Simple is smart!）
提示：注意限制（在问题陈述中指明）
如果可以给你带来方便的话就浪费内存（假如你能侥幸逃脱规则处罚的话）
不要删除你额外的调试输出，将它注释起来
逐渐地优化，足够了即可
保留所有的工作版本
编码到调试：
注意留有空白（whitespace is good）
使用有意义的变量名
不要重复使用变量
逐步细化
在写代码之前先写注释
有可能的话尽量避免使用指针
避免使用麻烦的动态内存：静态地分配所有的东西。
尽量不要使用浮点数；如果你不得不使用，在所有使用的地方设置允许的误差（绝对不要
测试两个浮点数相等）
如何写注释：
不要写得太长，简洁的注解就可以了
解释复杂的功能：++i; /* increase the value of i by 1*/ 这样的注释是毫无意义的。
解释代码中的技巧
将功能模块划定界限并且归档（Delimit & document functional sections）
注释要好像是写给某个了解该问题但并不了解程序代码的聪明人看的
对任何你不得不考虑的东西加以注释
在任何你看到了以后会问“他到底干什么用”的地方加注释（Anything you looked at
even once saying, "now what does that do again?"）
总是注释数组的索引次序
记录你每一次竞赛的情况：成功之处、犯的错误，以及何处你可以做得更好；利用这些记
录来改进你的策略。
复杂度
基础和阶符号
复杂度分析的基本原理围绕着符号大“O”，例如：O(N).这意味着算法的执行速度或内存
占用将会随着问题规模的增倍而增倍。一个有着O(N 2)的算法在问题的规模增倍时其运行
时间将会减慢4倍（或者消耗4倍的空间）。常数时间
或空间消耗的算法用O(1)表示。这个概念同时适用于时间和空间；这里我们将集中讨论时
间。
一种推算一个程序的O( ) 运行时间的方法是检查它的循环。嵌套最深的（因而也是最慢
的）循环支配着运行时间，同时它也是在讨论O( ) 符号时唯一考虑的循环。有一个单重
循环和一个单层嵌套循环（假设每个循环每次执行N次）的程序的复杂度的阶是O(N
2)，尽管程序中同时有一个O(N)循环。
当然，递归也像循环一样计算，并且递归程序可以有像O(b N)， O(N!)， 甚至O(N N)的
阶。
经验法则
在分析一个算法以计算出对于一个给定的数据集它可能要运行多长时间的时候，第一条经
验法则是：现代（1999）计算机每秒可以进行10M次操作。对于一个有五秒钟时间限制的
程序，大约可以处理50M次操作。真正优化的好的程序或许可以处理2倍甚至4倍于这个数
目的操作。复杂的算法或
许只能处理这个数目的一半。
640K确实是苛刻的内存限制。幸运的是，1999-2000赛季将是这个限制的最后一次起作用
。
2的十次方 约等于1000
如果有k重嵌套的循环，每重大约循环N次，该程序的复杂度为O(N^k)。
如果你的程序有l层递归，每层递归有b个递归调用，该程序复杂度为O(b^l)。
当你在处理有关排列组合之类的算法时，记住N个元素的排列有N!个，N个元素的组合或N
个元素组成的集合的幂集的有2^n个。
对N个元素排序的最少时间是O(NlogN)。
进行数学计算！将所有的数据加起来。（Plug in the numbers.）
例子：
一个简单的重复N次的循环复杂度为O(N)：
1 sum=0
2 fori=1ton
3 sum=sum+i
一个双重嵌套循环的复杂度通常为O(N 2)：
#fill array a with N elements
1 fori=1ton-1
2 forj=i+1ton
3 if(a[i]>a[j])
swap(a[i],a[j])
注意，虽然这个循环执行了N×(N+1)/2 次if语句，但他的复杂度仍然是O(N 2)，因为N加
倍后执行时间增加了四倍。
解决方案的范例
产生器 vs. 过滤器
产生大量可能的答案然后选择其中正确的（比如8皇后问题的解答），这样的程序叫做过
滤器。那些只产生正确答案而不产生任何错误节点的叫做产生器。一般来说，过滤器较容
易（较快）编程实现但是运行较慢。通过数学计算来判断一个过滤器是否足够好或者是否
你需要尝试制作一个产生器。
预先计算
有时生成表格或其他数据结构以便快速查找结果是很有用的。这种方法叫做预先计算（在
这里用空间换取时间）。你可以将需要预先计算的数据和程序一起编译，在程序开始时计
算；也可以干脆记住预先计算出的结果。比如说，一个程序需要将大写字母转化为小写字
母，可以不需任何条件
地利用一个表格进行快速查找来实现。竞赛题经常要用到素数——生成一长串素数在程序
中某处使用通常是很实用的。
分解（编程竞赛中最困难的事）
虽然在竞赛中经常使用的基本算法不超过20种，但是某些需要将两种算法结合才能解决的
组合型问题却是很复杂的。尽量将问题不同部分的线索分离开来以便你可以将一个算法和
一个循环或其他算法结合起来以独立地解决问题的不同部分。注意，有时你可以对你的数
据的不同（独立）部分重复使用相同的算法以有效地改进程序的运行时间。
对称
许多问题中存在着对称（例如，无论你按哪一个方向，一对点之间的距离通常是相同的）
。对称可以是2路的（？？原文是2-way），4路的，8路的或是更多的。尽量利用对称以减
少运行时间。
例如，对于4路对称，你只需解决问题的四分之一，就可以写下4个结果，这四个结果和你
所解决的一个结果是对称的（注意自对称的解答，他当然只应该被输出一次或两次）。
正向 vs. 逆向
令人惊讶的是，许多竞赛题用逆向法解决比正面突破要好得多。以逆序处理数据或构造一
种基于某种非明显的方式或顺序检索数据的突破策略时，要特别小心。
简化
某些问题可以被改述为一个有点不同的其他问题，这样你解决了新问题，就已经有了原始
问题的答案或者容易找出原始问题的答案；当然，你只需解决两者之中较容易的那个。另
外，像归纳法一样，你可以对一个较小的问题的解答作一些小小的改变以得到原问题的完
整答案。
-- Long long ago,there is a hero stand at the edge of the land......
--
※ 修改:·kaman 於 Mar 18 15:54:54 修改本文·[FROM: 192.168.111.157]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.157]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店