B3665 题解

kimidonatsu · 2022-11-02 20:03:35 · 题解

B3665 题解

题意简述

其实说起来也很简单，就是给 n 条数据和 q 次询问，需要存储下数据以备询问，最后在查询时将答案统计在 ans 里（使用按位异或和，即 ^）。

题目分析

这道题的考点在于数据的存储，很多同学可能和我一样，写了一份二维数组的代码，但是交上去却爆了个 0。

那么我们可以来到数据规模部分，我们不难发现，题目给的数据是很大的，需要使用 unsigned long long，但是用它开数组一定会爆空间，也就是俗称的 MLE。

那么有什么办法呢？在 C++ 的 STL 中有一个序列式容器，称为 vector。那么什么是 vector 呢？

std::vector 是 STL 提供的 内存连续的、可变长度 的数组（亦称列表）数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。 —— OI WIKI

我们知道我们很有很多时候不能提前开好足够大空间的长数组（e.g. 就像本题），就算控制下来了，单份数据可能还是会非常大（e.g. 还是本题）。那么这个时候，我们就可以使用 vector 来把内存控制在空间范围下。而且 vector 还支持 动态扩容 ，在内存紧张的时候就可以派上用场了（e.g. 仍然是本题……）

在这道题我们还会运用到在 C++11 中支持的 vector 列表初始化（详见 cppreference）。

`vector` 使用方法

在这里先讲一些基础的用法：

push_back() 成员函数在 vector 的末尾插入值，如果有必要会扩展 vector 的大小。
size() 函数显示 vector 的大小。
begin() 函数返回一个指向 vector 开头的迭代器。
end() 函数返回一个指向 vector 末尾的迭代器。

那么我们就可以愉快地写出代码了~

代码

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
const ull N = 4e6;

ull n, q, s, x, y, ans;
vector<ull> a[N];

int main() {
    scanf("%llu %llu", &n, &q);

    /* 存储数据 */
    for (ull i = 1; i <= n; i++) {
        scanf("%llu", &s);
        for (ull j = 1; j <= s; j++) {
            ull tmp;
            scanf("%llu", &tmp);
            a[i].push_back(tmp);
        }
    }

    /* 处理询问 */
    for (ull i = 1; i <= q; i++) {
        scanf("%llu %llu", &x, &y);
        ans ^= a[x][y - 1];
    }

    printf("%llu\n", ans);
    return 0;
}

代码小注：

此处的 typedef 是用于自定义变量类型名的，由于 unsigned long long 实在是又臭又长，所以使用 typedef 将它定义为 ull 方便使用。
使用 const 定义数组的原因是在 C++ 中const 常量有数据类型，编译器可以对它进行类型安全检查，开到了 4e6 是防一手数据太大。
这里的 vector<ull> a[N] 的写法正是前文提及的 vector 所支持的 列表初始化，包括在下文中使用到的直接使用 [] 运算符直接操作 vector，也正是应用到了这个特性。
在 for 循环中定义 tmp 是因为在 for 中的变量在跳循环之后会回卷删除，所以能节省一部分空间。
在计算答案时使用的是 a[x][y - 1]，这是因为 vector 的数组和正常数组一样，也是从下标 0 开始。

结语

需要注意的是，vector 的底层实现还是定义长数组，能够实现动态扩容的原因是因为添加了防溢出的操作。所以如果可以善用 resize() 和 reverse()，就可以使得 vector 的复杂度与普通数组差不多。

引用资料

各位有兴趣的同学可以自己探索：

OI Wiki 序列式容器 - vector
Runoob vector 容器浅析
C++11 列表初始化

B3665 题解

B3665 题解

题意简述

题目分析

vector 使用方法

代码

结语

引用资料

`vector` 使用方法