Ø       复赛的命题

1．  准循大纲：考察常用的数据结构和基本算法；

2．  考察能力：包括阅读理解能力、构建数学模型的能力、程序编码与调试能力、程序的时空性能分析和测试数据的生成能力、各种知识的综合应用能力等；

3．  有区分度：一般3-4题，复赛题目的特点是：1-2题算法和数据结构比较明显、或者和数学关系比较大的题目，得率比较高；1题好上手，但程序量要大一点或数据规模大的题目，考虑全面、得满分也不容易；还有1题一般是搜索、或者算法不明显、或者用到复杂高深一点的数据结构的题目，难度较大。但顺序不一定！！！

Ø       如何备战复赛

1.       做做以往历年的竞赛题和网上的模拟题，熟悉比赛的题型和要求，找出自己的不

足，加强训练；

2.       增强自己编写代码和调试的熟练程度，提高做题的时间和节奏感；

3.       熟练掌握文件的输入/输出操作，新大纲中对复赛的要求；

4.       提高自己设计测试数据的能力；

5.       提高自己做题的正确率（分数/时间）；

6.       算法方面：递推、递归、动态规划、贪心、搜索（初中到回溯就差不多了）基本

上是必考！！！对一些经典问题和算法，一定要熟练的不能再熟练；

7.         数据结构方面：字符串经常考，树（尤其二叉树）、图的基本算法（最短路径、最

小生成树等）；

Ø       复赛注意事项

1.              认真审题，尤其要注意问题的规模（数据范围），从某种意义上说，问题规模也暗示了你可能的算法。数据小，也许是搜索派上用场的时候；数据大了，可能只能考虑动态规划，数学方法等高算法了。

2.              正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目，做到心中有数！注意：题目的难易对所有人是公平的，只要最大限度地发挥自己的水平，不要有包袱，考出自己的最佳成绩。

3.              正确地选择题目去做（最擅长、最简单的先完成），合理地安排时间和解题顺序。

4.              复赛中：一定提高正确率！！！解题速度是其次。

5.              复赛考查的算法并不困难，选手在实现上的问题往往要多一些。
建议大家：

1）  充分利用草稿纸，不要对自己的“心算能力”太自信！编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。我认为这样不好，做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉”来编程往往是漏洞百出。比如初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低（命题者的陷阱），而程序编了大半才发现，时间浪费了不说，还影响了信心和发挥。

2）  做一些复杂的题目，编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视这一点）。

3）  多测试：样例数据、极限（小大）数据、特殊数据，分析能否在规定的时空范围内出解，精度是否够，格式是否对，输入输出文件名、格式是否正确等。

4）  不一定要拿满分，有些题目如果你很拿手，也肯定能做对，那么一定要保证拿满分；但有些题目，在有限的竞赛时间里，你很难拿满分，或者自己觉得没有足够的时间和信心，没有好的方法，那么在很少的时间内用投机取巧的方法（如贪心等）能得到不错的分数，也是一种很大的成功。

数组

一维数组

定义格式：

类型说明符   数组名[常量表达式]；

一维数组的初始化

1.int i[5]={0,1,2,3,4};

2.int i[10]={0,1,2,3,4};

3.int i[]={0,1,2,3,4};

4.（字符数组）  char c[]=”this is a C program.”;

char c[]={‘t’,’h’,’i’, }；

注意字符数组与字符串数组的区别。

二维数组

定义格式：

类型说明符   数组名[常量表达式][常量表达式]；

二维数组的初始化

1.int i[2][3]={0,1,2,3,4,5};

2.int i[2][3]={{2,4,6},{1,3,5}};

3.int i[2][3]={{11},{22,33}};

[例]

打印杨辉三角形

#include<stdio.h>

main()

{

int i,j,yh[6][6];

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

{

             yh[i][0]=1;yh[i][i]=1;

}

for (i=2;i<6;i++)

             for (j=1;j<i;j++)

                  yh[i][j]=yh[i-1][j-1]+yh[i-1][j];/*杨晖三角中间的每一个元素的值均为前一行同一列元素和前一行前一列元素值之和*/

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

      {

for (j=0;j<=i;j++)/*循环嵌套控制打印内容成三角形*/

                    printf(“%4d”,yh[i][j]);

printf(“\n”);/*打印完每一行内容后打印换行符*/

}

}

作业：计算灯的开关状态——有N盏灯放在一排，从1到N依次顺序编号，有N个人也从1到N依次编号。1号将灯全部关闭，2号将凡是2的倍数的灯打开；3号将凡是3的倍数的灯作相反处理（该灯如为打开的，则将它关闭，如关闭的，则将它打开）。以后的人都和3号一样，将凡是自己编号倍数的灯作相反处理。试计算第N次操作后，哪几盏灯是亮的。（0—表示灯是打开的，1—表示灯是关闭的）

（文件：8.c）

#include<stdio.h>

main()

{

      int n,i,j,a[100];

      scanf("%d",&n);

      for (i=1;i<=n;i++)

          a[i]=0;/*为数组元素赋初值，可换用“memset(a,0,sizeof(a));”*/

      for (i=1;i<=n;i++)

      {

          j=i;

          while (j<=n)

          {

                a[j]=!a[j];/*取反操作*/

                j=j+i;

          }

      }

      for (i=1;i<=n;i++)

          if (!a[i])

             printf("%3d",i);

      printf("\n");

}

循环结构

for循环

for (表达式1;表达式2;表达式3)

语句；

注意！: for循环中，表达式可以省略但分号不可省，即，最简形式：for(;;)此循环循环体中要有“break”适时推出，否则为死循环。

while 循环 ，当型循环

while（表达式）

语句；

do-while 循环 ，直到型循环

do

语句

while（表达式）

作业：

1、打印水仙花数，所谓水仙花数是指一个三位数，其各位数字立方和等于该数本身。例如，153是一个水仙 花数，因为153=1*1*1+5*5*5+3*3*3

2、求1！+2！+3！+……+n!

3、Nocomachns定理——任何一个N3一定可以表示成n个连续的奇数和。输入n,输出N3对应的表达式。

1.  （文件：5.c）

#include <stdio.h>
main ()
{
       int i,g,s,b,sum;
       for (i=100;i<=999;i++)
       {
           b=i/100;/*求百位数*//*C中当/两边都为整形变量时，得数也是整数*/
           s=(i-b*100)/10;/*求十位数*/
           g=i%10;/*求个位数*/
           sum=g*g*g+s*s*s+b*b*b;/*注意g3不可写成g^3,^为异或运算符。*/
           if (sum==i)
              printf("%d\n",i);
       }
}/*拆分球的各个位上的数，求立方和*/

2.   （文件：6.c）

#include <stdio.h>
main()
{
    int i,n;
    long int t,sum;
    scanf("%d",&n);
    for (i=1,t=1,sum=0;i<=n;i++)
    {
           t*=i; /*利用n!=(n-1)!*n计算n!*/
           sum+=t;/*累加求和*/
    }
    printf("1!+2!+…+%d=%d",n,sum);
}/*后面还将利用函数求阶乘*/

3.   （文件：7.c）

#include <stdio.h>

main()

{

      long int i,n,a;

      scanf("%d",&n);

      a=n*(n-1)+1;/* Nocomachns定理，起始的奇数为n*(n-1)+1*/

      for (i=1;i<=n-1;i++)

      {

          printf("%d+",a);

          a=a+2;

      }

      printf("%d",a);

}/*注意常用算法*/

选择结构

if语句的三种形式

if (表达式) 语句；

if （表达式）语句1；

else 语句2；

if （表达式1） 语句1；

else if （表达式2） 语句2；

else if （表达式3） 语句3；

……

else 语句n;

[例]：

#include<stdio.h>
　main()

{

　　long int a，b，c，d，sum；
　　 scanf (“%d,%d,%d,%d”,&a，&b，&c，&d)；
　　 a=a % 23：
　　 b=b % 28；
　　 c=c % 33；
　　 sum=a*5544+b* 14421+c*1288-d;
　　 sum=sum+21252;
　　 sum=sum % 21252;
　　 if (sum==0)
　　　　sum=21252;
　　printf(“%d”,sum)
　 }

输入：283 102 23 320 输出：8910

作业：1、判断闰年。输入年份，输出该年是否为闰年的信息

2、输入三个整数，按从小到大的序顺输出

1 （文件3.c）

#include <stdio.h>
main()
{
    int a;
    char b;
    printf("请输入年份:");
    scanf("%d",&a);
    if ((!(a%4)&&a%100)||(!(a%400))) /*注意"！"的优先级高于%，！a%4,先计算！a*/
        printf("%d年是闰年\n",a);
    else
        printf("%d年不是闰年\n",a);
}/*闰年年号能被4整除且不能被100整除或能被400整除*/

2 （文件4.c）

#include <stdio.h>
main()
{
    int a,b,c;
    while (1==1)
    {
        scanf("%d %d %d",&a,&b,&c);
        if (a>b)
            if (b>c)
                printf("%d>%d>%d\n",a,b,c);/*a>b>c*/
            else/*b<c*/
                if (a>c)
                    printf("%d>%d>%d\n",a,c,b);/*a>c>b*/
                else/*a<c*/
                    printf("%d>%d>%d\n",c,a,b); /*c>a>b*/
        else/*a<b*/
            if (a>c)
                printf("%d>%d>%d\n",b,a,c);/*b>a>c*/
            else/*a<c*/
                if (b>c)
                    printf("%d>%d>%d\n",b,c,a);/*b>c>a*/
                else/*b<c*/
                    printf("%d>%d>%d\n",c,b,a); /*c>b>a*/
    }
}/*三个数两两相比*/