算法笔记

其他文章
字数统计: 2.1k字   |   阅读时长≈ 8分钟

⏳本文状态：停止更新 🚩

第1章 如何使用本书

1.3 在线评测系统

  1. PAT乙级
  2. PAT甲级
  3. POJ

1.4 常见的评测结果

  1. 答案正确（Accepted，AC）
  2. 编译错误（Compile Error，CE）
  3. 答案错误（Wrong Answer，WA）
  4. 运行超时（Time Limit Exceeded，TLE）
  5. 运行错误（Runtime Error，RE）
  6. 内存超限（Memory Limit Exceeded，MLE）
  7. 格式错误（Presentation Error，PE）
  8. 输出超限（Output Limit Exceeded，OLE）

第2章 C/C++快速入门

cin和cout消耗的时间比scanf和printf多得多。不要同时在一个程序中使用cout和printf，有时会出问题。

2.1 基本数据类型

  1. 整型： 看到题目要求 $10^9$ 以内或者说32位整数，就用int型来存放，输入输出用%d；如果是 $10^{18}$ 以内或者说64位整数，就要用long long 型来存放，输入输出用%lld。
  2. 浮点型： 不要使用float。碰到浮点型数据都用double，输入用%lf，输出用%f。
  3. 字符型： 字符变量 char c=‘a’；输入输出用%c。字符串 char strl[3] = “a b c”; 输入输出用%s。注意输入无&,为scanf(“%s”,strl)，以 空格 或换行截止。
  4. 布尔型

2.2 顺序结构

  1. 使用 getchar() 和 putchar() 输入/输出字符
    getchar输入单个字符（多个连续字符只捕获第一个），putchar输出单个字符。getchar可以捕获换行符。
  2. typedef long long LL；
  3. 'math.h’常用数学函数：
    • fabs(double x) 取绝对值
    • floor(double x), ceil(double x) 向下取整， 向上取整
    • pow(double r,double p), sqrt(double x) 返回$r^p$，算术平方根
    • log(double x) 以e为底的对数
    • sin(double x), cos(double x), tan(double x) 参数为弧度制
    • asin(double x), acos(double x), atan(double x)
    • round(double x) 返回四舍五入double值，需用int强制转换取整

2.3 选择结构

if语句、switch语句

2.4 循环结构

while语句、for语句、break和continue

2.5 数组

如果数组大小太大（大概 $10^6$ 级别），则需要将其定义在主函数外面，否则会使程序异常退出，原因是函数内部申请的局部变量来自系统栈，允许申请的空间较小；而函数外部申请的全局变量来自静态存储区，允许申请的空间较大。

  1. 对数组中每一个元素赋相同的值。

    • menset(数组名，值，sizeof(数组名))；：添加string.h头文件，速度快，只用它赋值0或-1.
    • fill():赋其他值

  2. 字符数组

    • 直接赋值字符串来初始化（仅限于初始化）

      1
      char str[15] = "Good Story!";

    • %s识别空格作为字符串的结尾。

      1
      scanf("%s", str);

    • getchar()输入，putchar('\n')输出 单个字符 。（不要用它读取字符串，容易忘掉最后的'\0'）

    • gets输入，puts输出 一行字符串 。

      gets用来输入一行字符串（注意：gets识别换行符\n作为输入结束，因此scanf完一个整数后，如果要使用gets，需要先用getchar接收整数后的换行符）；puts用来输出一行字符串，即将一维数组（或二维数组的一维）在界面上输出，并紧跟一个换行。

  3. string.h头文件

    • strlen(字符数组)：第一个\0前的字符个数
    • strcmp(字符数组1, 字符数组2): 比较字符串大小
    • strcpy(字符数组1, 字符数组2): 把字符数组2复制给字符数组1，包括\0
    • strcat(字符数组1, 字符数组2): 把2接到1后面

  4. sscanf和sprintf: 在stdio.h中
    sscanf把字符数组str中的内容以“%d”的格式写到n中（从左至右）

    1
    sscanf(str,"%d",&n);

    处理简单的字符表达式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include <stdio.h>
    int main()
    {
    int n;
    double db;
    char str[100]="2048:3.14,hello",str2[100];
    sscanf(str,"%d:%lf,%s",&n,&db,str2);
    printf("n = %d, db = %.2f, str2 = %s\n",n,db,str2);
    return 0;
    }

    sprintf把n以“%d”的格式写到str字符数组中（从右至左）

    1
    sprintf(str,"%d",n);

2.6 函数

main函数返回0的意思在于告知系统程序正常终止。

2.7 指针

  1. 指针是一个unsigned类型的整数。

    指针最好在定义时赋初值，指针定义写为：

    1
    int *p1=&a, *p2=&b, *p3=&c;

    下面的定义中，只有p1是int*型的，而p2是int型的。

    1
    int* p1, p2;

    指针变量支持p++和p--，常用在数组中。

  2. 引用

    引用 不产生副本 ，而是给原变量起了个别名。对引用变量的操作就是对原变量的操作。（注意：要把引用的&跟取地址符&区分开来，引用并不是取地址的意思） 常量不可以使用引用。

    函数的形参里使用变量的引用，便可以在函数中修改这个变量的值；

    函数的形参里使用变量的地址的引用，便可以在函数中修改某个变量的地址。

    前者指针也可以实现。后者只能通过引用实现。下面代码展示了通过将传入的地址交换来达到交换两个变量的效果（注意引用的类型要和原变量一致）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <stdio.h>
    void swap(int* &p1, int* &p2)  // p1为int*型,所以&p1也为int*型
    {
        int *temp = p1;
        p1 = p2;
        p2 = temp;
    }
    int main()
    {
        int a = 1, b = 2;
        int *p1 = &a, *p2 = &b;
        swap(p1, p2);
        printf("a = %d, b = %d\n",*p1, *p2);
        return 0;
    }

2.8 结构体

  1. 结构体里面不能定义自己本身，但可以定义自己类型的指针变量。

  2. 访问结构体变量内的元素用"." ;访问结构体指针变量内的元素用"->" 。

  3. 结构体构造函数两种方法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    struct studentInfo{
        int id;
        char gender;
        //用以不初始化就定义结构体变量
        studentInfo(){}
        //方法一：下面的参数用以对结构体内部变量进行赋值
        studentInfo(int _id, char _gender){
            id = _id;
            gender = _gender;
        }
        //方法二：构造函数也可以简化成一行
        studentInfo(int _id, char _gender): id(_id), gender(_gender) {}
    }

    这样就可以在需要时直接对结构体变量进行赋值了：

    1
    studentInfo stu = studentInfo(10086, 'M');

2.9 补充

  1. cin、cout

    1
    2
    3
    cin >> db;  // db为double型浮点数
    cin >> c;  // c: char型字符
    cout <<c;
    1
    2
    char str[100];  // 把一整行读入char型数组
    cin.getline(str, 100);
    1
    2
    string str;  // string容器
    getline(cin,str);

  2. 浮点数的比较

    极小数eps, 圆周率$\pi$

    1
    2
    3
    4
    5
    6
    7
    const double eps = 1e-8;
    const double Pi = acos(-1.0);
    #define Equ(a,b) ((fabs((a)-(b)))<(eps)) //==
    #define More(a,b) (((a)-(b))>(eps))  //>
    #define Less(a,b) (((a)-(b))<(-eps))  //<
    #define MoreEqu(a,b) (((a)-(b)>(-eps))  //>= 等号右边易错
    #define LessEqu(a,b) (((a)-(b))<(eps))  //<=

    由于精度问题，在经过大量运算后，可能一个变量中存储的0是个很小的负数，这时如果对其开根号sqrt，就会因不在定义域内而出错。同样的问题还出现在asin（x）当x存放+1、acos（x）当x存放-1时。这种情况需要用eps使变量保证在定义域内。

  3. 复杂度

    1. 时间复杂度：$O(1)<O(\log{n})<O(n)<O(n^2)$ 。对一般的OJ系统来说，一秒能承受的运算次数大概是$10{7}-10{8}$,因此$O(n^2)$的算法当n的规模为1000时是可以承受的，而当n的规模为100000时则是不可承受的。
    2. 空间复杂度：空间一般够用，只要不开好几个$10^7$以上的数组即可。

2.10 黑盒测试

  1. 单点测试

  2. 多点测试

    • while…EOF型: 题目没有给定输入的结束条件，默认读取到文件末尾。scanf函数的返回值为其成功读入的参数的个数。文件结束时，scanf函数会返回-1，C语言中使用EOF（即End Of File）来代表-1.
    1
    2
    3
    4
    5
    6
    7
    // 读入数字
    while(scanf("%d", &n) != EOF){
        // ...
    }
    //读入字符串
    while(scanf("%s", str) != EOF){}  // 方法1
    while(gets(str) != NULL){}  // 方法2

    如果想要在黑框里面手动触发EOF，可以按<Ctrl+Z>组合键，这时会显示一个^Z，按<Enter>键就可以结束while了。

    • while…break型

    当输入的数据满足某个条件时停止输入。两种方法：

    一种是在while…EOF的内部进行判断，满足条件break；

    另一种是把退出条件放到while语句中，令其与scanf用逗号隔开

    1
    while(scanf("&d&d",&a, &b), a||b){}
    • while(T–)型

请我喝杯咖啡吧~

支付宝
微信