算法竞赛入门经典（第2版）—前几章总结

第一章

零碎知识点记录

• 整数值用%d输出，实数用%f输出。double类型一般使用%lf来输入和输出，但在C99中输出用%f。
• 一般输出均以回车符结束（包括最后一行），通常行末可以有多余空格，但个别题目不行。最好读清题意，确定题目的输入输出格式。
• 输出\应该用printf（"\n"），而输出%d两个字符则可以用%c输出两个变量（其值分别为%和d）。
• int类型的取值范围-2³¹ 到 2³¹-1（9个0）。long long类型的取值范围-2⁶³ 到 2⁶³-1(18个0)，并且输入输出为%lld。C语言中的int和long long

第2章

零碎知识点记录

• floor函数：一个小数向下取整，返回double类型的数。因为double类型直接转int是直接截取整数部分，所以可以使用int a = floor(x+0.5)来实现四舍五入的效果。
• 不要在比较两个double类型是数是否相等，因为有浮点误差，但可以比较大小。
• 10^-6可以表示为1e-6。
• 在计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每一步运算后对n取余，结果不变。
• scanf函数有返回值，返回的是成功输入的变量个数。即scanf("%d", &x)==1。
• 在进行测试while(scanf("%d", &x)==1)，可能会因为输入个数不确定而无法测试，但是在Windows下先按Enter键，再按Ctrl+Z键，最后按Enter键即可结束。在Linux下，输入完毕后按Ctrl+D键即可结束输入。
• cout中输出小数点后4位：cout << fixed << setprecision(4) << value << endl;使用cout标准输出控制小数点后位数
• next_permutation（a, a+n)：按字典序获取a的全排列。在使用该函数时，一般先使用sort(a, a+n)来获得a的最小字典排序，并且该函数一般与do-while循环有关。 注意其头文件为algorithm。

#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)&&n){
        int a[1000];
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        do{
            for(int i=0;i<n;i++)
                printf("%d ",a[i]);
            printf("\n");
        }while(next_permutation(a,a+n));
    }
    return 0;
}

• 比较大的数组应该尽量声明在main函数外，否则会栈溢出，程序无法运行。
• 从数组a复制k个元素到b数组中：memcpy(b, a, sizeof(int)*k)。将数组a全部复制到b数组中：memcpy(b, a, sizeof(a))。注意其头文件为string.h或cstring。
• &&是短路运算，x+1<n && !a[x]，当x+1>=n时，不会运算后面的式子。
• strchr（char *s, char c）：表示查找c在s字符串中第一次出现的位置（返回其指针），如果未找到则返回NULL。strrchr（char *s, char c）：表示查找c在字符串s中最后一次出现的位置（返回其指针），如果未找到则返回NULL。

韩信点兵问题

参考博文：韩信点兵算法
算法：
当除数分别是3、5、7时,

• 用70乘以用3除的余数
• 用21乘以用5除的余数
• 用15乘以用7除的余数
• 然后把这三个乘积相加
  加得的结果如果比105大,就除以105,所得的余数就是满足题目要求的最小正整数解。也就是说一定会有最小正整数解，但如果最小正整数解大于所给的范围则输出无解。

printf中固定宽度和精度的输出

参考博文：C语言（C++）中：详解floor函数、ceil函数和round函数
printf格式字符串中，与宽度控制和精度控制有关的常量都可以换成变量，方法就是使用一个*代替那个常量，然后在后面提供变量给*，同时变量为负时表示左对齐，为正时表示右对齐。

#include <stdio.h>
int main(void) {
    char s[] = "abcdefg";
    int i = 12345;
    double d = 123.45678;

    printf("%s\n", s);//abcdefg，输出字符串
    printf("%.*s\n", 3, s);//abs，输出字符串前三个字符
    printf("%#.8x\n", s);//0x006dfef8，输出十六进制地址
    printf("%#p\n\n", s);//0x6dfef8，取地址

    printf("%d\n", i);//12345，正常输出
    printf("%*d\n", 10, i);//     12345,控制宽度为10，单右对齐
    printf("%0*d\n\n", 10, i);//0000012345，补0

    printf("%f\n", d);//123.456780，默认六位小数
    printf("%.*f\n", 3, d);//123.457，三位小数
    printf("%20.10f\n", d);//     123.4567800000,表示总宽度为20位，其中小数部分占10位。
    printf("%*.*f\n\n", 20, 10, d);//     123.4567800000,
    return 0;
}

博文链接：
C语言之字符串函数相关总结
C/C++常用输入输出函数总结