数列 前缀 区间 算法
算法性能分析
1.究竟什么是时间复杂度 时间复杂度是一个函数,它定性描述该算法的运行时间。假设算法的问题规模为n,那么操作单元数量便用函数f(n)来表示,随着数据规模n的增大,算法执行时间的增长率和f(n)的增长率相同,这称作为算法的渐近时间复杂度,简称时间复杂度,记为 O(f(n)) 2.什么是大O 算法导论给 ......
文心一言 VS 讯飞星火 VS chatgpt (107)-- 算法导论10.1 5题
五、用go语言,栈插入和删除元素只能在同一端进行,队列的插入操作和删除操作分别在两端进行,与它们不同的,有一种双端队列(deque),其插入和删除操作都可以在两端进行。写出4个时间均为 O(1)的过程,分别实现在双端队列的两端插入和删除元素的操作,该队列是用一个数组实现的。 文心一言: 在 Go 语 ......
[学习笔记] 前缀和与(树上)差分
还是复习笔记,因为我发现我都不会 数组 \(a=[1,9,1,9,4,5,1,4].\) 前缀和 前缀和数组 \(s = [1,10,11,20,24,29,30,34]\). 如何计算? \(s_i = s_{i - 1} + a_i\)。 有什么用? 计算区间和,区间 \([l,r]\) 的和就 ......
算法异或的运用
题目描述 在一条无限长的路上,有一排无限长的路灯,编号为1,2,3,4,…。 每一盏灯只有两种可能的状态,开或者关。如果按一下某一盏灯的开关,那么这盏灯的状态将发生改变。如果原来是开,将变成关。如果原来是关,将变成开。 在刚开始的时候,所有的灯都是关的。小明每次可以进行如下的操作: 指定两个数,a, ......
算法之动态规划(DP)求解完全背包问题(状态转移式方程推导)
完全背包是01背包的进阶版。在这里补充一下代码随想录的完全背包状态转移式的推导。有兴趣的可以先看一看原版。 状态转移方程 状态:dp[i][j] 选择前i个物品,容量为j的背包时 所选物品价值总和最大。 状态转移: dp[i][j]=max(dp[i-1][j-k* v[i]]+k* w[i]) ( ......
基础算法--字符串
\(KMP\) \(KMP\) 算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,效率很高,但是确实有点复杂。 基本概念 \(1\)、s[ ]是模式串,即比较长的字符串。 \(2\)、p[ ]是模板串,即比较短的字符串。(这样可能不严谨。。。) \(3\)、“非平凡前缀” ......
文心一言 VS 讯飞星火 VS chatgpt (106)-- 算法导论10.1 4题
四、用go语言,重写 ENQUEUE 和 DEQUEUE 的代码,使之能处理队列的下溢和上溢。 文心一言: 在 Go 语言中,我们可以使用切片来实现队列。下面是如何实现 ENQUEUE 和 DEQUEUE 操作,同时处理队列的下溢和上溢的情况: package main import "fmt" t ......
【ACM算法】整数分块
思考如何计算以下算式: \[\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor \qquad (n \le 10^6) \]所有人都会觉得这个非常简单,一个for循环可以直接解决,时间复杂度 \(O(n)\),但是如果将 \(n\) 的范围改大一点点,改成 \(n\ ......
Letter Picking (CF D) (区间DP, 暴力)(0,1,2 Alice 平 bob ,尽可能小,尽可能大)
思路 : 区间dp(区间DP的时间复杂度 不一定是 n^3 ,可能是 n^2 更具题意) 直接题 直接 区间dp, 0 Alice 赢 1 平局 2 Bob 赢 (于是 alice 尽可能小, bob 尽可能大) alice 选 l , bob 可以选 l+1, 或者 r alice 选 r , b ......
合并区间(区间排序,vector的动态扩容的应用)
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。 示例 1: 输入:intervals = [[1,3],[2,6],[8,10],[ ......
10.5算法
对称二叉树给你一个二叉树的根节点 root , 检查它是否轴对称。 示例 1: 输入:root = [1,2,2,3,4,4,3]输出:true示例 2: 输入:root = [1,2,2,null,3,null,3]输出:false 提示: 树中节点数目在范围 [1, 1000] 内-100 <= ......
【知识点】如何找到正确的算法?
算法思路 一、多组查询 · 考虑如何利用已知信息避免重复查询。 · 考虑各种预处理,例如前缀和。 二、规模减小 · 考虑树、链等 三、以小见大 · 考虑特殊情况,并考虑以此为基础继续转移 四、模拟优化 · 考虑高维复杂度算法,并考虑尽可能优化 五、题面信息 · 数据规模 \[n≥10^8:O(\lo ......
【知识点】如何找到正确的算法?
# 算法思路 **一、多组查询** · 考虑如何利用已知信息避免重复查询。 · 考虑各种预处理,例如前缀和。 **二、规模减小** · 考虑树、链等 **三、以小见大** · 考虑特殊情况,并考虑以此为基础继续转移 **四、模拟优化** · 考虑高维复杂度算法,并考虑尽可能优化 **五、题面信息** ......
2023“钉耙编程”中国大学生算法设计超级联赛(3)
题解: https://files.cnblogs.com/files/clrs97/2023HDU%E7%AC%AC%E4%B8%89%E5%9C%BA%E9%A2%98%E8%A7%A3.pdf Code: A. Magma Cave #include<iostream> #include<al ......
【基础算法】排序算法 —— 插入排序
一、算法原理 插入排序将数组分为已排序区间和未排序区间,初始已排序区间只有数组第1个元素,未排序区间从下标 1 开始到数组末尾。每次取未排序区间的第1个元素,将它插入已排序区间的合适位置,并保证已排序区间一直有序。重复这个过程,直到未排序区间为空,算法结束。 给有序数组(已排序区间)插入1个新元素, ......
【基础算法】排序算法 —— 选择排序
一、算法原理 选择排序将数组分为已排序区间和未排序区间,每次选择未排序区间的最小元素,将它放到已排序区间末尾。一次选择会让一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序。 示例:使用选择排序对数组 arr = [4,5,6,3,2,1] 从小到大排序。 第1次选择: 第2次选 ......
【基础算法】排序算法 —— 冒泡排序
一、算法原理 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,如果不满足大小关系要求,就进行交换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序。 示例:使用冒泡排序对数组 arr = [4,5,6,3,2,1] 从小到大排序。 第1 ......
稳定婚姻问题(Gale-Shapley算法)
前言 今天 duck、香饽饽老板和彬彬一起出了个模拟赛,赛时T2想到了跟正解很接近的做法,但最后还是打挂了then喜提0pts,后面 duck 讲题的时候才知道是稳定婚姻板题。 看完证明之后觉得很妙,遂开坑。 只是简单整理,图一乐子吧算是。 说是稳定婚姻问题,但其实我觉得更合适的叫法是属性稳定分配问 ......
P3901 数列找不同 【莫队】
P3901 数列找不同 莫队:一种离线处理的优化暴力解法,时间复杂度在n * n^(1/2),会被卡常数,但是极为简单 推荐视频:莫队算法 点击查看代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int ......
EI 的区间加正数区间最大子段和的 polylog 做法(KTT)
非常有道理。orz EI。 首先单点修改区间最大子段和是 GSS 的经典问题。我们维护出区间和 \(sm\)、最大前缀和 \(lmx\)、最大后缀和 \(rmx\)、最大子段和 \(mx\),发现这是一种半群信息,直接线段树维护就可以了。 那么对于区间加正数问题,我们依然考虑线段树。线段树想要 pu ......
【基础算法】排序算法
一、排序算法简介 排序是对批量数据按照一定的顺序进行排列的操作。 1.1 学习排序算法的要点 算法原理、代码实现、评价算法优劣。 1.2 评价排序算法的优劣 排序算法的优劣可以从以下 3 个方面进行评价: 时间性能:最好、最坏、平均时间复杂度; 内存占用:是否原地排序,原地排序算法,特指空间复杂度是 ......
高维前缀和 (SOSDP)
介绍 一维前缀和 : $ s[i] = s[i - 1] + a[i] $ 二维前缀和: $s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] $ 当然也可以这么写: for(int i = 1; i <= n; i++) for(int j ......
关于斐波那契数列 - 1
令斐波那契数列第 \(i\) 个为 \(F_i\) \(F_0 = 0, F_1 = 1, F_2 = 1 \ …\ …\) 结论:\(F_n^2 = F_{n - 1} F_{n+1} - (-1)^n\) 不难发现,这一结论对于 \(n = 1\) 显然是成立的 接下来,运用数学归纳法 若该结论 ......
关于斐波那契数列 - 2 (平方的和)
令斐波那契数列的第 \(i\) 项定义为 \(b_i\) 。 再令 \(f_n = \underset{i = 1}{\overset{n}{\sum}} b ^ 2 _ i\) 结论:\(f_n = b_n \times b_{n + 1}\) 首先,不难发现,该结论对于 \(n = 1\) 和 ......
「高等数学」1.2 数列的极限
数列极限的定义 数列概念: 如果按照某一法则, 对每个 \(n \in \mathbf{N_{+}}\), 对应着一个确定的实数 \(x_n\), 这些实数按照下标 \(n\) 从小到大排列得到的一个序列 \[x_1, x_2, x_3, \dots, x_n, \dots \]就叫做数列,简记为数 ......
视频融合/监控汇聚平台EasyCVR人形检测算法应用汇总
安防视频监控平台EasyCVR是一个具有强大拓展性、灵活的视频能力和轻便部署的平台。它支持多种主流标准协议,包括国标GB28181、RTSP/Onvif、RTMP等,还可以支持厂家的私有协议和SDK接入,例如海康Ehome、海大宇等设备的SDK。该平台不仅拥有传统安防视频监控的功能,还具备接入AI智 ......
排序算法
在线验证算法 排序数组 算法实现 1. 快排 思路 树的前序遍历。 每次选取一个数作基准值,将小于基准值的数放在左边,大于基准值的数放在右边。遍历左子树及右子树,直到只有1个数为止。 实现 class QuickSort { public static void sort(int[] nums) { ......
归并排序算法详解
算法介绍 引用百度百科的介绍。 归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有 ......