- 博客(50)
- 收藏
- 关注
RSS订阅原创 搜索:flood fill,DFS连通性与剪枝优化
BFS flood fill flood fill模型可以在线性的时间内，找到一个连通块。例子：城堡问题 思路：枚举每一个格子，判断它是否于其他块连通，如果连通，扩展其他块。直到不连通为止，更新最大面积。#include<iostream>#include<algorithm>#include<queue>using namespace std;const int maxn = 55;const int dx[4]={0,-1,0,1},dy[4]={
2022-03-12 12:57:23
1196
原创 数论2:欧拉函数,快速幂，扩展欧几里得算法
欧拉函数 欧拉函数f(n):1-n中与n互质的数的个数。互质指两个整数只有1这一个公约数,或者说最大公约数为1,gcd(a,b)=1。eg.f(6) = 2. 根据唯一分解定理:N=p1a1p2a2…pnan 可以得到欧拉函数f(N) = N*(1-1/p1)(1-1/p2)…(1-1/pn)欧拉函数的证明可以利用容斥定理。int Eula(int t){ int ans = t; for(int i = 2;i <= t / i;i++) {
2022-03-06 23:03:49
323
原创 数论:线性筛、埃氏筛与欧几里得算法
质数 数论部分在算法中也相当重要，掌握基本的数论内容十分必要。1.质数定义 对于大于1的整数而言，只有1和本身两个约数则其被称为质数或素数。2.试除法 if(t <= 1) { puts("No"); continue; } for(int i = 2;i <= t / i;i++) //注意判断条件,不要写成i * i <= t 不然i可能会溢出 { if(t % i == 0)
2022-03-06 10:51:47
329
原创 时间复杂度分析
1.根据数据范围判断时间复杂度 一般C++一秒可以执行107-108次运算，那么就可以根据数据量，判断算法类型。1.n<30,指数级别，dfs+剪枝,状态压缩dp2.n<100,O(n3) floyd,dp3.n<1000,O(lognn2) dp 二分4.n<100000,O(nlogn) 排序，map/set,5.n<1000000,O(n) 双指针，KMP，并查集或常数较小的O(n*logn) spfa。6.n<10000000,O(n) 双指针
2022-03-05 10:42:38
849
原创 贪心：区间问题
区间问题 区间问题是贪心问题的一大类，处理区间问题通常可以从排序入手。可以按照左端点排序，右端点排序或者双关键字排序。区间选点#include<iostream>#include<algorithm>using namespace std;const int maxn = 1e5 + 10;int n,ans;struct Range{ int l,r;}range[maxn];bool cmp(Range a,Range b){ return
2022-03-03 11:35:20
376
原创 dp2:线性dp、区间dp、计数dp.
线性dp 动态规划时间复杂度分析，状态数目与状态转移次数相乘。数字三角形数字三角形以集合的观点考虑dp问题。#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int maxn = 510;int n,ans;int a[maxn][maxn],f[maxn][maxn];int main(){ cin>>n;
2022-03-01 09:50:04
744
原创 最小生成树和二分图
Prim与dijistra比较像，分为朴素版和堆优化版。朴素版Prim，时间复杂度O(n^2)，一般用于稠密图。算法流程：初始化距离矩阵为0x3f3f3f3f.循环n次，找到距离集合最短的点t，用t更新其他点到集合的距离。注意：与dijistra不同的在与距离的更新方式。Prim最小生成树#include<algorithm>#include<iostream>#include<cstring>using namespace std;const in
2022-02-25 23:25:52
172
原创 微分方程基本模型
微分方程的求解 利用MATLAB求解微分方程，利用现有的接口。dsolve求解解析解solver求解数值解人口预测模型简单的人口自然增长模型，不考虑环境资源限制。自然增长模型，不能正确地描述人口的增长。因为自然资源有限。Logistic模型考虑自然资源的限制，自然增长率随着人口增加线性减少。LV捕食模型种群相互竞争模型不考虑竞争时，种群演变符合logistic模型。对于甲种群而言，考虑乙对甲的竞争作用。传染病模型SISISSIRSIRS...
2022-02-17 09:35:18
282
原创 美赛A,B,C题
2021美赛A,B,C三类题目简单讲解思路。A模型建立，第一问中考虑多种真菌共存情况下分解。暂时不考虑相互作用。第二问考虑相互作用来改进模型。 第三问可视为对第二问的补充，在第二问中可以将环境因素视为不变。而对于第三问而言，环境因素是改变的，不同的真菌分解能力也会改变。模型进一步扩充。(在数据量不够的情况下，考虑微分方程。量足够可以考虑统计类，例如回归模型)对第四问而言，因为环境不同。因此，可以考虑：修改第三问中方程的相关参数进行对比分析。对第无问而言，在前两问基础上，加以讨论多样性即可。
2022-02-16 20:50:16
995
原创 动态规划-背包问题
动态规划在运筹与算法竞赛中都是重点，没有固定的模板。有着几类基本的模型，其中，背包问题是最常用的模型之一。它包含了许多类型的问题，熟练掌握基本模型是必要的。对于动态规划问题而言，确定问题的状态与状态之间的转移是基本的两点。 问题的状态 ：简单地说，一个问题可以用几维来表示，每一个状态的含义是什么。通常从集合和属性两个角度考虑状态表示。属性一般有三种：最大值，最小值，总数目。 状态转移 ：由当前状态转移到下一个状态。可以视为集合划分。一般要做到不重不漏，使得原问题划分为更小的子问题。 DP优化
2022-02-10 19:11:19
270
原创 优化2：非线性规划应用及模板
非线性规划 非线性规划在求解起来更困难，没有适用于任何情况的方法。不同的问题，需要不同的算法。因此掌握接口的使用是必要的，而且需要积累模型建立时的一些技巧。技巧1： 例子中xi只能取0或1，等价地在约束中建立方程xi(xi-1) = 0。求解 更重要的，要掌握MATLAB接口的调用。注意，API中规定：非线性不等式约束右端必须是0。 接口里包含了线性规划的部分参数A,b,Aeq,beq,lb,ub。使用方法与linprog是一致的。其余参数需要注意。 fun是目标函数，需要用.m文
2022-02-08 22:40:56
350
原创 优化：线性规划,整数规划应用及模板
优化类问题在国赛与美赛中都比较常见，尤其国赛，一般都有一道运筹优化类。优化类问题涉及内容很多，再结合图论相关的算法，加在一起是难点也是重点。例如21年国赛C题，考点很清晰，数据处理内容：插值拟合，降维。结合运筹的多目标规划与动态规划，最终利用启发式搜索遗传，模拟退火等等求解。线性规划 理论部分并不难，接口也很容易。 但是，一般不会直接考查。为了体现区分度，会涉及一些技巧。对于线性规划问题而言，目标函数以及约束条件必须都是线性函数。而对于部分问题，可以转换为线性规划问题求解。接着，上应用
2022-02-07 22:36:43
1297
原创 预测:时间序列&LSTM
时间序列 时间序列预测，可以对小样本预测。使用时间序列预测，数据必须要满足平稳性要求。平稳性： 要使用时间序列预测数据，数据需要满足稳定性要求。一般要求数据的均值和方差不发生明显变化。 严平稳：高斯白噪声即高斯分布，也就是标准的正态分布。它的均值和方差不发生变化。一般在真实的数据集上，很难达到。通常采用的是宽平稳。 宽平稳：数据的期望与相关系数，不发生明显变化。例如，要预测今天的下雨量，那么它依赖于昨天的下雨量，而昨天的下雨量依赖于前天的下雨量。这期间的相关系数不应变化很大。 为了使数据满
2022-02-05 16:25:36
3011
原创 图的最短路
最短路：可以分为单起点终点最短路和多起点多终点最短路。它包含了很多算法Dijkstra，floyd等等。当图中，边权全都是正数，一般采用Dijkstra朴素Dijkstra 它的时间复杂度只和点有关，适用于稠密图(边较多)。一般而言，如果m与n^2是一个级别可以认为是稠密图。//时间复杂度O(n^2),n是点数堆优化Dijkstra 适用于稀疏图(边较少)//时间复杂度O(m*logn) m是边数 存在负权边，可以采用bellman-ford，spfa，Floyd。bel
2022-02-01 18:21:24
519
原创 c++ 搜索与图的遍历及拓扑排序
DFS DFS在搜索中，拥有的空间复杂度与树(解空间构成的搜索数)的高度成正比，但是搜索的点不具有“最短路”的概念。//算法框架void dfs(int n){ if(搜索结束){ 记录结果。 return; } for(遍历所有解){ if(合法的解){ 占位。 } dfs(n+1); 取消占位。 }}BFS BFS在搜索中，需要大量空间是树(解空间构成的搜索数)的高度的指
2022-01-30 22:46:59
886
原创 数学建模序言
想找一找美赛常用的考点，逛了一大圈没有任何收获。又看了看一些教程，感觉它们很难直接应用到美赛上，不系统地掌握很难应用。况且，数学建模又不是只有算法，包括画图，软件使用，甚至排版等等。无奈之下，选取最基本的策略，广撒网。 数学建模毕竟是利用算法解决问题，那么一定有考纲主要有如下几类：预测类算法评价类算法分类与聚类关联因果分析优化类 基本的分类如上，对于以上算法，博主比较喜欢优化类，它主要包含了图论与运筹。我将尽可能多的将原理与代码一并附上。对于其他类都会涉及，只挑重点。之后还会补充深
2022-01-28 00:07:39
850
原创 C++ STL库
STL包含的内容很多，部分容器以及算法等等。本节主要介绍容器。//各容器公有函数size(); // O(1) 求长度empty(); //O(1) 判断空vector#include<vector>//使用时包含头文件定义一维vector<int> v//其中,int可换为其他类型，重点要掌握结构体类型。vector<int> vec(10);//定义10个元素vector<int> vec(10,3);//定义10个值为3定义二维
2022-01-27 22:24:07
716
原创 Trie树,并查集,堆与哈希表
Trie字典树Trie又称字典树用来高效的存储与查找字符串。例题：字符串统计模板如下：int son[maxn][N],cnt[maxn],idx; //其中N的取值和题目有关，例如字符串全是小写字母则N = 26//son[][]数组用来存储字符串，本题中它存储的是字符串中每个字符的下标,cnt[i]表示以i结尾的字符串总共出现的次数。void insert(char str[]){ int p = 0; for(int i = 0; str[i] ;i++){ //因为字符数组
2022-01-22 15:52:40
231
原创 单调栈、单调队列以及KMP
单调栈 单调栈主要用来解决：对于给定的一串数据序列，对于其中的某一元素，找到在它左边比它小的元素。例题：单调栈对于例题而言，最简单的思路就是枚举，简单而言，但是显然会超时。那么就要做优化。代码：#include<iostream>using namespace std;const int maxn = 1e5 + 10; int stk[maxn],tt;int main(){ int n; cin>>n; for(int i=0;i<n
2022-01-20 17:16:04
191
原创 链表、栈与队列
链表 为了提高效率，算法竞赛中通常使用数组模拟链表而不采用链式结构。这种方法称作—静态链表。单链表单链表最常被用来实现邻接表，用来存储树与图。int head,idx; //head表示头指针，指向头结点。idx表示当前节点是第几个节点，从0开始计数。int val[maxn],ne[maxn];//val数组存储每个节点值，ne数组存放指向下一个节点的指针。void init(){ //初始化为空,head指向-1表示空。 head = -1; idx = 0; //idx
2022-01-15 22:39:54
200
原创 双指针&位运算&离散化&区间合并
双指针 双指针核心，利用某种性质降低时间复杂度。一般可以将O(n2)降为O(n)。这里的指针并不是指针变量。模板：for(int i=0,j=0;i<n;i++){ while(j<i && check(i,j)) j++; //这道题的逻辑}结合一个具体例题来讲解：最长连续不重复子序列#include<iostream>using namespace std;const int maxn = 1e5 + 10;int a[max
2022-01-14 13:04:46
469
原创 高精度&前缀和&差分
高精度 在c++中，高精度的实现一般利用数组，将大整数的每一位用数组存储。 存储顺序：大整数的个位存储在数组的最低位或者是0位。大整数加法模板#include<vector>vector<int> add(vector<int> &A,vector<int> &B){ vector<int> C; int t=0; //低位的进位 for(int i=0;i<A.size()||i<
2022-01-09 22:37:38
247
原创 排序与二分
今天，算法篇要续更了。内容的话对于一些算法竞赛是适用的。内容涵盖：基础算法：排序，二分，前缀和差分等等。数据结构：栈，队列，堆，哈希等等。图论与搜索：图的应用+DFS+BFS等等。贪心算法：区间问题+huffman树等等。动态规划：线性，区间等等。数学类：快速幂，博弈论等等。（这个看时间）理论补充完后，将补充习题，正文开始。排序包含：快速排序和归并排序。快速排序：1.确定枢轴量x，以及双指针i，j。2.交换元素，使得左区间元素小于等于x，右区间大于等于x。3.递归左区间，递归右区
2022-01-08 17:49:14
315
原创 python常用基础
做deeplearning离不开python。除了tensorflow，torch之外，一些经常用的基础操作也要熟练掌握，python太庞大了，涉及到太多数据结构和方法了。都记下来，也太难了吧！当然熟记一些基础操作也是十分必要的，我之前总想着，等有时间再一起整理，也是经过导师指导，开始整理。列表操作字典操作numpy数组pandas seriesI/O慢慢补充！！！...
2021-09-23 22:46:25
85
原创 c++搜索—BFS
(Happy Mid-Autumn Festival)博主前来更新c++的BFS。上篇说了DFS框架和例题，这次说BFS。先说，思想和用途。 为什么要用到BFS呢？有的时候，对于DFS而言会陷入搜索过深仍然找不到解，也就意味着超时。因此，BFS就来了。尤其在连通性，最短路等问题。 对于BFS而言，会优先考虑每种状态和初始状态的关系。距离初始状态越近，越会被优先考虑，每个时刻(阶段)要做的状态，都是由上个时刻(状态)得来的。//模板如下#include<queue>queue
2021-09-21 23:19:43
308
原创 c++搜索
更新下c++中搜索算法，用在一般算法竞赛中是DFS和BFS。当然，一些启发式搜索，例如遗传算法，模拟退火等。一般算法竞赛中不会涉及。DFS：//算法框架void dfs(int n){ if(搜索结束){ 记录结果。 return; } for(遍历所有解){ if(合法的解){ 占位。 } dfs(n+1); 取消占位。 }}算法框架如上，对于一些简单的问题，相当于填空了。经
2021-09-19 21:28:31
1300
原创 数学建模论文写作
论文写作前言：论文一定要表达清楚，因为写给评委看，如果评委没看懂，分数应该不会高。在数学建模国赛中，除了论文以外，支撑材料：程序代码，中间结果，支撑数据。也非常重要。一篇论文评分很快，不会看的特别细，出现个别小错误，也不要太担心。 数学建模论文（中文）构成：首页：论文题目，摘要，关键词。论文正文： 1.问题重述 2.问题分析 3.模型假设 4.符号说明 5.模型建立与求解 6.模型检验/模型改进与推广 7.模型优缺点评价 参考文献 附录英文版有些部分稍有不
2021-09-09 09:02:01
3754
原创 c++记忆化递归
这有一道题 题目，其实是来源于深基，和洛谷P1028差不多。当然，主要是讲解记忆化递归。一般的递归，总会面对着超时的风险，比如，在源代码中，sol(2)，可能被sol(4)调用，也可能被sol(8)调用，因此做了很多无用功。 为此记忆化递归也是常用的，在动态规划中也是比较常用的。记忆化递归，可以用一个数组，存贮递归过程中计算出的值。当需要再次计算时，直接返回数组的值就可以了。#include<bits/stdc++.h>using namespace std;int n,f[10
2021-09-05 22:19:01
957
原创 排队论简介
基本概念： 排队系统的构成：输入过程，排队规则和服务机制。为此，引入6个变量描述这个系统。X/Y/Z/A/B/C。X表示顾客相继到达间隔的时间分布：Y-服务时间分布。Z-服务台个数。A-系统中，顾客容量限额。B-系统中，顾客源限额。C-服务规则。排队系统的好坏，由排队系统的指标评价。还有，排队系统的状态。状态N(t):指t时刻系统的人数为N(t)。状态概率：Pn。 Pn(t)：瞬时状态，指t时刻系统人数为n的概率。 Pn：稳定状态，Pn=limitt→∞Pn(t)
2021-09-05 11:20:07
248
原创 层次分析，critic以及topsis
AHP，EWM及其耦合。 AHP（层次分析法）：主观评价法，结合定性和定量来分析，对难以完全定量的复杂系统做出决策。算法步骤：（1）建立层次结构模型。（2）构造判断矩阵。（3）填写判断矩阵并进行一致性检验。（4）填充权重矩阵得出结果。（1）构建层次结构 首先，需要有层次，上图是一个三层的结构。是一个基本的结构，可以加深层次，具体实例如下：（2）构造判断矩阵。就根本目的来说，要得到评价体系，也就是要得到权重。为了得到同一层次元素对上一层的元素的重要性。将该层次元素两两比较。具体实例：为了得到
2021-09-04 22:08:37
7425
原创 基本预测类算法
一：灰色预测算法G(1,1)，可用于小样本时间序列预测。首先，介绍相关基本概念。白色系统：系统的相关信息全部已知。黑色系统：系统全部信息未知。灰色系统：处于黑色和白色系统的过渡阶段，只有部分信息已知。算法流程： （1）对数据进行处理和检验：计算数列的级比：前一项和后一项的比值。如果所有的级比都落在区间(e-2/(n+1),e2/(n+1))。则满足数据满足要求。如果不满足的话，可以进行平移变换，使得原数列中每一个数据加上常数c，至于c的值，以实验为准。 （2）当数据满足要求后，就可以建立G
2021-09-02 22:33:03
7699
原创 c++位运算技巧
选数 首先先放上一道算法题（c++），一道基础题。解法很多，搜索，枚举都可以。今天以枚举来讲解这道题。不再赘述题干。 最容易想到的办法，大概就是两重循环枚举吧。外循环控制执行次数，内循环执行寻找k个数，然后，相加并判断是否为素数。内循环的实现可以用递归或者是搜索。思路很简单，但却很容易超时。那么，思路该是怎样的呢？观察数据量，n=20,k<n。暗示性极强呀，复杂度就是O(2^n)呗。那不就是枚举n的所有子集，选取其中为k个数的子集。 如果，我们将集合中，每个元素出现标记为1，不出现标记为0
2021-08-30 21:34:16
89
原创 神经网络入门
启发式算法，和图论还没有更新，我又来写神经网络了。以我浅薄的理解，简单介绍下，神经网络的入门。 神经网络的构成：从层级结构上讲，分为输入层，隐藏层和输出层。细化结构：包含了神经元，神经元之间连接方式。神经元结构： 在神经网络中，神经元接受输入并通过加权求和，经过激活函数得到输出。神经网络是要找到合适的权值，使得预测结果和真实结果之间的误差最小。权重矩阵，在网络训练的过程中是可学习的，也就是可以不断更改的。激活函数有：sgn,sigmoid,relu等。 另一种比较特殊的节点是—偏置节点。它
2021-08-28 12:21:08
311
原创 图论相关算法
图论：图论作为运筹学的分支，无论是在算法上，还是在数学建模上都具有重要的地位。本篇，介绍图论的经典问题，并给出相关的算法。1.最短路问题，指定或任意两点间最短距离。2.公路连接问题。3.CPP，TSP问题(NP-hard)。4.指派问题。5.警局设立（规划问题，动态或静态） 图论的算法:对于指定两点最短距离问题，Dijsktra算法对于任意两点最短距离问题，Floyd算法公路连接问题，本质是求解最小生成树，Prim算法和Kruskal算法。TSP问题，求解哈密尔顿回路，Fleury
2021-08-25 21:09:34
431
原创 启发式搜索算法
模拟退火： 算法步骤：给出初始温度，初始解，退火系数等参数。在温度没有达到降到最终设定的温度时，进行退火过程即进行循环迭代。在该温度下，产生新解，并计算目标函数值。如果目标函数值更优，接受新解。否则，会以一定的概率接受错误解。该过程完成，即完成一次退火。算法的核心，在与接受概率的设定。内容代补充~...
2021-08-24 22:08:08
3409
原创 几种降维算法
1.TSNE算法思想：（1）SNE，其基本思想为在高维空间相似的数据点，映射到低维空间距离也是相似的。算法利用距离表达两个点之间的相似性。常用的距离度量方式是：欧式距离。（2）t-SNE,做出的优化是用t分布取代SNE中的高斯分布，使得降维后的数据，同类之间更加紧凑，不同类之间距离加大。换言之，对应于无监督聚类指标轮廓系数更好。2.PCA算法思想：将原有的n个特征，投影到k为空间，k维度空间之间两两正交称为主成分，新的特征由原特征变换而来。算法实现：在python中通过调用模块sklearn，
2021-08-24 20:35:54
881
原创 c++ STL(2)
并查集：处理不相交可合并关系的数据结构，操作分为两种：合并和查询。用法如下：int fa[num] //用来存放上级元素。//对于代表元素而言，fa[num]=num//查询int find(int x){ if(x==fa[x]) return x; //查询到代表元素，递归终点 return find(fa[x]) //查询上级元素}//合并int join(int x,int y){ int f1=find(x), f2=find(y); if(f1
2021-07-29 16:05:00
62
原创 c++字符串基础
主要总结了字符串的一些输入，并带来了string类：对于标准的输入输出，基本输入原则输入数值型数据，输入可以采用，空格，回车，tab作为分隔符。当编译器遇到他们时会认为输入结束。输入字符型数据，在scanf中没有给出分隔符的话，所有字符都是有效的。自然，空格，回车，tab也是有效的输入。标准的输入输出,使用时包含头文件。#include<cstdio>char a[100];//scanf向字符数组中输入scanf("%s",a);//重点，不能读入空格和回车。遇到空格和回
2021-07-23 21:22:49
293
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人