Blogs
Codeforces 第 995 轮 G 题
问题链接: Codeforces Round 995 Problem G 首先，注意题目约束如下： 第一行包含两个整数 nnn 和 qqq (1≤n≤201≤ n ≤201≤n≤20; 1≤q≤2⋅1051 ≤ q ≤ 2 \cdot 10^51≤q≤2⋅105) — 蛇的数量和事件的数量。 这意味着我们可以使用关于 nnn 复杂度较高的算法，因为 nnn 只有20。 由于我们知道蛇的放置顺序，我们只需要知道任意两条蛇之间的最小距离。为此，我们可以假设两条蛇在开始时是相邻的。我们可以用两个变量来存储蛇的位置。左边的蛇在位置 xxx，右边的蛇在位置 yyy。初始时，设置 x=0x = 0x=0 和 y=1y = 1y=1。然后我们以 O(q)O(q)O(q) 的时间复杂度扫描所有移动。 如果左边的蛇变大，我们将其向右移动 (x+=1x += 1x+=1)。如果右边的蛇缩小，我们也将其向右移动 (y+=1y += 1y+=1)。如果 x=yx = yx=y，这意味着两条蛇相遇了，我们需要增加它们之间的距离。增加距离后，我们可以将左边的蛇向右移动 (x+=1x += 1x+=1)，或者将右边的蛇向右移动 (y+=1y += 1y+=1)。
January 2, 2025
Transformer 模型详解
Transformer模型简介 欢迎来到我们NLP系列的第二篇文章！如果您还没有阅读上一篇文章，可以在这里找到。在这篇文章中，我们将深入探讨Transformer模型的奇妙世界。 关于Transformer模型的原始论文可以在这里找到。它由Vaswani等人在2017年发表，标题为“Attention Is All You Need”。这篇论文介绍了Transformer架构及其注意力机制，此后成为自然语言处理领域的基石。 Transformer模型彻底改变了自然语言处理领域。其创新的架构和强大的功能使其成为各种NLP任务的首选，包括机器翻译、文本生成和情感分析。 在本文中，我们将探讨Transformer模型的内部工作原理。我们将从理解其注意力机制开始，该机制允许模型关注输入序列的相关部分。我们还将讨论位置编码的概念，它帮助模型理解句子中单词的顺序。最后，我们将深入研究自注意力层，这些层使模型能够捕捉不同单词之间的依赖关系。
September 2, 2024
自然语言处理
在这一系列与自然语言处理（NLP）相关的文章中，我们将首先讨论几个用于解决问题的基本概念和基础方法。随后，我们将介绍最新的方法，例如GPT。 我假设读者熟悉神经网络和多层感知器（MLP）的基本概念。 词嵌入 (Word Embedding) 基于计算机的方法处理的是数值数据。因此，有必要找到一种方法将字母语言中的单词或字符语言中的字符转换为数字。 One-hot向量是一个直接的概念，其中一个向量由一个设置为1的元素和所有其他设置为0的元素组成，以表示一个单词或字符。One-hot向量本质上就像一个词索引。然而，one-hot向量的问题在于其稀疏性，这使得大多数方法难以处理。因此，我们需要一种方法将这个one-hot向量（索引）映射到一个嵌入（一个密集向量）中。 某些神经网络模型具有一个嵌入层，可以在神经网络的训练过程中进行训练。也可以直接使用像Word2Vec和GloVe这样的预训练嵌入模型。 如何获得词嵌入 延伸阅读 https://arxiv.org/pdf/1301.3781 主要思想是构建一个网络来预测句子中缺失的单词。例如，在句子“我吃苹果”中，如果我们遮盖掉“苹果”这个词（“我吃__”），网络的任务就是预测缺失的单词。这种方法使我们能够生成一个训练数据集而无需手动标记。 让我们给出一个更正式的描述。给定一个包含 nnn 个单词的词典，我们的目标是创建一个模型，将单词的one-hot编码映射到 ddd 维空间（RdR^dRd）中的嵌入。通过使用单词的嵌入作为输入，网络预测被省略的单词。因此，我们通过训练这个网络来获得词嵌入。 评论：词嵌入类似于降维。因此，像t-SNE和UMAP这样的技术可以被看作是获得词嵌入的方法。然而，这些方法不能直接应用，因为one-hot向量不捕捉单词之间的关系。但是，如果我们能够使用非神经网络方法将one-hot向量映射到特征空间，可能会得到更具可解释性的嵌入。 循环神经网络 (Recurrent Neural Network - RNN) 循环神经网络（RNN）是一种神经网络架构，允许在不同的时间步重复使用相同的网络。这使得它们特别适用于涉及序列数据的任务，例如自然语言处理和时间序列分析。 RNN的基本思想是维持一个隐藏状态，该状态捕获来自先前时间步的信息，并与当前输入结合以生成输出。这个隐藏状态充当一个记忆，允许网络捕获依赖关系和序列数据中的模式。 RNN的架构如下图所示： 在每个时间步，RNN接收一个输入向量，表示为 xtx_txt，并将其与前一个时间步的隐藏状态 ht−1h_{t-1}ht−1 相结合。这种结合通常通过加权和来完成，其中的权重在训练过程中学习。得到的隐藏状态，表示为 hth_tht，然后用于生成该时间步的输出，表示为 yty_tyt。
August 31, 2024
树状数组
背景 芬威克树（Fenwick tree） 或 树状数组（binary indexed tree） 是一种数据结构，可以高效地更新元素和计算数字表中的前缀和。[^1] 空间和时间复杂度 算法 平均 最坏情况 空间 O(n)O(n) 搜索 O(logn)O(logn) 插入 O(logn)O(logn) 删除 O(logn)O(logn) \begin{array}{lll} \text { 算法 } & \text { 平均 } & \text { 最坏情况 } \\ \text { 空间 } & \mathrm{O}(n) & \mathrm{O}(n) \\ \text { 搜索 } & \mathrm{O}(\log n) & \mathrm{O}(\log n) \\ \text { 插入 } & \mathrm{O}(\log n) & \mathrm{O}(\log n) \\ \text { 删除 } & \mathrm{O}(\log n) & \mathrm{O}(\log n) \end{array} 算法 空间 搜索 插入 删除 平均 O(n)O(logn)O(logn)O(logn) 最坏情况 O(n)O(logn)O(logn)O(logn)解释
October 4, 2023
Image to image translation
https://arxiv.org/abs/1512.04150 https://arxiv.org/abs/2104.01538 多峰无监督图像到图像翻译 目的 尽管这种条件分布本质上是多模态的，但现有方法做出了一个过于简化的假设，将其建模为确定性的一对一映射。因此，它们无法从给定的源域图像生成多样化的输出。为了解决这个限制，我们提出了一个多模态无监督图像到图像翻译 (MUNIT) 框架。(摘要) 方法 损失函数: 功能总结：给定一个输入图像并从高斯分布中采样一个风格变量 zzz，模型会生成一个目标域图像，其内容取决于输入图像，风格取决于风格变量。不同的 zzz 会在目标域中生成不同的输出图像。但这种方法仍然局限于一个域到另一个域的转换。如果需要多域转换，则应应用条件生成。（也许有其他工作解决了这个问题）。 网络结构 结果 DRIT 方法 损失函数 结果
September 21, 2023
线段树
在计算机科学中，线段树（Segment Tree），也称为统计树，是一种用于存储区间或线段信息的树形数据结构。它允许查询哪些存储的线段包含一个给定的点。原则上，它是一个静态结构；也就是说，一旦构建就无法修改。一种类似的数据结构是区间树。 空间复杂度: O(n)O(n)O(n) 时间复杂度: 建树: O(n)O(n)O(n) 查询: O(logn)O(\log n)O(logn) 单点更新: O(logn)O(\log n)O(logn) 区间更新（使用懒惰标记）: O(logn)O(\log n)O(logn) 线段树是一棵二叉树，每个节点存储原始数组中一个区间的信息。线段树节点中的值是该区间的某种属性，例如，和、最小值、最大值、最大公约数等。 一个线段树的例子。（属性：和） graph TD; A(10, 1-4) --> B(3, 1-2); A --> C(7, 3-4); B --> D(1, 1-1) ; B --> E(2, 2-2); C --> F(3, 3-3); C --> G(4, 4-4); 根节点将包含整个数组（范围1-4）的属性。左子树和右子树分别包含范围(1-2)和范围(3-4)，依此类推。叶子节点是原始数组的值。 树的节点 树的节点包含我们想要维护的属性以及该节点（线段）的左右边界。 template <typename T> class segment_tree_node { public: T val; unsigned int left, right; segment_tree_node(){ val = T(); // 值的初始值 left = right = 0; // 初始左右边界设为0 } // 使用值、左边界、右边界创建节点 segment_tree_node(T _val, unsigned int _left, unsigned int _right) : val(_val), left(_left), right(_right) {} }; 建树 我使用递归的方法从根节点开始建树。根节点的值由其左右子树派生而来。因此，在设置根节点的值之前，我们需要递归地构建左右子树。
September 17, 2023