在信息学竞赛中，同学们都非常注重各种算法和数据结构的学习。有的同学对最短路径、最小生成树等固定算法记得滚瓜烂熟，分析竞赛题思路头头是道，但是参加竞赛却成绩不理想，每次都说自己失误了，会做的题目粗心没做对，或者是做出来了测试结果却不对。这是为什么呢？其实在信息学竞赛中同学们不仅仅要学会设计算法，还要在有限的时间内实现自己的算法，并且得出正确的结果。这就要求你不仅仅会设计算法，还必须从编程过程的各个步骤下功夫，提高程序正确率，这样才能在竞赛中取得高分。

       信息学竞赛有自身的一些特点，同学们需要在有限的几个小时里完成相当难度的3或4道题目，这个过程包括了审题、设计算法、验证算法、编程、测试和调试等多个环节，时间非常紧。怎样才能加快变成速度，提高编程正确率呢？我们知道，越简单的程序越不容易出错，当一个程序非常的复杂，他的编程、测试、调试难度大大增加。所以，我们可以借鉴软件工程方法中的模块化编程，将一个复杂的程序划分为多个简单模块，基于模块编程，模块独立测试，从而化繁为简，使编程更简单快速，更容易编出正确的程序。

信息学竞赛解题过程详解

       信息学竞赛的解题过程往往包括以下几个步骤，我们逐一分析：

第一步 审题、设计验证算法

       1、

写算法流程，验证算法

注意在这一步一定要确定没有模糊的、为解决的问题再向下进行，否则编写到最后发现有问题解决不了，就会会浪费时间。

第二步 自顶向下分析：划分程序模块，确定存储结构

第三步 逐模块编程->静态检查->测试->调试：在本模块没有测试完以前不要开始编写新模块

对每一个模块逐个求精，确定模块接口，明确存储结构，

第四步 整个程序测试。

模块化模板（c语言描述）

void init();

void solve();

void print();

int main(){

    init();

    solve();

    print();

}

三、例子

1020 麦森数

题目大意：从文件中输入P（1000＜P＜3100000），计算2^P-1的位数和最后500位数字（用十进制高精度数表示）

step1算法分析：

题目肯定要用高精度计算。首先计算位数，可知为trunc(log(2^p))；

然后是计算具体后500位数字，经分析知道，朴素方法时间复杂度为O(p*500)肯定超时，所以思考倍增思想。

算出来2^1 2^2 2^4 2^8 2^16...（后一项等于前一项平方）存储结果在表table中。然后给一个任意的2^p=2^(2^x1+2x2+2^x3...)=2^2^x1*2^2^x2*2^2^x3...，即将p化为2进制数x1x2x3...，然后在在结果表table中查找值来乘。

step2程序模块设计：

输入模块；输出模块；solve模块

存储结构：用整数数组模拟高精度数；table设为高精度数数组，存储2^2^i；计算结果放在result数组中

solve模块流程：

计算2^2^0...2^2^22存入结果表table中；

将p转化为2进制存入数组pa，

for(i=0;i<paweishu;i++){

    if(pa[i]=1){

        multi(result,table[i]);

    }

}

solve模块用到高精度计算，所以可以细化模块multi；

multi模块流程：

void mulit(int a[],int b[])//将a和b相乘结果存入a中

{

    for(i=0;i<500;i++)

        for(j=0;j<500;j++)

           if(i+j<500){

               a[i+j]+=[i]*a[j];

   然后 一遍进位；

}

step3：逐模块编程->测试

关键是multi模块的测试，不妨将位数由500改成5，然后编一个int类型的程序对拍，看看结果是否正确。

竞赛的时候一定要对重点模块进行充分测试。否则很容易出错。

step4:整体测试

将规模改变为更大位数，使用对拍程序测试。

例2：the castle

题目大意：给定一个城堡的平面图，m*n(m,n<=50)。输出房间数目，最大房间的大小，拆掉一面墙能得到的最大房间大小，拆掉那一面墙。

step1：算法分析

城堡的房间数目可以用floodfill求出，同时可以求出最大房间的大小；要求拆掉一面墙得到的最大房间，需要枚举墙，并且墙两边是不同的房间，房间编号在floodfill时记录。这里存储结构非常重要，所以要先确定存储结构。

题目上给的存储结构很好，可以满足程序需求，所以使用题目给定的存储结构：用一个数字表示房间，数字够不够1、2、4、8减表示四面是否有墙。

step2：程序模块

init模块，solve模块，print模块

存储结构：全局变量

int castle[50][50];//存储城堡房间信息

int maxroom;//存储最大房间大小；

int count;//存储房间编号

int roomsize[2500];//存储编号对应的房间大小

 int maxchai;//拆掉墙后最大房间大小

solve模块求精：

for(i=0;i<m;i++)

  for(j=0;j<n;j++)

     floodfill(i,j);

输出房间数，最大房间大小；

for(j=0;j<m;j++)//先枚举列

  for(i=0;i<n;i++){//先枚举西面的墙

     if(西面有墙&&墙两面不同房间){

        temp=roomsize[castle[i][j-1]]+roomsize[castle[i][j]]

        if(maxchai<temp) maxchai=temp

     }

    for(i=0;i<n;i++){//再枚举南面的墙

    ...

    }

  }