29 蓝桥杯省赛总结(习题解惑回顾)下

陈小白     2022.04.29     算法相关     抢沙发     127人打酱油
成绩出来了,很一般的成绩省二 比赛做了九道题,感觉能对7道左右,对完答案很懵。多的不用说了,上篇已经整理了原因和一些问题。 填空没太多疑惑 直接大题 1.算个花费日子的数量,很简单,可以直接算出。当时循环做的,想做完优化,可是忘了,条件<写成了<= ...

28 拓扑排序BFS实现思路疑惑

陈小白     2022.04.28     算法相关     抢沙发     124人打酱油
拓扑排序bfs的实现既可以使用队列也可以使用栈,当路径唯一时,两者结果并无差异。原因是因为后排的元素是相互独立的。 模板题:http://poj.org/problem?id=1094 思路: 找度为0的元素,入列查找关系 对应关系减度 反复直到队列为空 没太...

23 关于堆的判断

陈小白     2022.04.23     算法相关     抢沙发     142人打酱油
题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805064676261888 题意大概就是在一个小顶堆里面判断下根节点,父子关系,兄弟关系 不过我感觉天梯赛的题麻烦在一些输入输出,存储的形式...

18 天梯赛L2—紧急救援

陈小白     2022.04.18     算法相关     抢沙发     127人打酱油
题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840 一道迪杰斯特拉的变形题,之前我这个弱鸡基本只做了模板或接近模板的题。这道题可以很好的帮助我消化最短路径。 在看了一遍题...

18 第一次天梯热身赛总结

陈小白     2022.04.18     算法相关     抢沙发     127人打酱油
分数124,只有一道二叉树的题没有去尝试,其他的题都花费了挺长的时间去做或者去读题。 有两道题没有读明白 题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805058485469184 ...

16 数据结构 ———— 线段树(4.15更新)

陈小白     2022.04.16     算法相关     抢沙发     229人打酱油
4月15日更新 有个地方上次知识点讲述的时候说错了。线段树存储的空间是开了四倍。(我是蒟蒻,<<2应该是*4哈) 这样的话,推导也讲错了,按照最好情况讲的。 上次给同学们画的图是典型考虑的二叉树没有空间浪费的画法,没有考虑到完全二叉树画法。 而在一个二叉树中,最后一层的数...

16 SPFA算法求最短路径

陈小白     2022.04.16     算法相关     抢沙发     192人打酱油
算法适用场景:非负权,负权非负环。 算法的实现在贝尔曼福特算法的基础上适用队列优化(类似于广度优先搜索的方法)将修改后的点放入队列后设置标记,防止下一次再利用该点进行松弛,直到改点被使用后为止。 需要用到的空间:vector领接表,队列(存放点),dis[]单源最短路径,sig...

15 数据结构——树状数组的学习

陈小白     2022.04.15     算法相关     抢沙发     125人打酱油
树状数组基础操作 代码比较简单,但是用途比较受限,不如线段树用途那么广。 更多情况下,树状数组要与其他算法合用(如二分答案、前缀和优化之类的)才能发挥出最大的威力 更新 voidadd(intx) { while(x<105) { treep[x]++;...
蓝桥杯省赛参赛总结分两期更,获奖出来前和出来后 这是大一第一次参加较为正式的比赛,虽然是线上比赛,有不可避免的作弊现象,但是对于一个算法竞赛选手来讲,这并不应该成为拿不到一个好成绩的借口,算法竞赛,菜是原罪。 下面正式进入比赛分析阶段 由于是第一次参加省级别算法类竞赛,对成绩的...

06 蓝桥杯 左孩子右兄弟

陈小白     2022.04.06     算法相关     抢沙发     127人打酱油
一道将多叉数转换为二叉树的题。 具体方法,我们可以利用vector动态存储每个节点的儿子 我们最后要的是什么,是他的儿子层数和与他并列的兄弟层数。我们用max来找每个从不同的儿子节点延伸的层数的最大值,然后再加上我兄弟的数量。并在一起就是我们要求的最大层数。 代码...

05 最大子段和 三种解法 :分治、贪心、dp

陈小白     2022.04.05     算法相关     抢沙发     143人打酱油
题目链接:https://www.luogu.com.cn/problem/P1115 如题,先分析复杂度。n的范围是2*10^5,对应之前总结的复杂度问题,nlogn可以解决10^5,这个题能解决一半 从而这个题只能考虑n线性计算的复杂度,这里贪心算法和一维dp可以解决,两个...

04 贝尔曼福特(负权优化)

陈小白     2022.04.04     算法相关     抢沙发     132人打酱油
题目链接:https://www.acwing.com/problem/content/description/855/ 贝尔曼福特负权模板,额外占用的空间就是n的数量,用覆盖的方式实现。 实现起来挺容易的,在贝尔曼福特上面改改就可以了 #include<bits/st...

03 蓝桥杯 字符串转换

陈小白     2022.04.03     算法相关     抢沙发     129人打酱油
题目链接:https://www.lanqiao.cn/problems/1507/learning/ 一道小小思维的dp题 要弄明白3个操作对应的数据的位置 先说说为什么要从i+1j+1开始计算呢,因为我们初始化默认第一个元素相等更容易操作 其实如果从ij开始计算...

03 快速幂运算(更)

陈小白     2022.04.03     算法相关     抢沙发     275人打酱油
基本思想将b转换成二进制数 a^10(10)=a^1000(2)+a^000(2)+a^10(2)+a^0(2)括号内为进制 以a^b为例 while(b!=0) { if(b&1)ans=ans*a; a=a*a; b>>=1; } ...

01 蓝桥杯七段码(更)

陈小白     2022.04.01     算法相关     抢沙发     228人打酱油
在dfs中通过并查集找到有多少个根节点,当只有一个根节点的时候进行记录 从而达到去重的效果 _____________________________________ 这题真心不错,再更一波 这里除了用邻接矩阵来做,用邻接表也是挺不错的 再做一遍犯了一个小小的错误,...