算法竞赛注意事项

基本算法注意事项

  • 在算法竞赛中,每行输出均应以回车符结束,包括最后一行。 除非特别说明,每行的行首不应有空格,但行末通常可以有多余空格。 另外,输出的每两个数或者字符串之间应以单个空格隔开。
  • 尽量用const关键字声明常数
  • 浮点运算可能存在误差。 在进行浮点数比较时,应考虑到浮点误差,为了减小误差的影响,一般改成四舍五入,即floor(x+0.5)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include<stdio.h>
    #include<math.h>
    int main()
    {
    for(int a = 1; a <= 9; a++)
    for(int b = 0; b <= 9; b++)
    {
    int n = a*1100 + b*11; //这里才开始使用n,因此在这里定义n
    int m = floor(sqrt(n) + 0.5);//向左取整,floor(3.9)即为3.0
    if(m*m == n) printf("%d\n", n);
    }
    return 0;
    }
  • C99并没有规定int类型的确切大小,但在当前流行的竞赛平台中,int都是32位整数,范围是-2147483648~2147483647
  • long在Linux下的输入输出格式符为%lld,但Windows平台中有时为%I64d。 为保险起见,可以用后面介绍的C++流,或者编写自定义输入输出函数。
  • 可以使用time.h和clock()函数获得程序运行时间。 常数CLOCKS_PER_SEC和操作系统相关,请不要直接使用clock()的返回值,而应总是除以CLOCKS_PER_SEC。为了避免输入数据的时间影响测试结果,可使用一种称为“管道”的小技巧:在Windows命令行下执行echo 20|abc,操作系统会自动把20输入,其中abc是程序名。
    1
    printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
  • 比较大的数组应尽量声明在main函数外,否则程序可能无法运行
  • 如果数组a和b都是浮点型的,复制时要写成“memcpy(b,a,sizeof(double)*k)”。 另外需要注意的是,使用memcpy函数要包含头文件string.h。 如果需要把数组a全部复制到数组b中,可以写得简单一些:memcpy(b,a,sizeof(a)),另外“memset(a,0,sizeof(a))”的作用是把数组a清零
  • 注意,“scanf(“%s”, s)”遇到空白字符会停下来
  • strchr的作用是在一个字符串中查找单个字符
  • C语言中的gets(s)存在缓冲区溢出漏洞,不推荐使用。 在C11标准里,该函数已被正式删除
  • p101的UVa1583、p102的UVa1584、p118组合数(?)
  • 一方面避免了每次重复计算sqrt(n),另一方面也通过四舍五入避免了浮点误差——正如前面所说,如果sqrt将某个本应是整数的值变成了xxx.99999,也将被修正,但若直接写m = sqrt(n),“.99999”会被直接截掉
    1
    int m = floor(sqrt(n) + 0.5);
  • 在运行时,程序会动态创建一个堆栈段,里面存放着调用栈,因此保存着函数的调用关系和局部变量;局部变量也是放在堆栈段的。 栈溢出不一定是递归调用太多,也可能是局部变量太大。
  • 声明数组时,数组大小可以使用const声明的常数(这在C99中是不允许的)。 在C++中,这种写法更为推荐,因此本书后面的代码中一律采用这样的写法,而不是用#define声明常数