笑枕晚风の小站

参考《算法竞赛进阶指南》、AcWing题库 1049. 大盗阿福 题目描述 阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 NNN 家店铺，每家店中都有一些现金。 阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。 作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。 他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？ 输入格式 输入的第一行是一个整数 TTT，表示一共有 TTT 组数据。 接下来的每组数据，第一行是一个整数 NNN ，表示一共有 NNN 家店铺。 第二行是 NNN 个被空格分开的正整数，表示每一家店铺中的现金数量。 每家店铺中的现金数量均不超过1000。 输出格式 对于每组数据，输出一行。 该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。 数据范围 1≤T≤501 \le T \le 501≤T≤50, 1≤N≤1051 \le N \le 10^51≤N≤105 输入样例： 12345231 8 2410 7 6 14 输出样例： 1 ...

✨问题产生 安装了PyTorch CUDA后运行yolov5的train.py遇到如下报错 完整报错提示如下 1234567891011OMP: Error #15: Initializing libiomp5md.dll, but found libiomp5md.dll already initialized.OMP: Hint This means that multiple copies of the OpenMP runtime have been linked into the program. That is dangerous, since it can degrade performance or cause incorrect results. The best thing to do is to ensure that only a single OpenMP runtime is linked into the process, e.g. by avoiding static linking of the OpenMP runtime in any libra ...

查看CUDA版本 使用nvidia-smi命令 在NVIDIA控制面板查看 安装Pytorch 打开官网PyTorch下滑到安装页面 选择对应版本复制命令进行安装 测试安装是否成功 123import torchprint(torch.__version__)print(torch.cuda.is_available()) 123456789101112131415161718192021222324252627282930313233import torchimport timefrom torch import autograd#GPU加速print(torch.__version__)print(torch.cuda.is_available())a=torch.randn(10000,1000)b=torch.randn(1000,10000)print(a)print(b)t0=time.time()c=torch.matmul(a,b)t1=time.time()print(a.device,t1-t0,c.norm(2))device=torch.device ...

int ”较“的原则：加法不爆。 极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80 long long ”较“的原则：加法不爆。 极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80 float ”较“的原则：保证一定位精度。 极大值：0x7f 较大值：0x4f 较小值：0xce 极小值：0xfe double ”较“的原则：保证一定位精度。 极大值：0x7f 较大值：0x43 较小值：0xc2 极小值：0xfe

参考《算法竞赛进阶指南》、AcWing题库 背包问题 0/1背包 模型介绍 给定 NNN 个物品，其中第 iii 个物品的体积为 ViV_{i}Vi​，价值为 WiW_{i}Wi​ 。有一容积为 MMM 的背 包，要求选择一些物品放入背包，使得物品总体积不超过 MMM 的前提下，物品的价位总 和最大。 根据上一节线性 DP 的知识，读者应该很容易想到依次考虑每个物品是否放入背 包，用 “已经处理的物品数” 作为 DP 的 “阶段”，以 “背包中已经放入的物品总体积”作为附加维度。 F[i,j]F[i, j]F[i,j] 表示从前 iii 个物品中选出了总体积为 jjj 的物品放入背包，物品的最大价值 和。 F[i,j]=max⁡{F[i−1,j] 不选第 i 个物品 F[i−1,j−Vi]+Wi if j≥Vi 选第 i 个物品 F[i, j]=\max \begin{cases}F[i-1, j] & \text { 不选第 } i \text { 个物品 } \\ F\left[i-1, j-V_{i}\right]+W_{i} &am ...

参考《算法竞赛进阶指南》、AcWing题库 线性DP 具有线性”阶段“划分的动态规划算法被统称为线性DP。读者对于最长上升子序列(LIS)、最长公共子序列(LCS)、数字三角形(IOI1994)等DP的经典入门例题应该并不陌生，在动态规划的入门书籍或者网络上很容易找到这些问题的描述和解答。这里不会花费时间再次详细解释这些问题，但本着见微知著的思想，我们可以简单回顾它们，并尝试分析一下DP要素在其中的体现。 线性DP: 即线性动态规划，在本节中是一个作常广义的概念，不局限于“线性时间复杂度”的一维动态规划。与数学中的“线性空间”类似，如果一个动态规划算法的“状态”包含多个维度，但在每个维度上都具有“线性”变化的“阶段”，那么该动态规划算法同样称为“线性DP” 。 容易发现，无论状态表示是一维还是多维，DP算法在这些问题上都体现为“作用在线性空间上的递推”——DP的阶段沿着各个维度线性增长，从一个或多个“边界点”开始有方向地向整个状态空间转移、扩展，最后每个状态上都保留了以自身为“目标”的子问题的最优解。 这几个问题也是线性DP中最简单的一类，在这类问题中，需要计算的对象表现出明 ...

参考《算法竞赛进阶指南》、AcWing题库 迭代加深 迭代加深是一种 每次限制搜索深度的 深度优先搜索。 它的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 ，当达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始。 既然是为了找最优解，为什么不用 BFS 呢？我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势。事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小。 当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的。 深度优先搜索每次选定一个分支，不断深入，直至到达递归边界才回溯。这种策略带有一定的缺陷。试想以下情况：搜索树每个节点的分支数目非常多，并且问题的答案在某个较浅的节点上。如果深搜在一开始选错了分支，就很可能在不包含答案的深层子树上浪费许多时间。 如果下图左半部分是问题的状态空间，五角星标识着答 ...

独立集（Independent set） 一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点所形成的集合，如果两个点没有公共边，那么这两个点可以被放到一个独立集中。换句话说，独立集 S 由图中若干顶点组成，且 S 中任两个顶点之间没有边。等价地，图中的每条边至多有一个端点属于 S 。一个独立集的基数是它包含顶点的数目。 如下图中，所有灰色的点可以构成一个独立集，因为他们互相之间没有任何公共边。 对于三个点组成的完全图而言，每个点自身是一个独立集（且是最大独立集）；对四个点构成的四边形图而言，对角的两个点组成一个独立集（且是最大独立集）。 最大独立集 如果往图 G 的独立集 S 中添加任一个顶点都会使独立性丧失（亦即造成某两点间有边），那么称 S 是极大独立集。 如果 S 是图中所有独立集之中基数最大的，那么称 S 是最大独立集，且将该基数称为 G 的独立数，记为 α(G) 。一般来讲，图 G 中可能存在多个极大独立集和最大独立集。 根据定义，最大独立集一定是极大独立集，但反之未必。 问题难度 给定一张图，寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是 N ...

传递闭包 对于某个集合 SSS 我们有定义在集合上的二元关系 RRR。 我们在 SSS 上还定义了一个二元关系 TTT，若关系 TTT 满足 ∀x,y∈S\forall x,y\in S∀x,y∈S，xTy→∃x0=x,x1,x2,…,xk=yxTy\to{\exists} x_0=x,x_1,x_2,\dots,x_k=yxTy→∃x0​=x,x1​,x2​,…,xk​=y 使得 xiRxi+1(0≤i<k)x_iRx_{i+1}(0\leq i<k)xi​Rxi+1​(0≤i<k) 均成立，那么就称关系 TTT 为关系 RRR 的传递闭包。 显然对于图 G=(V,E)G=(V,E)G=(V,E)，若我们把 SSS 视作 GGG 的点集 VVV，对于 x,y∈Vx,y\in Vx,y∈V，xRyxRyxRy 为真当且仅当存在 x→yx\to yx→y 的边，那么 RRR 的传递闭包 TTT 定义为：xTyxTyxTy 为真当且仅当存在 x→yx\to yx→y 的路径。 求传递闭包的方式非常容易，直接 n3n^3n3 跑遍 floyd 就行了。 偏序关系 对于集合 ...

前缀和 前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前 nnn 项的和”。 C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。 例题 有 NNN 个的正整数放到数组 AAA 里，现在要求一个新的数组 BBB，新数组的第 iii 个数 B[i]B[i]B[i] 是原数组 AAA 第 000 到第 iii 个数的和。 输入 1251 2 3 4 5 输出： 11 3 6 10 15 解题思路 递推：B[0] = A[0]，对于 i≥1i \ge 1i≥1 则 B[i] = B[i-1] + A[i]。 参考代码 123456789101112131415161718192021222324#include <iostream>using namespace std;int N, A[10000], B[10000];int main() { cin >> N; for (int i = 0; i < N; i++) { cin &g ...