使用 C 语言对内存的操作解题 P1042

kai_Ker · 2022-08-18 20:57:56 · 个人记录

这道题用一些循环便可解开，难度不大，但如果我们使用 C 语言对内存的细致操作来解题，则可以避免大多数的循环，并且更加 优雅 。

首先先来了解一些预备知识：

• C 语言中并没有 bool 类型，也没有 true 和 false，除非你使用 <stdbool.h> 头文件）。_Bool 类型占用一个字节，用 1 和 0 来表示真假。
• 使用 malloc 函数（需要包含头文件 <malloc.h>）来分配内存，函数接受一个参数，表示要分配的内存大小；函数返回 void * 类型，需要强制类型转换成 _Bool * 类型。内存大小在此题中为 sizeof(_Bool) * (l + 1)
• 使用 memset 函数（需要包含头文件 <string.h>）来设置一段连续的内存，函数接收三个参数，依次为起始位置地址、设置的内容（实际取后八位，即一个字节）、设置内存的长度（字节数），注意，memset 函数是按字节分配的，会将这段内存的每个字节设置成目标内容。在此题中的使用见代码。

首先导入头文件：

#include <malloc.h>   // 分配内存
#include <stdio.h>    // 标准输入输出
#include <string.h>   // 使用 memset 设置内存

然后定义变量，接收长度与数据组数：

int l, m;
int t1, t2;  // 临时变量，存放每一段的端点
scanf("%d %d", &l, &m);

接下来是申请内存空间，并将每个字节设置为 1，表示栽有树：

_Bool *arr = (_Bool *)malloc(sizeof(_Bool) * (l + 1));
memset(arr, 1, sizeof(_Bool) * (l + 1));
// 这里是 l + 1，因为有 l + 1 棵数

然后循环接收端点，并将这些端点所对应的内存设置为 0：

for (int i = 0; i < m; ++i)  // 理论上 ++i 比 i++ 稍快一点
{
    scanf("%d %d", &t1, &t2);
    memset(arr + t1, 0, sizeof(_Bool) * (t2 - t1 + 1));
    // 注意，指针的加减，会被乘上所指向数据的字节数
    // 比如 int 型指针加 1，地址实际上加了 4（int 一般是 4 个字节）
}

最后只要再遍历一遍这段内存空间，统计有几个 1 就可以了：

int res = 0;
for (int i = 0; i <= l; ++i)  // 这里是 <= 不要弄错了
{
    res += arr[i];
}

完整 AC 代码如下：

#include <malloc.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    int l, m;
    int t1, t2;
    scanf("%d %d", &l, &m);
    _Bool *arr = (_Bool *)malloc(sizeof(_Bool) * (l + 1));
    memset(arr, 1, sizeof(_Bool) * (l + 1));
    for (int i = 0; i < m; ++i)
    {
        scanf("%d %d", &t1, &t2);
        memset(arr + t1, 0, sizeof(_Bool) * (t2 - t1 + 1));
    }
    int res = 0;
    for (int i = 0; i <= l; ++i)
    {
        res += arr[i];
    }
    printf("%d", res);
    return 0;
}