HLAIA-光子

牛客周赛105 F \hspace{15pt}对于一个长度为 nnn 的数组 {a1,a2,…,an}\{a_1,a_2,\dots,a_n\}{a1​,a2​,…,an​}，小苯先定义 f(i)=gcd⁡(a1,a2,…,ai)f\left(i \right)=\gcd\left(a_1,a_2,\dots,a_i \right)f(i)=gcd(a1​,a2​,…,ai​)[1]^\texttt{[1]}[1]，基于此，再定义数组的权值为： ∑j=1nf(j)\sum\limits_{j = 1}^{n}{f(j)}j=1∑n​f(j) \hspace{15pt}现在，小红想让小苯构造一个长为 nnn 且所有元素都在 [1,m]\left[ 1,m \right][1,m] 之内的数组，满足其权值恰好为 xxx。 \hspace{15pt}请你帮帮小苯。 【名词解释】 \hspace{15pt}gcd[1]^\texttt{[1]}[1]：即最大公因数，指多个整数共有因数中最大的一个。例如，121212、181818 和 303030 的公因数有 1,2,3,61,2,3,...

在记录模拟退火之前，我们来看看它的启发灵感–(详情见WIKI) “模拟退火”来自冶金学术语退火，是将材料加热后再经特定速率冷却的技术，目的是增大晶粒的体积，并且减少晶格中的缺陷，以改变材料的物理性质。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。 模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。 可以证明，模拟退火算法所得解依概率收敛到全局最优解。 模拟退火法可用于精确算法失效的高难度计算优化问题，虽然通常只能获得全局最优的近似，但对很多实际问题已经足够。 模拟退火直观收敛图： 模拟退火(SA)是一种优化算法，用来找全局最优。 如上面的灵感所说，模拟退火算法模仿的是金属...

回顾Adam优化器 AdamW是Adam的升级版，我们先回顾一下 Adam 假如你在训练一个神经网络，目标是找到损失函数的最小损失值。优化器就是你找最小损失值的策略，我们可以把这个过程比作下山，找到这片区域的最低山谷。 Adam优化器是一个不错的策略(放以前来看很好，但现在有AdamW了)，它结合了两个方法： 动量：就像下山有惯性一样，Adam 会记住之前几步的方向，这样就走得更稳更快，用术语说就是加速收敛。 自适应学习率：山势陡峭（梯度大）的地方，它就小步走，防止摔倒(降低学习率)；山势平缓（梯度小）的地方，它就迈大步，加快速度(增大学习率)。它为每个参数都单独调整步幅（也就是学习率）。 Adam 的公式比较复杂(毕竟不复杂就不会这么出名)，但核心的参数更新步骤可以简化为： 新参数=旧参数−学习率∗动量梯度平方+一个小常数新参数 = 旧参数 - \frac{学习率 * 动量} {\sqrt{梯度平方} + 一个小常数} 新参数=旧参数−梯度平方​+一个小常数学习率∗动量​ 它有一个问题：处理“权重衰减”的方式有缺陷。要理解 AdamW，必须先理解“权重衰减”和“L2正则...

牛客周赛103 F \hspace{15pt}小红定义一棵树的其中一棵子树[1]^\texttt{[1]}[1]的权值为：将子树的所有节点编号从小到大排序后，形成数组的不动点[2]^\texttt{[2]}[2]数量。 \hspace{15pt}现在小红拿到了一棵有 nnn 个节点，以 nnn 为根的树，他想知道这棵树的所有子树的权值之和，请你帮帮他。 【名词解释】 \hspace{15pt}子树[1]^\texttt{[1]}[1]：树中某节点删掉与父亲相连的边后，该节点所在的子图。 \hspace{15pt}不动点[2]^\texttt{[2]}[2]：定义整数 i(1≦i≦m)i\left(1\leqq i \leqq m \right)i(1≦i≦m) 是长度为 mmm 的数组 {a1,a2,…,am}\{a_1,a_2,\dots,a_m\}{a1​,a2​,…,am​} 的一个不动点，当且仅当满足 ai=ia_i = iai​=i。 \hspace{15pt}第一行输入一个整数 n(1≦n≦2×105)n\left(1\leqq n \leqq 2\times 10...

二叉树 三种遍历 前中后序遍历的区别其实就是根节点的位置不同： 前序遍历是 根–左子–右子 中序遍历是 左子–根–右子 后序遍历是 左子–右子–根 前序遍历（Preorder Traversal） 顺序：根节点 → 左子树 → 右子树 特点：先访问根节点，再递归遍历左右子树。 示例： 12345 1 / \ 2 3 / \4 5 前序遍历结果：1, 2, 4, 5, 3 中序遍历（Inorder Traversal） 顺序：左子树 → 根节点 → 右子树 特点：先遍历左子树，再访问根节点，最后遍历右子树。 示例： 同一棵树的遍历结果：4, 2, 5, 1, 3 后序遍历（Postorder Traversal） 顺序：左子树 → 右子树 → 根节点 特点：先递归遍历左右子树，最后访问根节点。 示例： 同一棵树的遍历结果：4, 5, 2, 3, 1 完全二叉树 完全二叉树的性质： 对于任意一个节点iii，其父亲节点是i2\dfrac{i}{2}2i​，左子节点是2×i2 \times i2×i，右子节点是2×i+12 \times i+12×...

背包 01背包 01背包问题通常为：给定 nnn 种物品和一个背包，第 iii 个物品体积为 cic_ici​ ，价值为 wiw_iwi​ ，背包地容量为 CCC 。如何选择装入背包的物品，使装入背包中的物品的总价值最大？ 以 HDU 2602 为例 题目 用自底向上的递推完成转移过程， dp[i][j]dp[i][j]dp[i][j] 表示把前 iii 个物品(从第 111 个到第 iii 个)装入容量为 jjj 的背包中获得的最大价值。假设现在递推到 dp[i][j]dp[i][j]dp[i][j] ，分两种情况： (1) 第 iii 个物品的体积比 jjj 还大，则不能装入当前背包，直接继承前 i−1i-1i−1 个物品装入容量为 jjj 的背包，即 dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j] dp[i][j]=dp[i−1][j] (2) 第i个物品体积比j小，能装进背包，又分为两种：装或不装 ①装 dp[i][j]=dp[i−1][j−c[i]]+w[i]dp[i][j] = dp[i-1][j-c[i]] + w[i] ...

ITA练习赛 F 小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。 小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。 小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。 小d想知道，他在精力范围内，能够获得的利益值到底是多少。 设定小d自己的编号为1.并且对应一个人的交际次数限定为1. 本题包含多组输入，第一行输入一个数t，表示测试数据的组数 每组数据的第一行输入三个数，N,M，C，表示这个人际关系网一共有多少个人，关系网的关系数，以及小d的精力值 接下来N-1行，每行两个数ai，bi。这里第i行表示和编号为i+1的人认识需要花费ai的精力，能够获得的利益值为bi。 再接下来M行，每行两个数x，y，表示编号为x的人能够和编号为y的人接触 t<=50 2<=N<=1000...

2025年7月21日~7月23日(实际上要算上24日)，我们小队选择2022年数模国赛B题实战演练。 我们VP的规则是 答题过程中，不看当年的国赛获奖论文。 可以借助各种工具找资料，但是最开始的几个小时不要去找，只凭自己想。这样做是为了防止我们自己的思路在一开始就被网上的资料和思路牵头走。 完成论文并交给评委老师审阅后，去中国大学生在线上找当年国赛论文展示，比对自己的不足。看论文有个原则：辩证看待，即使是国一论文，也可能有错误和欠缺。 论文、源码和附录材料我已上传到github。 在第一天上午，老杨就迅速把问题1的第1、2问的数学模型建立出来了，并附带有第3小问的思路。我随之实现第一、二小问的代码，并把支撑材料的图给绘制出来，发给老陈。老杨数学功底很扎实，建模快；我不熟悉numpy、pandas和matplotlib，编程上花的时间多了些。 编程手在编程时，需要把建模手的思路完全摸清，然后对着题目描述进行编程规划，再开始敲代码。因此，我发现我们第三小问的思路有误，会错题意。我们原本的思路是用第一小问提出的数学架构去解决第三小问的问题，但是题目背景有变，仅凭纯数学方法无法解决...

牛客暑期多校4 开赛以来最难的一场，牢底坐穿。验题组用o3对最简单的题CF估分为1600~1700，且只有这道题估分在2000以下。不是，这给开了一场WF？ 可惜了，这周没多少时间补 Problem F. For the treasury! 公元11世纪初，有一些被称为维京人的丹麦入侵者在英格兰活动。 Askeladd是一群维京海盗的领袖，他在这片肥沃的土地上寻找宝藏。在一夜袭击了1个村庄后，他们共收集了nnn个宝藏，按顺序排列，价值分别为a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​。Askeladd的团队有一项关于如何分配这些宝藏的协议：作为领袖的Askeladd将取走前面的kkk个宝藏，即价值为a1,a2,…,aka_1,a_2,\ldots,a_ka1​,a2​,…,ak​的宝藏，而其余海盗将分配其余的宝藏。但是，由于时间太晚，他们决定在第二天早上进行这个分配。 Askeladd非常聪明且狡猾，他在夜间偷偷摸摸地试图重新安排宝藏，以便他可以获得更多的宝藏总价值。然而，由于某种原因，他只被允许交换两个相邻的宝藏。此外，考虑到被其他...

差分 差分是前缀和的逆运算，运用于区间修改和询问。当对数据集A的某个区间做修改时，引入差分数组D，只需要修改这个区间的端点，就能记录整个区间的修改，这个修改的复杂度为O(1) 。当所有修改都完成后，再利用差分数组计算出新的A。 差分数组D[]的定义是：D[k] = a[k] - a[k-1]，a[]是原数组 显然，a[i] = D[1]+D[2]+...+D[i]，a[]是D[]的前缀和 例如，把数组区间[L,R]内的每个元素都加上d，只需要对应的差分数组D[]做以下操作： 把D[L]加上d：D[L] += d; 把D[R+1]减去d:D[R+1] -= d; D[]只会修改区间[L,R]内的值，不会修改到区间外的，要查询a[i]时，做一个D[i]的前缀和即可 以HDU 1556 为例 题目 代码 1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;const int maxn = 1e6+1;int a[maxn],D[maxn];int ...