为了更好的阅读体验，请点击这里 题目链接：GElectricCircuit 看到了\(N\)的数据范围，因此是显然的状压dp。 不妨设\(f_S\)为仅使用\(S\)集合中的所有点，能够连成恰好\(1\)个连通块的方案数。\(g_S\)为仅使用\(S\)集合中的所有点的方案数，其中\(cntr(S)\)在\(S\)中为red的个数，\(cntb(S)\)为在\(S\)中blue的个数。 不难发现对于某一集合\(S\)而言，只有在\(cntr(S)=cntb(S)\)时才能连成恰好\(1\)个连通块，对于答案才有贡献。因此最终答案为： \[ans=\sum_S\frac{f_S\timesc...

为了更好的阅读体验，请点击这里 题目链接 套上平衡树板子就能做的很快的题，然后因为是指针存树，因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度\(O(N\log^2N)\)。 但是一定要记住不可以直接使用std::swap交换包含带有指针的类的实例（如代码中的Treap类）！原因在于在std::swap函数中涉及了调用析构函数来析构用于承载交换的中间变量，如果你没写析构函数释放空间还好，如果写了那么它会把中间变量中的指针（从正常指针复制）指向的空间给释放掉！ 为了避免这种情况，因此写一个成员函数用于交换。 include<bits/stdc.h> usingnam...

为了更好的阅读体验，请点击这里 这里只有板子没有原理QWQ 可实现 1.插入x数 2.删除x数(若有多个相同的数，只删除一个) 3.查询x数的排名(排名定义为比当前数小的数的个数+1) 4.查询排名为x的数 5.求x的前驱(前驱定义为小于x，且最大的数) 6.求x的后继(后继定义为大于x，且最小的数) 原题https://www.luogu.com.cn/problem/P3369 在Ver1.0基础上把指针板子修正成C的类方法版本了，null指针使用static静态量来处理。然后仅需要实现类的方法中包含小于号的重载就可以使用这个名次树了。另外，这里所有涉及到的名次都是1-index的。 in...

为了更好的阅读体验，请点击这里 分数规划小技巧：尽可能将式子写成存在某种取值，使得不等式成立的形式。不然可能需要绕几个弯才能想出来。 题目链接 题目大意：给出一个DAG，每条边有一个\(b_i,c_i\)，保证从编号小的边向编号大的边连边，且\(1\)到\(n\)必有路径，求\(1\)到\(n\)路径上的\(\max\frac{\sumb}{\sumc}\)。 分数规划常规做法：二分答案\(x\)，下面比较一下两种设法： \(x>\max\frac{\sumb}{\sumc}\iff\)从\(1\)到\(n\)的所有路径都满足\(x>\frac{\sumb}{\sumc}\)...

为了更好的阅读体验，请点击这里 由于发不出论文，所以找点冷门方向做一做。从汉语比喻开始。 读完这篇论文之后我觉得COLING这方向我上我也行（ε=ε=ε=┏(゜ロ゜;)┛ 题目：CM-Gen:ANeuralFrameworkforChineseMetaphorGenerationwithExplicitContextModelling 论文链接 代码链接 发表于2022，10月，COLING ChineseNominalMetaphor——汉语比喻，以下简写做NM。 本文提出了一个基于GPT2的结构解决三个问题，NM的识别，NM中部件的识别（就是本体、喻体、比喻词（e.g.像、若、似）、上下文...

5042.龟速飞行棋 题目链接：5042.龟速飞行棋 赛中没过，赛后补题时由于题解有些抽象，自己写个题解。 可以发现每次转移的结果只跟后面两个点的胜负状态有关。 不妨设\(f_{u,a,b}\)表示，\(u+1\)号点的胜负态为\(a\)，\(u+2\)号点的胜负态为\(b\)，此时从\(1\)号点出发的胜负态是什么。那么可以发现，利用\(a,b\)的数值，可以求出\(u\)号点的胜负态\(uwin\)。这样就可以从\(n\)号点的胜负态一路推到\(1\)号点的胜负态，然后在推的过程中用记忆化搜索的方式记录一下，就可以简单做了。 当\(u=n\)时，不妨令\(a=1,b=1\)，这样\(u...

5039.摇钱树 题目链接：5039.摇钱树 感觉在赛中的时候，完全没有考虑分数规划这种做法。同时也没有想到怎么拆这两个交和并的式子。有点难受…… 当出现分数使其尽量大或者小，并且如果修改其中直接相关的某个值会导致分子分母同时变化的时候，还是要多想想分数规划的做法。 下面引用一下题解 另外这两个交和并的式子，令\(a=S\andT,b=Ta\)，所以原来的式子变成了 \[\frac{|S\andT|}{|S\orT|}=\frac{a}{b+|S|}\] 所以，用分数规划的做法，二分一个答案\(ans\)，则有 \[\frac{a}{b+|S|}\geans\impliesab\...

为了更好的阅读体验，请单击这里 AtCoderBeginnerContest302H.BallCollector 题意跳过。 可以视作将\(a_i,b_i\)之间连了一条边，然后\(a_i,b_i\)之间只能选一个等价于对于一条边只能选择其一个端点。那么对于只包含树的联通块而言，如果都选择儿子节点，那么会有一个根节点无法被选择上；而对于包含至少一个环的联通块而言，所有节点都可以被选择上，例如，可以先找出环，然后利用环上的边将环上的点都选上，然后对于连上环的边，选上边另一头的节点即可，这样慢慢延申到整个联通块。 因此，答案为：所有节点个数树联通块个数 于是问题就转化为如何维护树联通块个数了。 可...

为了更好的阅读体验，请点击这里 题目链接：TravelPlan 题目大意：\(n\)个点的完全二叉树，每个点可以分配\(1\simm\)的点权，定义路径价值为路径中最大的点权，求所有路径的价值和。 对于任意长度（这里主要指包括几个节点）的路径\(t\)，最大点权不超过\(k\)的方案数有\(k^t\)个，因此最大点权恰好为\(k\)的方案数有\(k^t(k-1)^t\)。所以，对于任意一条长度为\(t\)的路径，不考虑不在路径上其他点的影响时，其对于答案的贡献为： \[\begin{aligned}\text{pathcontribution}_t&=\sum_{k=1}^m(k^...

为了更好的阅读体验，请点击这里 本文大部分内容翻译自Chapter1Basics，原因是之前翻译的版本太老了，不得不亲自披挂上阵拿机器翻译一下。只截取了部分自己可能用得到的，所以如果有看不太懂的地方，去翻一下原网页吧。QWQ 附赠libzmq的api接口函数说明一份。 一、基础函数 intzmq_recv(voidsocket,voidbuf,size_tlen,intflags);zmq_recv()函数应从socket参数引用的套接字接收消息，并将其存储在buf参数引用的缓冲区中。任何超过len参数指定长度的字节都将被截断。如果指定套接字上没有可用消息，则zmq_recv()函数将阻塞，...

为了更好的阅读体验，请点击这里 device_map 以下内容参考HuggingfaceAccelerate文档：超大模型推理方法 在HuggingFace中有个重要的关键字是device_map，它可以简单控制模型层部署在哪些硬件上。 设置参数device_map="auto"，Accelerate会自动检测在哪个设备放置模型的哪层参数（自动根据你的硬件资源分配模型参数）。其规则如下： 首先充分利用GPU上的显存资源 如果GPU上资源不够了，那么就将权重存储到内存 如果内存还不够用了，将会使用内存映射的技术，将剩余的参数存储到硬盘上 设置参数no_split_module_classes...

开场 多模态串讲的上篇是比较传统的多模态任务 多模态最后的模态交互很重要 传统的缺点是都用了预训练的目标检测器，训练和部署都很困难。 ViLT把预训练的目标检测器换成了一层的PatchEmbedding。 因此容易比不过c类的方法 ViLT训练很慢 认为未来是c类的模型结构 Loss： b类（CLIP）仅用对比学习的loss（ImageTextContrastive），比较简单。 c类由于有目标检测，因此提了WordPatchAlignment ViLT中发现WPALoss非常慢 MLM的Loss ImageTextMatching效果也很好 认为目标函数应该是ITC+ITM+MLM...

ViT 概括 论文题目：ANIMAGEISWORTH16X16WORDS:TRANSFORMERSFORIMAGERECOGNITIONATSCALE 论文地址：https://openreview.net/pdf?id=YicbFdNTTy 作者来自Google 亮点: 一些有趣的特性： CNN处理不太好但是ViT可以处理好的例子： 遮挡 数据分布偏移 加入对抗性的patch 排列 作者认为： 对于CNN的依赖是不必要的 纯Transformer可以做到和CNN媲美的结果 Transformer需要更少的训练资源，即使如此，也需要2500TPUv3天数。这里说的少，只是跟更耗卡的模...

2023/3/20粒子群（PSO）算法 老师又没来，这说明助教比老师强，男助教能讲算法，女助教讲论文怎么写，说明男助教强 大作业相关 下周起开始汇报，下周一 按照题目第一关键字，顺序号第二关键字 讲15分钟，问答5分钟 下周一、三讲的组只需要把算法设计讲出来即可 上课内容 TheParticleSwarmOptimizationAlgorithm（粒子群） Origins：1986年，有人描述这个过程用3个简单的行为。 Separation 避免人群过于拥挤 Alignment 朝领头的个体对齐 Cohesion（内聚） 个体会朝着中间个体走，开始向中间集合 结合了自身经...

希望您们先看过书，再来看本blog，否则可能会看不懂，原因是我只写书上没写或者很新奇的东西。 先引个torch包 importtorch 2.1数据操作 2.1.1入门 x.numel()会返回张量中元素的总数。 torch.tensor()与torch.Tensor()的区别 torch.tensor()是（当你未指定dtype的类型时）将data转化为torch.FloatTensor、torch.LongTensor、torch.DoubleTensor等类型，转化类型依据于data的类型或者dtype的值 直接使用vec=torch.tensor()会报错，可以考虑如下方案修改：...

群智能（Swarmintelligence） 自然界动物群，称之为群。 群的特征： 相互作用的相邻个体的集合 个体的行为简单，既有竞争又有协作 智能化的集体行为（1+1>2）： 个体间不仅能够交互信息，还能够处理信息，根据信息改变自身行为 没有一个集中控制中心，分布式、自组织 作为群体协同工作时，展现出非常复杂的行为特征——智能 任何一种由昆虫群体或其他动物社会行为机制而激发设计出的算法或分布式解决问题的策略都属于群智能算法 典型算法： 粒子群PSO 蚁群ACO 人工鱼群AFSA 人工蜂群ABCA 算法原理：蚁群觅食 模拟自然界蚁群觅食（从巢穴到食物的最佳路径的行为）的过程。...

LLaMA最近开源，分别开源了7e9,1.3e10,3.3e10,6.5e10四个参数量的模型。但是这里有意思的是，他们管自己的模型称为smallermodels。 Google推出了22B的ViT 1.Efficient（PEFT） 简要概括 更高效，哪里慢就让它快起来 让所有的方法更efficient一些。 论文1：AIM 论文：AIM:AdaptingImageModelsforEfficientVideoActionRecognition 如何使用parameterefficientfine-tuning 本篇是做视频动作识别（视频理解） 摘要、介绍、相关工作、结论 之前的视频理解的工...

论文：LLaMA:OpenandEfficientFoundationLanguageModels 模型代码：https://github.com/facebookresearch/llama/blob/main/llama/model.py你也可以打开之前的目录看完整代码。 摘要、介绍、相关工作、结论 摘要 LLaMA是一个从7B到65B参数的模型集合。 作者在\(10^{12}\)级别的词元上训练，证明了仅使用公开数据集也可以训练出来SOTA级别的模型。 LLaMA-13B比GPT3(175B)在大多数测试标准上强，并且LLaMA-65B与最好的模型Chinchilla-70B和PaLM-...

2.4微积分 2.4.3梯度 梯度是一个多元函数所有变量偏导数的连接。具体而言：设函数\(f:\mathbb{R}^n\rightarrow\mathbb{R}\)的输入是一个\(n\)维向量\(\boldsymbol{x}=[x_1,x_2,\cdots,x_n]^T\)，输出是一个标量。函数\(f(\boldsymbol{x})\)相对于\(\boldsymbol{x}\)的梯度是一个包含\(n\)个偏导数的向量： \[\nabla_xf(\boldsymbol{x})=[\frac{\partialf(\boldsymbol{x})}{\partialx_1},\frac{\part...

这章感觉没什么需要特别记住的东西，感觉忘了回来翻一翻代码就好。 3.1线性回归 3.1.1线性回归的基本元素 1.线性模型 \(\boldsymbol{x}^{(i)}\)是一个列向量，表示第\(i\)个样本。用符号标识的矩阵\(\boldsymbol{X}\in\mathbb{R}^{n\timesd}\)可以很方便地引用整个数据集中的\(n\)个样本。其中\(\boldsymbol{X}\)的每一行是一个样本，每一列是一种特征。 对于特征集合\(\boldsymbol{X}\)，预测值\(\hat{\boldsymbol{y}}\in\mathbb{R}^n\)可以通过矩阵-向量乘法表示为...