- 博客(67)
- 收藏
- 关注
RSS订阅原创 【数据结构】线段树区间查询修改板子
//#pragma GCC optimize(2)#include <bits/stdc++.h>#define endl '\n'#define int long long#define INF 0x3f3f3f3f#define ull unsigned long long#define mem(a, b) memset(a, b, sizeof(a))#define ck(x) cerr << #x << "=" << x <<
2022-03-12 14:19:19
1339
原创 【动态规划】ST算法解决区间最值询问问题（RMQ问题）
一、前言RMQ问题、即区间最值问题，在遇到这类题目的时候，我们可以用暴力枚举两重for循环的方式来解决，但是这样的话会在时间上超时。如果想要不超时的话，我们也可以用线段树来解决该问题。但是我们在日常的训练中意识到：线段树的代码比较多并且比较复杂，稍有不慎的话就有可能出错。因此，在这里作者简单介绍一种写起来比较简单的算法-----ST算法。例题引入：Acwing 天才的记忆从前有个人名叫 WNB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果
2022-02-21 20:22:21
349
原创 【数据结构】线性处理字符串中指定字串的个数问题
一、问题引入给出一个长度为n的字符串S和一个长度为m的不含重复字符的字符串T，每次你可以在S中删除一个等于T的子序列，最多可以删除多少次？如字符串S=ababccd，T=abc，可以选择s1s2s5,s1s2s6,s1s4s5,s1s4s6,s3s4s5,s3s4s6进行删除，删除后分别得到abcd,abcd,bacd,bacd,abcd,abcd。如果删除后得到abcd，则还可以再进行一次删除，最多可以删除2次。这里注意，字符串T种只会包含小写字母以及T中不会出现重复的字符二、问题分析提炼一下
2022-02-15 09:59:07
703
原创 【数论】四则运算的取模处理
一、前言在日常的算法题学习中，我们有时会遇到一些题目中所需要处理的数据比较大。由于计算机的特点，我们直接处理这些大数据是会出问题的，为了避免出现这样的问题，题目中往往需要对计算中的数据或者结果取模处理，但是我们往往不能等到所有的计算结束后再取模处理，因为这样数据往往已经超出规定的范围了。因此，我们在进行运算的时候就要同时进行取模处理，在本篇博客中，会简单介绍一下四则运算的取模处理，但是限制与篇幅问题，本博客只会直接介绍处理方法，对于原理则不做证明。二、加法运算取模加法取模的处理是比较简单的。(A +
2022-01-28 09:52:37
3036
1
原创 【思维，暴力】奋发
一、题面分析题目链接：奋发题目分析：这里题目告诉我们给我们的有序单调不减数对。根据题意我们能够知道，A和B的值一定会从ai，bi到ai+1,bi+1,那么我们只需要找出每一次从ai，bi到ai+1,bi+1时A和B可能重复的次数就可以了，具体实现方法可以通过代码好好理解。二、代码分析#include <bits/stdc++.h>using namespace std;int t;int n, m;int l, r, tot;long long ans;int x[30000
2021-10-24 19:54:27
103
原创 【分层图最短路】通信线路
一、前言曾经有一场比赛分层图最短路的知识点不会导致一道比较简单的题目没写出来。然后今天看到了这道题，刚好巩固一下分层图最短路。在图论问题中，使用分层图最短路可以有效的解决有选择条件的最短路问题。不同维度之间用有向边单向连接，当状态从低维度通向高纬度时就代表进行了一次条件选择。二、题面分析题目链接：通信线路在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 Ai 和 Bi。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中
2021-10-15 09:53:19
133
原创 【二进制】Special Numbers
一、题面题目链接：Special NumbersTheofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.Let's call a positive number special if it can be written as a sum o
2021-10-09 18:40:42
302
原创 【思维、费马小定理】CQXYM Count Permutations
一、题面题目链接：CQXYM Count PermutationsCQXYM is counting permutations length of 2n.A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appe
2021-10-08 19:31:19
212
转载 【排序】动画演示10大排序算法
传载自CSDN博客：你必须知道的十大经典排序算法汇总0.排序算法种类和时间复杂度比较、时间复杂度指的就是一个算法执行所耗费的时间空间复杂度定义为该算法所耗费的存储空间1.冒泡排序（Bubble Sort）1.比较相邻的元素如果第一个比第二个大，就交换它们两个。2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数;3.针对所有的元素重复以上的步骤，除了最后一个;4.重复步骤1〜3，直到排序完成。点击查看演示动图function bubbleS
2021-09-30 14:14:45
152
原创 【图论】新年好（最短路的综合问题）
一、前言这道题目的时间复杂度卡的很死，需要在算法设计和细节上仔仔细细的考虑才能通过。非常考验对最短路算法的基础理解和灵活运用，是一道值得细细品味的图论题。二、题面分析题目链接：Acwing：新年好重庆城里有 n 个车站，m 条 双向 公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b
2021-09-30 12:20:34
376
原创 【排列组合、思维】Combinatorics Homework
一、前言CF经典折磨…如果没能想到结论的话就是疯狂的折磨,没有尽头的那种.这种题目也只能通过不断写写CF来长长见识了.一边写一边庆幸自己没打这场Div2，否则是真的太自闭了。二、题面讲解Combinatorics Homework先放出英文题面吧You are given four integer values a, b, c and m.Check if there exists a string that contains:a letters 'A';b letters 'B';c
2021-09-24 17:46:08
162
原创 【图论】昂贵的聘礼（最短路变形）
昂贵的聘礼一、前言二、题目展示三、题目分析四、题目代码讲解一、前言最近遇到的最恶心的最短路问题，题目又臭又长，理解起来也需要花时间。但是是一道不错的题目。二、题目展示题目链接：昂贵的聘礼年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用 10000 个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要 8000 金币。如果你能够弄来他的水晶球，那么只要 50
2021-09-23 21:28:42
111
原创 【图论】最优乘车（最短路变形）
一、题面例题链接：Acwing 最优乘车H 城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。现在用整数 1,2,…N 给 H
2021-09-22 21:35:35
175
原创 【图论】关于Dijkstra与Spfa算法区别的思考和分析
Dijkstra与Spfa算法区别的思考和分析一、前言二、算法原理区别分析1.Dijkstra分析2.Spfa分析三、例题讲解分析1.例题链接：[Acwing 香甜的黄油](https://www.acwing.com/problem/content/1129/)2.题目分析3.正确代码一、前言在最短路问题中，Dijkstra算法与Spfa算法都是比较常用的算法。但是如果学习了这两个算法我们就能发现Dijkstra算法的优先队列优化与Spfa算法的代码极为相似，如果不去深入了解两个算法的原理与区别的话在
2021-09-20 15:59:31
1306
1
原创 【数据结构】可以逃课其它字符串算法的字符串哈希算法
一、例题引入Acwing 字符串哈希给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。输入格式第一行包含整数 n 和 m，表示字符串长度和询问次数。第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。注意，字
2021-09-17 14:19:01
180
原创 【数据结构】堆的手动模拟实现
例题链接：Acwing 模拟堆维护一个集合，初始时集合为空，支持如下几种操作：I x，插入一个数 x；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第 k 个插入的数；C k x，修改第 k 个插入的数，将其变为 x；现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。输入格式第一行包含整数 N。接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。输出格式
2021-09-14 22:23:57
192
1
原创 【数据结构】图文例题详解单调栈与单调队列
单调栈与单调队列一、前言二、单调栈1、单调栈的概念与实现方式2、单调栈代码实现三、单调队列1、单调队列的概念与实现方式2、单调队列代码实现一、前言在学习了最基本的栈和队列的知识点后，我们可以通过栈和队列解决一些更加复杂的问题，也可以通过栈与队列来优化一些算法的时间复杂度。在本博客中，笔者将介绍一下单调栈与单调队列的概念与实现方法。二、单调栈1、单调栈的概念与实现方式与栈不同，单调栈中的元素必须保证某种单调性，可以是单调递增，也可以是单调递减。当然，为了保证栈中的元素单调，我们需要在入栈时进行一定的
2021-09-11 09:43:47
190
原创 【解题报告】Jury Meeting （9.8CF div2）
解题报告知识点总结题面思路正确代码知识点总结排列组合思维乘法取模题面题目链接：Jury Meeting （9.8CF div2）C. Jury Meetingn people gathered to hold a jury meeting of the upcoming competition, the i-th member of the jury came up with ai tasks, which they want to share with each other.
2021-09-09 09:06:07
406
原创 【解题报告】表达式求值（栈，表达式树）
题目链接：Acwing 表达式求值题面给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。注意：数据保证给定的表达式合法。题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。题目保证表达式中所有数字均为正整数。题目保证表达式在中间计算过程以及结果中，均不超过 231−1。题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小
2021-09-07 21:52:10
155
原创 【数据结构】图文讲解神奇的单链表与双链表
单链表与双链表一、前言二、单链表概念讲解三、单链表代码讲解add_head()函数insert()函数del()函数四、双链表一、前言在平时我们的作业中，我们有可能会遇到对于数组需要进行一个数或者是一批数的插入处理。在这里我们如果采用传统暴力插入的话，每一次插入处理我们都是O(n)的时间复杂度，如果我们插入的次数一旦变多，那么很容易就会超时，在这里我们需要学习一种数据结构----链表。本篇博客建议与博主另一篇博客一起学习理解（【图论】链式前向星）二、单链表概念讲解在链表中，我们依然使用数组来模拟，
2021-09-06 22:44:53
542
1
原创 C++生成题目样例文件的代码
//#pragma GCC optimize(2)#include<iostream>#include<iomanip>#include<cstdio>#include<string>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<map>#include<stack>
2021-08-23 13:36:30
448
原创 【图论】图文详解匈牙利算法
匈牙利算法一、一些概念1.二分图2.二分图的匹配二、匈牙利算法的实现步骤1.情况一（你是我的唯一）2.情况二（你们都是我的翅膀）3.情况三（我会把你抢过来）4.情况四（我爱的人已经有了爱人）三、匈牙利算法的代码实现一、一些概念1.二分图一定不含有奇数环，可能包含长度为偶数的环， 不一定是连通图二分图是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in
2021-08-18 13:39:37
2180
原创 【图论】染色法判定二分图详解
染色法判定二分图一、二分图二、染色法1.算法实现思路2.DFS深度优先遍历代码实现3.BFS广度优先遍历代码实现一、二分图一定不含有奇数环，可能包含长度为偶数的环， 不一定是连通图二分图是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。
2021-08-15 17:10:46
2039
原创 【图论】Prim算法求最小生成树详解
Prim算法一、算法学习前先要知道1.最小生成树（必须了解）2.Dijkstra算法（建议了解）二、算法实现步骤1.初始化2.寻找三、算法的代码实现1.朴素Prim算法实现2.Prim算法优先队列优化一、算法学习前先要知道1.最小生成树（必须了解）对于无向图G(V,E),连接所有点V以及边集是E的子集的树称为G的生成树。而边的权值和最小的树即为G的最小生成树。2.Dijkstra算法（建议了解）Prim算法与Dijkstra算法在思路上非常相似，如果能理解Dijkstra算法的话对于Prim算法的
2021-08-13 14:20:57
1973
原创 【紫书第十一章】图论模型与算法入门
图论基础前言一、无根树转有根树二、表达式树三、最小生成树四、最短路问题1.Dijkstra算法2.Bellman_Ford算法3.Spfa算法4.Floyd算法前言有关图论的更多知识点请移步作者“图论与数据结构”专栏。专栏地址：图论与数据结构专栏一、无根树转有根树问题描述：输入一个n个结点的无根树的各条边，指定一个根节点要求转化为有根树。分析：树是一种特殊的图，我们可以用vector数组来存下这个图。然后定义一个数组p[n],p[i]为i的父节点。代码实现#include<iost
2021-08-12 17:42:04
272
原创 【图论】Kruskal算法求最小生成树详解
Kruskal算法求最小生成树一、算法学习前先要知道1.最小生成树概念2.数据结构：并查集二、Kruskal算法实现步骤1.把所有的边排序2.遍历所有的边三、Kruskal算法的代码实现一、算法学习前先要知道1.最小生成树概念对于无向图G(V,E),连接所有点V以及边集是E的子集的树称为G的生成树。而边的权值和最小的树即为G的最小生成树。2.数据结构：并查集博客链接：并查集介绍以及例题二、Kruskal算法实现步骤1.把所有的边排序把所有的边按照边的长度从小到大排序。对此，我们可以把边的起点
2021-08-12 15:31:47
1734
原创 【紫书第十章】数论与概率入门
数论与概率入门一、数论初步1.欧几里得算法(辗转相除法)2.素数筛-埃氏筛3.素数筛-欧拉筛4.扩展欧几里得算法5.快速幂二、概率基础1.容斥原理2.杨辉三角和二项式定理3.离散概率基础三、其它数学专题1.汉诺塔2.斐波拉契数列一、数论初步1.欧几里得算法(辗转相除法)在求两个数的最大公因数时，我们通常使用欧几里得算法来求解。int gcd(int a,int b){ if(b==0)return a; else return gcd(b,a%b);}最小公倍数：(a*b)/最大公约数
2021-08-11 19:01:01
254
原创 【紫书第九章】动态规划(DP)常见模型汇总与DP问题分析方法
看完了紫书第九章还是有一点迷茫，dp果然是一个比较抽象和困难的知识点，这里结合学长（CSDN账号：蹲坑玩手机）上课的课件和看完紫书后自己的一些思考来记录一下dp学习的心得。一、基础dp1.性质：拥有子问题，子问题最优解（即拥有最优子结构），对于一个原问题解最优，其子问题必定也是最优，同时原问题的最优解依赖于其子问题的最优解子问题重复性，一个子问题可能会影响多个不同的下一阶段的原问题无后效性，即此时的之前状态无法直接影响未来的决策，换句话说就是之前的每个状态如何得来并不影响未来对此时（当前）状态的
2021-08-10 17:26:34
1339
1
原创 【紫书第八章】算法的时间优化设计
一、算法的时间优化需要提前知道的知识点：时间复杂度例题：给你一个数组a[N],要求求出最大连续和。1.暴力枚举起点和终点(下策)最不需要动脑子的算法，暴力枚举就可以了。int a[N];void solve(){ int ans = a[1]; for(int i=1;i<N;i++) for (int j = i; j < N; j++) { int sum = 0; for (int k = i; k <= j; k++) sum += a
2021-08-07 16:15:45
483
原创 【紫书第七章】暴力美学(能用暴力解决的事情为什么要动脑子?)
一、简单枚举1.寻找被枚举量之间的关系例题博客：紫书 p182 除法 (作者：Barsaker)题意分析：本题看上去是需要枚举两个数字不重复的5位数或4位数（前导0），但是我们发现只要枚举好了第一个数就可以计算出第二个数。然后判断两个数是否数字都不相同。我们可以用一个函数来实现判断两个数是否符合数字不重复这个条件。然后我们可以枚举第一个数字（12345~98765）来确定所有第二个数字。小结：当我们需要枚举两个或更多数字、变量时，我们可以寻找需要枚举的变量之间的关系，通过已经确定的变量来减少需要枚
2021-08-06 16:07:40
242
原创 【紫书第六章】二叉树、欧拉图基本概念与性质
一、二叉树的编号对于一个数组tree[N]而言，我们如果把tree[1]作为根节点，那么tree[i]的左儿子节点坐标为tree[i * 2]，右儿子坐标为tree[i *2+1]。这是一个非常重要的知识点。例题博客：紫书p148例题6-6 小球下落(作者：maplegam)思路：本题很容易就能想到暴力的思路，但是暴力的时间复杂度并不能让我们解决这一个问题，因此我们需要换一个思路去解决这个问题。书上提到：使用题目给出的编号i，当i为奇数时，它是往左走的第（i+1)/2个小球 。通过这条性质，我们
2021-08-05 12:40:43
783
原创 【紫书第六章】链表(list)、栈和双向队列(deque)
一、链表：list1、用处及优势链表对于一段数据的插入和删除操作具有很大的优势。而在数组、vector中，对于数据的插入与删除操作往往需要较高的时间复杂度。2、STL中list的常见用法 cout << "预设长度和值" << endl; list<int>l1(10, 0); for (list<int>::iterator it = l1.begin(); it != l1.end(); it++) { cout << *it
2021-08-04 11:06:57
152
原创 【紫书第五章】String、结构体、部分STL的常见用法
一、String相关1、带空格的字符串输入string a;getline(cin,a);2、字串的截取 string s = "sfsa"; string a = s.substr(0, 3); string b = s.substr(); string c = s.substr(2, 3); cout << a << endl; cout << b << endl; cout << c << endl;输
2021-08-03 16:07:10
130
原创 【解题报告】图论基础练习（一）
涉及知识点1.拓扑排序2.Dijkstra求最短路3.Dijkstra变形4.Bellman_Ford算法题目1.拓扑排序描述由于今天上课的老师讲的特别无聊，小Hi和小Ho偷偷地聊了起来。小Ho：小Hi，你这学期有选什么课么？小Hi：挺多的，比如XXX1,XXX2还有XXX3。本来想选YYY2的，但是好像没有先选过YYY1，不能选YYY2。小Ho：先修课程真是个麻烦的东西呢。小Hi：没错呢。好多课程都有先修课程，每次选课之前都得先查查有没有先修。教务公布的先修课程记录都是好多
2021-07-29 16:58:35
155
原创 南华大学【软卓】【ACM协会】【其它学习生活方面】Q&A
一、前言：对学弟学妹们的碎碎念在文章开始之前，请允许我，南华大学ACM协会20级会长，代表ACM队全体成员对21级计算机学院的全体新生表示欢迎！来到这里，你们或许充满迷茫，或许充满野心，或许心怀期待，但我认为目前你们心里更多的还是疑惑与好奇。你们会思考在花样与种类繁多的部门与社团中自己该如何做出选择，你们会思考自己在一个全新的、完全不同于高中教育模式的大学生活中该如何学习。在你们中，也许会有在今年6月考试中超越了自己的勇士，也许会有在梦想之路上暂时受挫的失意者，也许会有意料之外来到这里的迷茫者…现在的你们
2021-07-28 20:45:53
1439
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人