VLP: A Survey on Vision-Language Pre-training 论文总结

2024-02-18 19:50

本文主要是介绍VLP: A Survey on Vision-Language Pre-training 论文总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

VLP: A Survey on Vision-Language Pre-training

VLP:视觉语言预训练研究综述

论文地址:
https://arxiv.org/pdf/2202.09061.pdf

摘要:
在过去几年中,训练前模型的出现将计算机视觉(CV)和自然语言处理(NLP)等单峰领域带入了一个新时代。大量工作表明,它们有利于下游单峰任务,避免从头开始训练新模型。那么,这种预先训练好的模型可以应用于多模式任务吗?研究人员已经探索了这个问题,并取得了重大进展。本文综述了视觉语言预训练(VLP)的最新进展和新前沿,包括图像文本和视频文本预训练。为了让读者更好地全面了解VLP,我们首先从五个方面回顾了VLP的最新进展:特征提取、模型体系结构、预训练目标、预训练数据集和下游任务。然后,我们详细总结了具体的VLP模型。最后,我们讨论了VLP的新前沿。据我们所知,这是第一次关于VLP的调查。我们希望这项调查能够为VLP领域的未来研究提供一些启示。

1. 介绍

让机器以类似于人类的方式做出响应一直是人工智能研究人员不懈的目标。为了使机器能够感知和思考,研究人员提出了一系列相关任务,如人脸识别、阅读理解和人机对话,以训练和评估机器在特定方面的智能。具体来说,领域专家手动构建标准数据集,然后在其上培训和评估相关模型。然而,由于相关技术的限制,通常需要对大量标记数据进行训练,以获得更好、更有效的模型。最近出现的基于变压器结构的预培训模型[Vaswani等人,2017]缓解了这一问题。它们首先通过自监督学习进行预训练,通常利用辅助任务(预训练目标)从大规模未标记数据中挖掘监督信号来训练模型,从而学习普遍表征。然后,他们可以通过对下游任务中只有少量手动标记的数据进行微调,从而获得令人惊讶的效果。自BERT[Devlin等人,2019]在自然语言处理(NLP)中出现以来,各种预训练模型在单峰领域如计算机视觉(CV)中的视觉变换器(ViT)[Dosovitskiy等人,2020]和语音中的Wave2V ec[Schneider等人,2019]如雨后春笋般涌现。大量工作表明,它们有利于下游单峰任务,避免从头开始训练新模型。

与单峰字段类似,在多峰字段中也存在高质量标记数据较少的问题。自然的问题是,上述预训练方法能否应用于多模态任务?研究人员已经探索了这个问题,并取得了重大进展。本文主要研究主流视觉语言预训练(VLP),包括图像文本预训练和视频文本预训练。VLP主要通过对大规模数据的预训练来学习不同语态之间的语义对应关系。例如,在图像文本预训练中,我们希望模型将文本中的“狗”与图像中的“狗”相关联。在videotext预训练中,我们希望模型将文本中的对象\动作映射到视频中的对象\动作。为了实现这一目标,VLP对象和模型架构需要巧妙地设计,以允许模型挖掘不同模式之间的关联。

为了让读者更好地了解VLP,我们首先全面回顾其最新进展,并重点关注五个重要方面:

特征提取。本节包括VLP模型中图像、视频和文本的预处理和表示方法(见第2节)
模型架构。我们从两个不同的角度介绍VLP模型的体系结构:从多模式融合的角度介绍单流与双流,从整体体系结构设计的角度介绍仅编码器与编码器-解码器(见第3节)
培训前目标。预训练目标是VLP的核心,主要用于指导模型学习视觉语言相关信息。我们总结了典型的、有特点的培训前目标,分为完成目标、匹配目标、暂时目标和类型(见第4节)
训练前数据集。数据对VLP至关重要。我们简要介绍了VLP的主流语料库及其具体规模(见第5节)
下游任务。各种任务都需要对愿景和语言的合作知识。我们将它们分为五类:分类、回归、检索、生成和其他任务。我们还讨论了这些任务的基本细节和目标(见第6节)。

然后,我们详细总结了特定的最先进(SOTA)VLP模型(见第7节)。最后,我们总结了本文,并对VLP的新前沿进行了广泛讨论(见第8节)。
据我们所知,这是第一次关于VLP的调查。我们希望我们的调查能够帮助研究人员更好地理解这个领域,并激励他们设计更好的模型。

2 特征提取

本节介绍VLP模型如何预处理和表示图像、视频和文本,以获得对应的特征。

2.1特征提取

图像特征提取
(1)基于OD的区域特征(OD RFs)
以前大多数关于VLP的工作都是利用预先训练好的目标检测器来提取视觉特征。最常用的目标检测模型是具有自底向上注意力的快速R-CNN[Anderson等人,2018]。它用于识别属于特定类的对象,并使用边界框对其进行定位。通过使用更快的R-CNN,VLP模型获得了基于OD的区域特征,该特征嵌入了具有k个选定区域的图像的V=[o1,o2,…,ok]。每个区域特征oi是一个2048-d感兴趣区域(RoI)特征及其边界框。边界框由区域左下角和右上角的坐标定义。VLP模型使用边界框构造5-d向量,并将该向量嵌入到名为视觉几何嵌入的高维表示(2048-d)中。通过将基于OD的区域特征嵌入与其视觉几何嵌入相结合,得到OD RFs。虽然ODFs带来了令人印象深刻的性能,但提取区域特征可能很耗时。为了缓解这个问题,预训练的目标检测器通常在预训练期间被冻结,这会限制VLP模型的容量。
(2) 基于CNN的网格功能(CNN GFs)
VLP模型利用卷积神经网络(CNN)提取视觉特征,获得网格特征。一方面,VLP模型可以直接利用网格特征对CNN进行端到端的训练。另一方面,VLP模型还可以首先使用学习的视觉词典对网格特征进行离散化,然后将其输入跨模态模块。
(3) 基于ViT的补丁功能(ViT PFs)
受ViT启发,VLP车型重塑了图像Ii∈ RH×W×C成一系列扁平的二维面片∈ RN×(p2·C),其中(H,W)是原始图像的分辨率,C是通道数,(P,P)是每个图像块的分辨率,N=HW/p2是产生的块数,这也作为变压器的有效输入序列长度。输入图像Ii被编码成嵌入序列:{vcls,v1,…,vN},其中vcls是[CLS]令牌的嵌入

视频特征提取
视频剪辑表示为M帧(图像)

VLP模型使用上述方法提取帧特征。两个最常用的功能是CNN GFs和ViT PFs。对于CNN GFs,VLP模型首先使用在ImageNet上预训练的ResNet和在动力学上预训练的SlowFast来提取每个视频帧的2D和3D视觉特征。这些特征被连接为视觉特征,并通过一个完全连接(FC)的层被投射到与令牌嵌入相同的低维空间。对于ViT PFs,视频剪辑Vi∈ RM×H×W×C由分辨率为H×W的M帧组成,其中M=1表示图像。按照ViT和时间转换器中的协议,输入视频剪辑被划分为大小为P×P的M×N非重叠时空块,其中N=HW/p2。

文本特征
提取文本特征

继BERT之后,VLP模型首先将输入句子分割成一系列子词。然后,在序列的开始和结束处插入序列开始标记和序列结束标记,以生成输入文本序列。文本输入表示通过对相应的单词嵌入、文本位置嵌入和文本类型嵌入求和来计算。

2.2特征表示

为了充分利用单峰预训练模型,VLP模型可以将视觉或文本特征发送到变压器编码器。具体来说,VLP模型利用标准变压器编码器进行随机初始化,以生成视觉或文本表示。此外,VLP模型可以利用预先训练的视觉转换器对ViT PFs进行编码,例如ViT和DeiT[Touvron等人,2021]。VLP模型可以使用预先训练好的文本转换器对文本特征进行编码,例如BERT。为简单起见,我们将这些变压器命名为Xformer。

3模型体系结构

在本节中,我们从两个不同的角度介绍VLP模型的体系结构:(1)从多模式融合的角度介绍单流与双流,以及(2)从整体体系结构设计的角度介绍仅编码器与编码器-解码器。

3.1单流与双流

单流架构
单流架构是指文本和视觉特征连接在一起,然后输入到单个转换器块中,如图1(a)所示。单流结构利用合并注意力融合多模态输入。单流架构的参数效率更高,因为两种模式使用相同的参数集。

双流结构
双流体系结构指的是文本和视觉特征没有连接在一起,而是独立地发送到两个不同的转换器块,如图1(b)所示。这两个变压器块不共享参数。为了获得更高的性能,交叉注意力(如图1(b)中的虚线所示)用于实现跨模态交互。为了获得更高的效率,视觉转换块和文本转换块之间也可以没有交叉关注。

在这里插入图片描述

图1 VLP的两种模型架构示意图

3.2 仅编码器与编码器-解码器

许多VLP模型采用仅编码器架构,其中跨模态表示直接馈入输出层以生成最终输出。相比之下,其他VLP模型提倡使用transformer-encoder-decoder架构,其中跨模式表示首先被馈送到解码器,然后被馈送到输出层。

4预训练目标

本节介绍如何使用不同的预训练目标对VLP模型进行预训练,这对于学习视觉语言的通用表示至关重要。我们将培训前目标总结为四类:完成、匹配、暂时特定类型
完成是通过利用未屏蔽的剩余物来理解模态,从而重构屏蔽元素。(见第4.1、4.2和4.3节。)
匹配是将视觉和语言统一到一个共享的隐藏空间中,以生成通用的视觉语言表示(见第4.4、4.5和4.6节)
暂时是通过对中断的输入序列重新排序来学习良好的表示(见第4.7节)
特定类型包括其他预训练对象,如视觉问答和视觉字幕(见第4.8节)。
现在我们介绍最常用的培训前目标。

4.1蒙面语言建模蒙面语言建模(MLM)

最早由Talylor[1953]在文献中提出,由于BERT模型将其作为一项新的训练前任务进行了调整,因此广为人知。VLP模型中的传销与训练前语言模型(PLM)中的传销相似,但不仅通过其他文本标记,而且还通过视觉标记预测蒙面文本标记。根据经验,遵循BERT的VLP模型以15%的概率随机屏蔽每个文本输入标记,并使用80%的时间使用特殊标记[mask],10%的时间使用随机文本标记,10%的时间使用原始标记来替换屏蔽的标记。

4.2前缀语言建模前缀语言建模(PrefixLM)

是屏蔽语言模型和语言建模(LM)的统一。PrefixLM的提出是为了使该模型具有实体生成能力,从而在不进行微调的情况下实现文本诱导的零镜头泛化。PrefixLM不同于标准LM,因此它可以对前缀序列进行双向注意,并且只对剩余的令牌进行自回归分解。sequence-to-sequence(seq2seq)框架下的PrefixLM不仅像MLM一样具有双向语境化表示,而且可以执行类似于LM的文本生成。

4.3蒙面视觉建模

与MLM一样,蒙面视觉建模(MVM)对视觉(图像或视频)区域或面片进行采样,通常以15%的概率掩盖其视觉特征。VLP模型需要在给定剩余的视觉特征和所有文本特征的情况下重建被掩盖的视觉特征。遮罩的视觉特征设置为零。由于视觉特征是高维和连续的,VLP模型提出了两种MVM变体。

(1) 掩码特征回归学习将蒙版特征的模型输出回归到其原始视觉特征。VLP模型首先将遮罩特征的模型输出转换为与原始视觉特征相同维度的向量,并在原始视觉特征和向量之间应用L2回归。
(2) 蒙面特征分类学习预测蒙面特征的对象语义类。VLP模型首先将遮罩特征的输出反馈到FC层,以预测对象类的分数,然后通过softmax函数将其转换为预测标准化分布。请注意,没有地面真相标签。VLP模型的训练有两种方法。一种是,VLP模型将目标检测模型中最可能的目标类作为硬标签(w.p.0或1),假设检测到的目标类是掩蔽特征的基本真值标签,并应用交叉熵损失来最小化预测和伪类之间的差距。另一种是VLP模型使用软标签作为监控信号,这是检测器的原始输出(即对象类的分布),并最小化两个分布之间的KL差异。

4.4视觉语言匹配

视觉语言匹配(VLM)是最常用的训练前目标,用于调整视觉和语言。在单流VLP模型中,他们使用特殊标记[CLS]的表示作为两种模式的融合表示。在双流VLP模型中,它们将特殊视觉标记[CLSV]的视觉表示和特殊文本标记[CLST]的文本表示连接起来,作为两种模式的融合表示。VLP模型将两种模式的融合表示提供给FC层和sigmoid函数,以预测0到1之间的分数,其中0表示视觉和语言不匹配,1表示视觉和语言匹配。在训练期间,VLP模型在每一步从数据集中抽取正或负对样本。通过将配对样本中的视觉或文本替换为从其他样本中随机选择的视觉或文本来创建负对。

4.5视觉语言对比学习

视觉语言对比学习(VLC)从N×N个可能的视觉语言对中预测匹配的视觉语言对,给定一批N个视觉语言对。注意,这里有n2− N在一个训练批次内的负面视觉语言对。VLP模型分别使用特殊视觉标记[CLSV]的视觉表示和特殊文本标记[CLST]的文本表示来表示视觉和语言的聚合表示。VLP模型计算softmax标准化的视觉(图像或视频)-文本相似性和文本-视觉相似性,并利用视觉-文本和文本-视觉相似性的交叉熵损失进行自我更新。相似性通常由点积实现。

4.6单词区域对齐

单词区域对齐(WRA)是一种无监督的预训练目标,用于对齐视觉区域(视觉块)和单词。VLP模型利用最佳传输来学习视觉和语言之间的一致性。根据经验,VLP模型使用IPOT算法来近似OT距离,因为精确的最小化在计算上很难实现。求解极小化后,OT距离作为训练VLP模型的WRA损失。

4.7 帧顺序建模

为了更好地建模视频的定时,VLP模型随机中断一些输入帧的顺序,然后预测每个帧的实际位置。框架顺序建模(FOM)在实践中被建模为一项分类任务。

4.8特定的预培训对象

VLP模型有时也使用一些下游任务的培训对象,例如视觉问答(VQA)和视觉字幕(VC)作为预培训目标。对于VQA,VLP模型采用上述融合表示,应用FC层,并使用转换后的表示来预测预定义答案候选的分类。除了VLP模型将任务分类为预定义的候选答案外,VLP模型还可以直接生成原始文本格式的答案。对于VC,为了重建输入语句,赋予VLP模型生成能力,VLP模型使用自回归解码器生成相应的图像或视频文本描述。

请注意,由于篇幅限制,我们只介绍了一些流行的培训前目标。我们省略了一些特定的训练前目标,如基础参考表达(GRE)、图像条件去噪自动编码(IDA)[Xia等人,2020],文本条件图像特征生成(TIFG)[Xia等人,2020],目标检测(OD)[Kamath等人,2021]和对齐Kaleido面片建模(AKPM)[Zhuge等人,2021]。此外,我们将蒙面动作预测纳入MVM的范畴。

5培训前数据集

VLP的大多数数据集是通过组合不同多模式任务的公共数据集来构建的。然而,之前的一些作品,如VideoBERT[Sun等人,2019b]、ImageBERT[Qi等人,2020]、ALIGN[Jia等人,2021]和CLIP[Radford等人,2021]处理从互联网收集的大量数据,并使用其自行构建的数据集进行预训练。这里,一些主流语料库及其详细信息如表1所示。
在这里插入图片描述
图1 VLP的一些主流数据集的详细信息

6 下游任务

各种各样的任务需要合作的视野和语言知识。在本节中,我们将介绍此类任务的基本细节和目标,并将其分为五类:分类、回归、检索、生成和其他任务,其中分类、回归和检索任务也称为理解任务。

6.1分类任务视觉问答(VQA)

提供视觉输入(图像或视频)
VQA
代表正确回答问题的任务。它通常被视为一项分类任务,模型从一系列选择中预测出最合适的答案。
视觉推理和组合问答(GQA)
GQA是VQA的升级版,旨在推进自然场景视觉推理的研究[Hudson and Manning,2019]。其数据集中的图像、问题和答案具有匹配的语义表示。这种结构化表示的优点是,答案的分布可以更加均匀,我们可以从更多维度分析模型的性能。
视频语言推理(VLI)
给定一个以对齐字幕为前提的视频片段,再加上基于视频内容的自然语言假设,模型需要推断该假设是否与给定视频片段相矛盾。
视觉推理的自然语言(NLVR)
NL VR任务的输入是两个图像和一个文本描述,输出是图像和文本描述之间的对应关系是否一致(两个标签:true或false)。
视觉蕴涵(VE)
在虚拟现实任务中,图像是前提,文本是假设。我们的目标是预测文本是否是“蕴涵图像”。有三个标签,包含,中立和矛盾。
视觉常识推理(VCR)
VCR以多项选择题的形式存在。对于一个问题,有几种不同的答案。模型必须从多个答案中选择一个答案,然后从多个备选原因中选择选择该答案的原因。我们可以跟随VCR的排行榜追踪VLP的最新想法。
基础参考表达(GRE)
GRE的任务是定位给定文本引用的图像区域。该模型可以输出每个区域的得分,得分最高的区域被用作预测区域。
类别识别(CR)
CR指的是识别产品的类别,这是描述产品的重要属性。

6.2回归任务

多模态情绪分析(MSA)
MSA旨在通过利用多模态信号(例如视觉、语言等)来检测视频中的情绪。它是作为一个连续的强度变量来预测话语的情感取向。

6.3检索任务

视觉语言检索(VLR)
VLR涉及通过适当的匹配策略理解视觉(图像或视频)和语言领域。它包括两个子任务,视觉到文本和文本到视觉检索,其中视觉到文本检索是根据视觉从更大的描述库中获取最相关的文本描述,反之亦然。

6.4生成任务

视觉字幕(VC)
VC旨在为给定的视觉(图像或视频)输入生成语义和语法上合适的文本描述。
Novel Object Captioning at Scale (NoCaps)
NoCaps扩展了VC任务,以测试模型从开放图像数据集中描述新对象的能力,这在训练语料库中是看不到的[Agrawal等人,2019]。
视觉对话(VD)
VD的任务形式是一个图像(或视频)、一段对话历史和一个语言问题,并让模型生成问题的答案。

6.5其他任务

多模态机器翻译(MMT)
MMT是翻译和文本生成的双重任务,将文本从一种语言翻译到另一种语言,并从其他模式(即图像)获得附加信息。
视觉语言导航(VLN)
VLN是一种基于语言指令的基础语言任务,用于观察和探索真实世界的动态。
光学字符识别(OCR)
OCR一般指检测和识别图像中的文本信息,它包括两部分:文本检测(类似于回归)和文本识别(类似于分类)。此外,还有一些与视频相关的下游任务用于评估视频文本预训练模型,包括动作分类(AC)、动作分段(AS)和动作步骤定位(ASL)。

7 SOTA VLP模型

Image-Text VLP models

VisualBERT[Li et al.,2019]被称为第一个图像-文本预训练模型,它使用由更快的R-CNN提取的视觉特征,将视觉特征和文本嵌入连接起来,然后将连接起来的特征馈送给由BERT初始化的单个转换器。许多VLP模型[Li et al.,2020a;Su et al.,2019;Chen et al.,2020;Qi et al.,2020]在调整训练前目标和训练前数据集的同时,遵循与VisualBERT相似的特征提取和体系结构。最近,VLMO[Wang等人,2021a]利用补丁嵌入进行图像嵌入,利用文字嵌入进行文本嵌入,并与模态专家一起将连接的嵌入输入到单个转换器中,取得了令人印象深刻的性能。METER[Dou等人,2021年]探索了如何使用单峰预训练模型,并提出了一种双流体系结构模型来处理多峰融合,从而在许多下游任务上实现SOTA性能。

Video-Text VLP models.

VideoBERT[Sun等人,2019b]被称为第一个视频文本预训练模型,它扩展了BERT模型以同时处理视频和文本。VideoBERT使用预先训练过的ConvNet和S3D[Xie等人,2017]提取视频特征,并将它们与文本单词嵌入连接起来,以输入以BERT为首字母的转换器。训练VideoBERT时,ConvNet和S3D被冻结,这表明该方法不是端到端的。最近,受ViT的启发,Frozed[Bain et al.,2021]和Region Learner[Y an et al.,2021]首先将视频剪辑处理成帧,并根据ViT处理每帧图像的方法获得补丁嵌入。冻结和区域学习者以端到端的方式优化自己,实现SOTA性能。表2总结了更多现有的主流VLP模型。

在这里插入图片描述

8 结论和新前沿

在本文中,我们提供了第一次VLP调查。我们从特征提取、模型结构、预训练目标、预训练数据集和下游任务五个方面回顾了其最新进展,并详细总结了具体的SOTA VLP模型。我们希望我们的调查能够帮助研究人员更好地理解VLP,并激发新的工作来推进这一领域。未来,在现有工作的基础上,VLP可以从以下几个方面进一步发展:

结合声学信息
以往关于多模态预训练的大多数工作强调语言和视觉的联合建模,但忽略了音频中隐藏的信息。虽然音频中的语义信息可能与语言相交,但音频可以提供额外的情感信息、声音边界信息等。此外,音频预训练使模型能够使用声音输入完成下游任务。到目前为止,跨文本、视觉和音频的联合建模和表示仍然是一个有待进一步研究的开放问题。几部前沿作品为这一研究领域的未来带来了曙光。与以前的VLP模型不同,VATT[Akbari et al.,2021]将原始音频作为输入,并使用噪声对比估计(NCE)学习多模态表示。与V A TT不同,OPT[Liu等人,2021]通过各种多级掩蔽策略,学习跨文本、图像和音频的跨模态表示,并且还能够生成文本和图像。其他一些作品,如AudioCLIP[Guzhov et al.,2021]和MERLOT Reserve[Zellers et al.,2022],也展示了他们在三种模态上学习跨模态表示的独特方法。

有知识的学习和认知能力
尽管现有的VLP模型已经取得了显著的性能,但它们的本质是适合大规模多模态数据集。使VLP模型更加知识化对于未来的VLP非常重要。对于输入视觉和文本,有丰富的相关外部常识世界知识和说明性情境知识[Chen等人,2021],可用于增加输入,加速模型训练和推理。解决这个问题需要统一的认知模型架构、知识引导的训练前目标,以及与新知识交互的支持。

Prompt-Tuning
目前,微调是将VLP知识转移到下游任务的主要方法。然而,随着模型规模的增加,每个下游任务都有其微调参数,导致参数效率低下。此外,下游任务的多样性也使得预培训和微调阶段的设计变得繁琐,导致两者之间存在差距。近年来,在NLP中,快速调谐越来越受到关注。通过设计离散或连续的提示,并对特定的下游任务使用MLM,这些模型可以:1)减少微调大量参数的计算成本;2) 弥合预培训和微调之间的差距。快速调谐是刺激语言和世界知识在PLM中分布的一种很有前途的方法。在下一步中,可以对其进行改进,并将其转移到多模态场景中,打破传统范式,解决VLP的痛点[Tsinpoukelli等人,2021年]。

这篇关于VLP: A Survey on Vision-Language Pre-training 论文总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/722264

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

AI hospital 论文Idea

一、Benchmarking Large Language Models on Communicative Medical Coaching: A Dataset and a Novel System论文地址含代码 大多数现有模型和工具主要迎合以患者为中心的服务。这项工作深入探讨了LLMs在提高医疗专业人员的沟通能力。目标是构建一个模拟实践环境,人类医生(即医学学习者)可以在其中与患者代理进行医学

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

状态dp总结

zoj 3631  N 个数中选若干数和(只能选一次)<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int