- 2024-11-01dp专题总结 - AtCoder DP Contest
dp专题总结题单:this w
- 2024-10-31【最优化】第二次要点整理
目录精确线搜索技术进退法确定搜索区间分割法确定极小值二分法黄金分割法插值法三点二次插值法(拉格朗日插值法)【问题】在迭代中,已知\(x^{(k)}\)和下降方向\(d^{(k)}\),如何确定下降步长\(\alpha^{(k)}\),使得\(f(x^{(k)}+\alpha^{(k)}d^{(k)})<f(x^{(k)})\)?精确线搜索技
- 2024-10-18FlashAttention逐代解析与公式推导
StandardAttention标准Attention计算可以简化为:\[O=softmax(QK^T)V\tag{1}\]此处忽略了AttentionMask和维度归一化因子\(1/\sqrt{d}\)。公式(1)的标准计算方式是分解成三步:\[S=QK^T\tag{2}\]\[P=softmax(S)\tag{3}\]\[O=PV\tag{4}\]但这样做的问题在于,假设\(
- 2024-10-15P8386 [PA2021] Od deski do desk 题解
P8386[PA2021]Oddeskidodesk题解考虑一个大的序列一定被分成几个区间来删除。朴素的dp定义是\(dp_{i,j}\)表示前\(i\)个数,最后一个数元素是\(j\)的方案数。然而这样不仅不好转移,而且设不下状态。不难发现所有值是等价的。考虑这样一个事情:若我们要分出一个新的区
- 2024-10-03ABC221G Jumping Sequences 题解
JumpingSequences把移动的上下左右改成左上、左下、右上、右下(坐标轴旋转\(45\)°)。则最终目的地是\((A+B,A-B)\)。(以前移动的方式是\((\pmd_i,0),(0,\pmd_i)\)。现在每次移动的方式是\((\pmd_i,\pmd_i)\))则\(x,y\)两维可以分开考虑。目标:从\(d_1\simd_n\)中选
- 2024-09-18CF1716C Robot in a Hallway 题解
容易发现合法路径一定形如:先弯弯曲曲地走(即向下、向右、向上、向右地移动),再直接向右走到头,碰到边界后折回来。所以考虑枚举弯曲地走的部分,这部分的最快时间容易求出。只需考虑快速求出剩余部分的最快时间,设对于第\(i\)第\(j\)列,这个时间为\(f_{i,j}\)。发现移动和等待格子
- 2024-09-11摘果果
摘果果题意给出一棵以\(1\)为根的树和两个序列\(a\)和\(b\)。确定一种DFS遍历顺序,使得用以下方法计算出的权值最大:初始时\(v\leftarrow0,k\leftarrow0\)。经过一个节点\(x\)时\(v\leftarrowv+ka_x,k\leftarrowk+b_x\)。遍历完后最终的\(v\)即权值。
- 2024-09-11闲话 24.9.11
闲话哈哈,没有选题了。没有选题就不写了(最近摆的很舒服啊。等卖了题再拿题解充当闲话吧。碰壁:处理▂▕▄▄制▒▟▀问题不可以▙依赖[错误:所引对象未导引至对象实例;标准处理方法_004.rtf不存在]。不确定[已编辑]难的。推歌:樱桃簪子by天使盐feat.诗岸轻舟慢慢多
- 2024-09-08Graph Edge Partitioning via Neighborhood Heuristic
目录概符号说明VertexvsEdgepartitioningNE(NeighborExpansion)代码ZhangC.,WeiF.,LiuQ.,TangZ.G.andLiZ.Graphedgepartitioningvianeighborhoodheuristic.KDD,2017.概本文提出了一种图分割方法(edgepartitioning),保证只有少量的重复结点.符号
- 2024-08-30浅谈摩尔投票法
问题引入给定\(n\)个数\(a_i\),求出该数列的绝对众数,保证该绝对众数存在。\(n\le10^7\),空间限制1MB。算法介绍摩尔投票法可以\(O(1)\)空间\(O(n)\)时间内求出一个数列的绝对众数,使用前提是数列保证存在绝对众数,否则你只能求出一个可能是绝对众数的数,这时你还需要使用
- 2024-08-28EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) VP记录
EPICInstituteofTechnologyRoundSummer2024(Div.1+Div.2)VP记录A一眼\((n-1)m+1\)。B最后的数列是固定的,每个数与最后数列的数相减后,对差值求和再加上最大值即可。C唐诗C题,获得\(3\)发罚时。只有一个数右边的数归零了,它才会归零。右往左扫,如果右边
- 2024-08-16反悔贪心 & 模拟费用流
反悔贪心&模拟费用流参考资料来源cyt前言很多找到一种可行的方案,匹配(选择)某些东西,使价值最优化的问题可以建出费用流模型。但是直接跑费用流的复杂度是不对的。我们又想到可以用简单的贪心思路解决这些问题,然而一般的贪心都假掉了。于是我们考虑模拟费用流的退流操作来做
- 2024-08-09CF1647F Madoka and Laziness 题解
CF1647F给定排列\(p\),将其划分为两个单峰子序列,求两个单峰子序列的峰的组合的情况数。\(2\leqn\leq5\times10^5\)首先要注意到一个非常常见的地方:两个单峰子序列中的一个的峰值一定在整个排列\(p\)的最大值处这个非常显然,但并不注意到他的重要性,容易被忽视为
- 2024-07-10集合幂级数
集合幂级数从\(2^U\rightarrowR\)的映射加法乘法\(h=f\cdotg=\sum\limits_{L\in2^U}\sum\limits_{R\in2^U}f_Lg_Rx^{L\oplusR}\)类比乘法,其中\(\oplus\)需要满足交换律,结合律高维前缀和的dp解释设\(f_{S,i}\)表示考虑\(S\)的子集的后\(i\)位,前\(|S|-i
- 2024-06-22[题解]AT_abc264_e [ABC264E] Blackout 2
思路一道很经典的题,运用了一种叫「时光倒流」的技巧。「时光倒流」本质上就是将所有删边(或删点)的操作,通过倒序循环求值的方式转化为加边(或加点)。「时光倒流」具体实现通常伴随着并查集出现,维护一个连通块的某种性质。首先,我们需要将所有从始至终没有删过的边加入并查集。在这
- 2024-06-09Markdown箭头的输入方法
文章目录普通箭头长箭头普通箭头MarkDown(需要在前后各添加一个$)箭头形状\uparrow↑\uparrow↑\Uparrow
- 2024-04-10Air Conditioner 题解
[AirConditioner]题意简述题目链接。给定一个整数\(n\),每秒钟可以选择使\(n\)增加\(1\)或减少\(1\)或不改变,有\(M\)个询问,对于第\(i\)个询问,给定\(t_i,l_i,r_i\),表示询问在第\(t_i\)秒时,是否有\(n\in[l_i,r_i]\)。如果能满足所有的询问,输出YES,否则输出NO。
- 2024-04-05QOJ #1280.Fibonacci Partition/Fibonacci性质大杂烩
QOJ#1280.FibonacciPartition(为什么布置的作业题没有任何可见AC记录啊/kk)拿下了QOJ上的用户首杀(同时目前也是QOJ可见的submission中唯一一个过掉这个题的,另一个是vjudge上我的提交)。也许是这个题实在是太冷门了,但是从Fibonacci-Lucas数列的性质应用上是一道非常
- 2024-03-22常见优化器对比:梯度下降法、带动量的梯度下降法、Adagrad、RMSProp、Adam
系列文章目录李沐《动手学深度学习》线性神经网络线性回归李沐《动手学深度学习》优化算法(相关概念、梯度下降法、牛顿法)李沐《动手学深度学习》优化算法(经典优化算法)文章目录系列文章目录一、梯度下降法(一)基本思想(二)梯度下降法的三种不同形式(三)优缺点二、带动量的
- 2024-02-28ABC320 FG
F-FuelRoundTrip注意到路程分成了两段,所以我们也按两段dp。设\(f_{i,j,k}\)表示到第\(i\)个加油站,来程加油后油量为\(j\),回程加油后油量为\(k\)的最小代价。初始对于\(0\lei\leh\),有\(f_{0,h,i}=0\)。考虑刷表法转移(\(i\toi+1\)),令\(d=x_{i+1}-x_i\),然后根据
- 2024-02-27USACO 2024 Season
2024JANSilverCowmpetency线段树可以有效减少思维含量。建议评分:蓝。设\[x=\max_{k=1}^ia_k\]\[y=\max_{k=i+1}^{j-1}a_k\]则FJ的限制\((i,j)\)可以表示为\(x\gey\)并且\(x<a_j\)。将所有限制按\(i\)从小到大排序后,对每个限制\((i,j)\)执行以下流程。
- 2024-02-08KMP
KMP主要用于求解以下问题:求字符串\(t\)在字符串\(s\)中出现的所有位置。如果存在\(s[i\dotsj]\)与\(t\)完全相同,则称\(t\)在位置\(i\)出现了。用\(s[l\dotsr]\)表示字符串\(s\)的第\(l\)个字符到第\(r-1\)个字符所组成的字符串,下标从\(1\)开始
- 2024-02-08ABC 326
E题意:给定一个\(n\)面骰,长度\(n\)的数组\(a\)和一个初始为\(0\)的变量\(x\)。每次投掷骰子,等概率获得\(1\simn\)中的一个数\(p\)。若\(p\lex\),结束;否则\(x\leftarrowp\)且总收获\(S\leftarrowS+a_p\)。求期望值。其实期望\(S=\suma_i\timesp_i\),其中
- 2024-01-28闲话1.28
周日,爽爽爽
- 2024-01-11LaTeX
符号\(\LaTeX\)\(\operatorname{opt}\)$\$\operatorname{opt}\(\wedge\)\wedge\(\vee\)\vee\(\rightarrow\)\rightarrow\(\leftarrow\)\leftarrow\(\leftrightarrow\)\leftrightarrow