- 博客(36)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 力扣(leetcode) 42. 接雨水 （带你逐步思考）
难度：hard给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。主要需要实现快速对leftmax和rightmax的求解，这个十分简单，从左到右，从右到左各一次遍历就可以求出。将结果存放到数组里后续使用即可降低时间复杂度。这里由于需要保存rightmax，消耗了O(n)的内存，有没有更节省空间的方法？
2024-04-19 03:02:14
291
原创 HDU-2196 树形DP学习笔记
树形dp特指在树这种数据结构上进行的DP。由于树本身具有子结构的性质(树和子树)，很适合用来做递归和递推，符合dp的性质。树形dp中用的比较多的是dfs算法，需要熟练掌握树的几种表示方法和树的遍历方式。对于一棵有根树，对于给定的边权值（自然数），求距离每一个结点最远的结点的距离。首先考虑一下暴力算法怎么做。暴力算法的做法即 对于每于一个结点，将该结点作为根结点求一次到所有叶子结点的距离，然后取最大值。...
2022-07-03 23:18:30
259
1
原创 蓝桥杯 本质上升序列 动态规划 详解+python代码+答案
题目内容见：https://www.lanqiao.cn/courses/2786/learning/?id=131137C题题目分析这道题，如果要用暴力的方法来做，那么会有太多的组合了（涉及到排列组合的问题，暴力都基本过不去）。所以，比较容易想到的算法是动态规划。如何动态规划呢？在动态规划中，我们每次都是对于一个小的个体来处理，来看它的加入会对结果有什么影响。比如在最长上升子序列中，我们是从前往后，遍历每一个位置的字母（个体），看以它为结尾的最长上升子序列的长度。本题中，其实思路相差不大。我们
2022-03-05 10:59:56
796
原创 蓝桥杯——平面切分
题目链接：http://oj.ecustacm.cn/problem.php?id=1524题目分析找规律就好了，从第一条边开始切分平面，可以发现每加入一条边，新增的平面个数就等于加入的边与之前的边的交点个数（去掉重复的交点）+1。AC代码from math import *def Cross_Point(k1,b1,k2,b2): global eps x=(b2-b1)/(k1-k2) y=k1*x+b1 return (round(x,eps),round(
2022-03-03 23:23:36
280
原创 蓝桥杯 子串分值 详解 python
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T792题目分析题目中比较重要的信息就是 f的值仅受到在连续字串中出现一次的字符的影响。直接统计所有子串中单个字符的个数时间上过不去，那么，我们可以考虑单个字符带来的贡献值。（核心思想：换位思考）看样例：‘ababc’我们看第二个a，虽然它可以处于多个子串中，但是如果这个子串里面还包含了其它a的话，那么这个’a’就不能对f的值产生贡献（使f的总和增加）了。而它每处于一个有效子串（除开它自己没有别的a的子串）
2022-03-01 19:34:44
1252
5
原创 大模拟 脉冲神经网络（详细解析）
题目链接：https://www.acwing.com/problem/content/4011/本来不是很想写这个题解的，因为这道题卡常严重，往届的模拟题都是纯暴力模拟就能过，不用担心会超时。我只给出我当时得70分的代码，最后大数据的这30分的优化可以参考这篇文章。简单来说就是通过拆开结构体来获取更短的时间，这与我写代码能封装就封装的主旨是相违背的。可以说这30分更加偏向于竞赛风格。题目分析：读题后可以明确两个实体和它们间的关系：实体：神经元属性：内部变量u、v。影响u、v变换的常量a
2022-02-25 00:55:45
515
原创 大模拟 CCF CSP DHCP服务器（详细解析）
题目链接：https://www.acwing.com/problem/content/description/3416/题目分析：这道题目实际难度不大，给人的感觉更像是在做阅读理解。主要难点在于提炼出有用的信息。其实题目中试题背景部分并不重要，我们直接看问题描述后面的内容即可。在实现细节部分，题目要求我们初始化ip地址池等操作，可以看出，我们主要做的就是维护一个ip地址池。而维护的方式也在该部分给的十分详细，只需按照给定的需求来编写代码，也就不会出现问题。主要容易漏掉的地方就是地址过期后状态的改变了。
2021-09-12 18:31:05
699
2
原创 2021牛客暑期多校训练营2 K题 （模拟堆栈+拓扑排序）
题目链接：https://ac.nowcoder.com/acm/contest/11253/K题目大意：对于数组a而言，可根据下列代码构造一个数组b。其中Stk是一个单调栈，单调栈满足从栈底到栈顶元素大小都是有序的。Stk is an empty stackfor i = 1 to n : while ( Stk is not empty ) and ( Stk's top > a[i] ) : pop Stk push a[i] b[i]=Stk'
2021-07-20 17:24:01
146
原创 Flood Fill 区间dp练习
题目链接：https://codeforces.com/contest/1114/problem/D题目大意给予一个长度为n的整数串，起初选取某一个位置，然后某一轮可以将与该位置连通的(连通：相邻且数字相同，连通具有传递性)所有数字全部改为另一个数字。给定整数串，问最少需要多少轮才能是所有数字变为相同的。起始位置可以任选。做法首先，很容易看出来，我们可以先对输入的数组进行压缩，即将相邻的相同的数字压缩成一个数字。（这样问题和原来是等价的）代码如下： int x,cnt=0; for(int i=
2021-07-18 16:17:47
73
原创 2021牛客暑期多校训练营1 A:Alice and Bob (筛法+对称优化)
题目链接题目大意Alice和Bob做游戏，给两堆石头，各m,n个。游戏中，每一轮必须在某一堆石头中拿去k(k>0)个石头,同时另一堆石头中拿去s*k(s>=0)个石头。最终无法执行该操作的人输掉比赛。现在Alice先手，两人均采取最优策略的情况下，谁会获胜？分析考虑采用动态规划的做法来做，定义dp[i][j]表示两堆石头分别是i,j的个数的情况下，先手的人是否获胜，等于1即获胜，等于0失败。容易发现，dp[0][0]=0，因为没得选了。然后，考虑状态的转移。对于dp[i][j]而言，两
2021-07-17 23:13:27
241
原创 [蓝桥杯][2019年第十届真题]修改数组 (线段树|并查集)
题目描述链接：https://www.dotcpp.com/oj/problem2301.html给定一个长度为 NNN 的数组 AAA = [A1A_1A1, A2A_2A2, · · · ANA_NAN ]，数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2A_2A2,A3A_3A3,··· ,ANA_NAN。当修改 AiA_iAi 时，小明会检查 AiA_iAi 是否在 A1A_1A1 ∼ Ai−1A_{i−1}Ai−1 中
2021-01-31 22:49:13
309
原创 洛谷P3951 形象的题解
题目链接：https://www.luogu.com.cn/problem/P3951题目大意：给出两个互质的整数a,b，求出使得ax+by=m(x,y为自然数)无解的最大整数m分析：(分析中先讨论a<b的情况,得到答案后可发现结果关于a,b具有轮换对称性，故a>b的情况可不予讨论)画出数轴后，可以发现如果得到一条线段（定义：b个连续的整数）上的每个整数点都被覆盖（定义：该整数有解）了。那么值大于 该线段内的整数 的整数必然也是被覆盖了的。所以如果我们能找到首个长度为b的被完全覆盖的线
2021-01-30 20:10:12
161
原创 HDU 1255（线段树&离散化&扫描线）详细解析
题目链接题目解析：该题目要求 求取众多矩形重叠部分的面积，可以采用扫描线的方法来解决。扫描线首先来看一个利用扫描线实现的 计算所有矩形覆盖区域面积（不算重复面积）的求解过程。在下图中，利用蓝线从下往上扫描所有的平行于x轴的边，当接触到的是下边的时候，将该边对应的区间值都加上1（表示该区域又覆盖了一次），接触到上边的时候，减去1（该区域少覆盖一次）。而每次扫描到边的时候，将所有上一次值不为0的区间（处于覆盖状态的区间）的区间长度和 lenlenlen 乘以两次扫描的高度差(hi−hi−1h_{i
2021-01-19 17:58:25
441
2
原创 B-树基本操作的实现 利用C++模板类封装
程序还未经过严格的测试，不能保证完全正确，仅作为学习参考。注释感觉还比较详细，我就不多bb了，直接上代码/*项目名：B-树作者：龙卡完成时间：2020/12/21 0:04个人感受：手撕B-树真的太难了，要想写好还得在每一步把所有可能的情况全部考虑完，调试过程中遇到的最严重的bug就是par指针的维护不到位，有很多情况没有维护好，导致出了bug。本来以为会让做平衡二叉树的实验，结果直接上B-树，只能说 “老赵，可真有你的”*/#include<iostream>#includ
2020-12-21 00:46:42
1206
5
原创 拓扑排序练习 CCF CSP点亮数字人生(详细解析)
题目链接#include<iostream>#include<cstdio>#include<cstdlib>#include<string>#include<vector>#include<stack>using namespace std;const int MAX_N=503;//门即为结点 int in_degree[MAX_N];enum TYPE {XOR,NOT,AND,OR,NAND,NOR};s
2020-12-09 20:10:18
976
3
原创 cf.Extreme Subtraction（逆向思维）
题目链接题意简化：对于一个序列而言，如果能够操作后全部化为0，那么用该操作的逆操作（全为0的序列上面选k加1）便可以恢复该序列。那么我们就可以把逆操作分为左和右两组，容易看出这两组操作构造出来的序列必然是一个单调不升和一个单调不降。这样，原序列就可以看成是一个单调不升序列和一个单调不降序列的和。这样，我们只需证明原序列是符合该条件的即可。构造思路：要在各位和固定的情况下构造一个单调不升序列和一个单调不降序列，根据贪心的原则，我们肯定得让单调不升序列降低得慢、单调不降序列下降的慢。这样可以给后面的构造
2020-11-17 22:01:59
202
原创 计蒜客 And and Pair 题解
题目链接分析：（将一个二进制数的每一位111的下标作元素构成一个集合）iii&nnn=iii，那么就是说i中的111是nnn中的子集。iii的个数即为nnn的子集的个数。iii&jjj=000，那么说iii与jjj没有共同位上的111，即交集为空集。故对于一个确定的i>1i>1i>1，j的个数有2m2^{m}2m个(mmm：iii中最高位111后的000的个数)所以可以想到从后往前枚举，即从小到大枚举i的最高位的位数，例如nnn=110101101011010先枚
2020-10-02 19:55:41
173
原创 CCPC网络选拔赛 Graph Theory Class
题目大意：要求一颗最小生成树，其中图的结点标号从1-n，任意两个结点(i,j)间的边权值为lcm(i+1,j+1)题意分析：其实可以直接看成编号为从2到n+1，边的权值就是lcm(i,j)然后容易想到，对于i：1.若i是质数，i与2相连的边是该质数的邻边中权值最小的，值为2*i2.若i是和数，则i与自己的因子相连的边权值最小（这里可以找其最小的质因子），值为 i所以对于质数取与2相连的边、合数取与其因子相连的边，这样得到的生成树为最小生成树。再说说这样取为什么能构成树，可以将结点按序号升序排
2020-09-23 00:00:33
419
原创 牛客 Interesting Computer Game
题目链接题目大意：给出了很多组数，每组数最多选一个，且不能选已经选过的数，求能选的数的最大个数分析：第一反应是贪心，但是发现贪心算法上面走不通。后来才知道是一道图论的题。还是题做少了啊。在题中，如果把一组数字看成是一条边，那么问题就转化为了：图中对于每条边能够取一个相连顶点，求取的顶点的最大个数。我们就可以对每个连通分量来考虑。如果连通分量是一棵树（e=v-1），那么每条边取一个顶点，该连通分量会有一个顶点无法取到。如果不是树，也就是说形成了环，那么无论是重边、自环还是圈，都可以证明可以将该连通
2020-08-07 14:49:40
125
2
原创 牛客 Kabaleo Lite
题目链接题目大意：每次取一部分前缀，使得最后的和最大。分析：每次取前缀的话肯定是取最大的，主要难点在于取的时候的限制性，但是我们发现，取得的前缀长度必然越来越短，所以我们可以想到记录下当前前缀取过的次数chose以及上一次取的位置。而一个位置能否被取到取决于:1.该位置是否是在上一次的位置之前2.考虑到可能该位置会由于菜不够了无法取到，而菜是否足够看的是使得上一次无法取的位置（菜最少的位置）在该位置之前还是之后。而对于这一点，我们可以保存下每个点对应的前缀的菜的最小数量，然后与chose比较即可
2020-08-05 23:02:26
108
原创 牛客 K-Bag
题目链接题目分析：该题目要求的是判断给出的序列是否满足part-k-bag。而容易发现，如果序列中连续的K个数均没有重复，那么这个连续子序列就是k-bag（因为值的范围是1-k，如果k个数没有重复，必定取完了1-k的所有数）。所以现在每个位置能否构成k-bag就可以通过判断以它为起点的最长无重复连续序列的长度来确定。这样我们就可以每隔k个数检查一次来判断整个串是否为part-k-bag了。但是还有一个问题，检查的起始位置该从哪里开始？由于part-k-bag的两端不一定是完整的k-bag，所以检查的时
2020-07-30 09:31:54
207
原创 牛客 Drop Voicing LIS
题目链接题目分析：题目给定了一条串，共有两个操作可以执行，并且只有Drop-2会产生花费。这就是说我们只需要把串转换成周期性的1-n就行了（比如：k—n 1—(k-1)）。而连续的多个Drop-2操作仅需一个花费，这也就可以看成是一个操作。现在我们可以对串的任意位置做Drop-2操作（因为可以通过Invert操作来将任意的位置变成倒数第二），而我们又能发现，对一个长度为K的连续字串做了Drop-2操作后，该串其实就往右移动了一个单位。反过来看，可以看成该子串的右边第一个元素左移了k个单位。（k可以任意选
2020-07-26 15:59:10
112
原创 牛客Harder Gcd Problem
题目链接题意：在1-n的整数中每次选取两个不互质的数，求最多能选多少对？分析：对于两个不互质的数，情况有两种：质数与它的倍数两个相同质数的倍数这两种情况都与一个质数有关，所以可以从每个质数来出发，将它的不同倍数两两配对。（大于n/2的质数必定没得匹配，下面均未考虑）而容易想到，必定得先满足较大的质数，因为如果先取小质数，那么大质数到时候可能就没有匹配了。例如：2和5，如果先取2的各个倍数，10就会被2用掉，如果n=10，5就没有数与他匹配，就用不掉了。而如果从大到小来，每个质数至少有自
2020-07-25 11:35:14
104
原创 Two Matchings 动态规划，思维
题目链接题意解析：题中matching指的就是一个逆元为本身的置换，并且要求不能有不变元。这样可知p中的数必定是两两配对的(互相映射)，如果p的长度为奇数必定会剩余一个数与自己配对，则无法构成matching,故长度必为偶数。cost中由于i与pi是对称的（如1映射到5时，|a1-a5|与|a5-a1|计算了两次）。所以除2后，cost的含义为每次从a中取两个数，求其差的绝对值。题解:下面的提到的数组都是排好序后的最小的取法：其实我们需要找的就是一个使得cost最小的p和次小的q，显然最小就是
2020-07-19 15:14:52
203
原创 HDU 6103 Kirinriki 尺取法
写一个反思吧，这道题拿到手真的是没有什么思路，尺取法也不是很熟悉。题目链接为什么想到用尺取法：题目要求的是一个有限定条件的连续区间的最大长度，即可联想到尺取法尺取法要求所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到根据其端点得到，那么尺取法便是不可行的。参考：尺取法 — 详解 + 例题模板(全)为什么能用尺取法：在这里能用
2020-07-15 17:52:05
122
原创 2020牛客暑期多校训练营（第二场）F
类型这道题很明显是一道单调队列的题目，这个数据结构在我之前的文章中有写到。二维化一维不过这是二维的，首先想到的是用一个单调队列来维护当前的最大值（如下图中que），由于对于每列来说只有该列的最大值是有用的，小于最大值的数不用理会（想想为什么），所以每列就存一个最大值就行，这样就变成了一维的了。由于对不同行，计算新的连续K个排在一列的数（如图中蓝框）的最大值会重复遍历相同点，时间复杂度高，可以想到能不能先把最大值全算出来再利用。求连续K个排在一列的数的最大值其实又是一个求m区间内的最小值的问题，不过
2020-07-13 18:01:17
151
原创 洛谷P3956 优先队列解法
蒟蒻来练BFS啦题目传送门分析：优先队列这道题要求的最小花费，容易想到BFS，但是不同于一般的BFS求最短路问题。因为普通的最短路问题BFS能求出最短路是因为BFS是依次按照距离从小到达遍历的，这样最先到达终点的路必然就是最短路，而且遍历的时候不用回头（回头就肯定不是最短路了）。这道题中按照相同的思想，只要我们能够按照花费从小到大遍历那就OK了，而利用普通队列是做不到的，所以很容易想到可以采用优先队列来取节点。决策题目中说到有无色的格子，将其变为有色花费为2，还有一点就是不能从无色格子走到无色
2020-06-12 20:00:30
211
原创 Solve The Maze（codeforces）
题目传送门分析： 题目要求为让所有B无法到达右下角，所有G都能到达右下角，很容易想到将所有的B周围的’.‘换掉检测条件就ok，检测的时候有个技巧，那就是从终点出发，检查所有能到的位置（单个终点或单个起点的问题就这么搞）错误原因： 第一次认为将B周围的’.'换掉B就一定出不来了，漏掉了B与G相邻的情况（相邻则G能到B也能到），改了之后发现还是wrong answer，结果是dfs写错了（心好累，我的深广搜就学的这么烂吗），其实这个dfs就是Lake counting问题，参考着写就没问题了。（我还记忆化搜
2020-06-08 10:14:57
301
原创 Count Triangles 队列解法
题目链接： https://codeforces.com/contest/1355/problem/C分析： 这道题给出了3个范围，要求求出满足不退化三角形（其实就是能构成三角形啦）的个数，看数据范围5e5，肯定不是暴力（i遍历A-B，每一个i遍历B-C）能过的题。思路： 既然暴力过不了，就优化暴力解法。取 i=A（最小边），j在B-C范围内（第二小的边），将每一个j对应的能取的三角形个数存下来（arr[j]）。同时我们也得到了i=A时，所有能构成的三角形个数。那么，当i=A+1时，相对于上一次，发现
2020-06-06 13:17:10
184
原创 Canvas Line 计蒜客
题目链接：https://nanti.jisuanke.com/t/45471解析： 这道题需要我们找出最小的钉子花费，容易发现当钉子放在相接的两块布之间时能够达到减少花费的目的，所以可以先将所有可以放钉子的相接点（两块挨着的布的连接点）放满，然后再来考虑每一个布中间位置的放置。impossible的情况只有当原有的钉子不满足条件(在某块布上已经有2个以上的钉子)C++代码：#include<iostream>#include<vector>#include<set&
2020-06-05 10:30:18
171
1
原创 UVA532 Dungeon Master反思
题目：UVA532 Dungeon Master类型：bfs 队列主要错误：标记已走过的点不及时第一次标记的位置如下注释，在判断可达到后标记，标的是当前的位置（我在想啥呢），会出现两个问题：如果当前位置没有路可走，那么当前位置不会被标记只标记当前位置会导致位置重复压入，原则上说每个位置只能让它压入一次，所以必须一旦压入就立马标记已走过while(que.size()) {...
2020-04-02 15:31:55
124
原创 洛谷P1608 路径统计（最短路数统计）
洛谷P1608 路径统计题目要求的是求出每个顶点所对应的最短路径的条数，而这道题中边的权值都为1，所以和最短路联系起来的话不难想到可以用BFS。但是毕竟我刚学了最短路系列算法怎么可能不用呢，所以在P1144中采用了Dijkstra算法 其实完全没必要，实现了后发现和BFS没啥区别主要思想： 到第i个顶点的最短路径是第i个顶点的所有前趋顶点（就是从起点到i的最短路径上i的前一个顶点）最短路径条...
2020-03-31 01:36:21
301
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人