阿里嘎多懒羊羊桑_

分类

未归档(1) 题解(36)

/ 注册

TA的专栏 36篇文章 2人订阅

15天大厂真题带刷Go题解

36篇文章 64人学习

全部文章（共105篇）

牛客算法竞赛入门课第二节习题Part2（FBI树~新建 Microsoft Office Word 文档）

牛客算法竞赛入门课第二节习题Part2（FBI树~新建 Microsoft Office Word 文档） FBI树题意：输出FBI树的后序遍历序列。思路：二叉树一般就是分左右两个子树，然后递归下去，在这个过程中判断一下字母就好了。题目中要求的是后序遍历，所以对于一个节点，是先输出左子树再...

2020-05-30

0 538

2020年牛客算法入门课练习赛1(ABDE)

咕咕咕~ A. 第k小数（快排，STL之nth_element）题意：给定一个序列，求第k小数的值。思路： 1.会把sort卡掉，可以用快速排序的思想来做。 2 .C++的STL里有一个 nth_element ，可以线性寻找第k小数，get了。代码： 1 . https://ac.now...

2020-05-30

0 631

UPC——2020年春混合个人训练第三十场

2020年春混合个人训练第三十场感觉题都很好就是我不会qwq 问题 A: 选举时间限制: 1 Sec 内存限制: 128 MB提交状态题目描述 C国的总统选举委员会最近遇到了一些麻烦。他们在统计各省对H先生的支持率（百分比）时，把支持率四舍五入到了整数。等他们公布结果后，该国媒体发现这些省份...

2020-05-29

0 659

图论——负环与01分数规划

图论——负环与01分数规划 Sightseeing Cows 思路： 01分数规划可以考虑二分答案，先判断边界的范围是（0，1000 ] 再来看二分的过程。关键就在于判断是否存在一个环点权之和/边权之和>mid，此时答案在右半区间，否则答案在左半区间。整理一下式子会发现因为本题里既...

2020-05-28

0 517

图论——负环以及玄学优化

图论——负环以及玄学优化负环的定义一个图中存在一个环，里面包含的边的边权总和<0 。在含有负环的图，是无法求出最短路的，因为只要是重复走这个环，最短路就会不断缩小。负环的求法基于Bellman-Ford算法若n次迭代，算法仍旧未结束，则图中存在负环，反正咋不存在负环。基于SPFA算...

2020-05-28

0 1690

牛客—— [JSOI2007]建筑抢修（贪心+优先队列）

题意：有n个建筑需要修理，修理需要时间，如果在限制时间里没有修理完成，就报废了。问最多能够修理多少个建筑。思路：贪心。先按时间限制从小到大排序，对于某个建筑，不能修理的话就跟之前修理并且修理花费时间最长比较，如果前者花费时间小，就将后者移除。维护修理花费时间可以用堆维护。代码： #incl...

2020-05-28

0 521

牛客——货币系统（思维+DP）

牛客——货币系统（思维+DP）题意：求一个集合b，使得该集合能够表示出的数与给出的集合a能够表示出的数相同，输出该集合最少有多少个元素。思路：首先我们可以知道，如果集合里的一个数可以由集合里的其他数表示出来，那么前者就没有存在的必要了。所以，在最优解里，集合b里面的元素一定是在集合a里的，...

2020-05-27

0 758

牛客—— Protecting the Flowers （贪心）

牛客—— Protecting the Flowers （贪心）题意：农夫有n头牛在破坏花朵，每头牛每分钟破坏d[i]朵花，农夫把这头牛运回牛棚的时间为t[i]（单程）,问如何运才能使得被破坏的花最少。思路：考虑贪心。其实贪心无非几种排序关键字，某单个数值，某些数值之加减乘除。对于本题，...

2020-05-27

0 592

#关于BFS的拓展（2）——双向广搜，A*

这两种都是BFS的优化方法。双向广搜相当于从起点和终点轮流进行扩展，最后如果两边各自有一个状态发生重复的话，说明这两个搜索过程相遇了，由此可以合并出起点到终点的最小步数。一般适用于最小步数模型，即把这个状态看做无向图的一个点。再有一个小优化就是每一次扩展时选择当前队列里元素个数较少的一方来扩...

2020-05-26

0 928

关于BFS的拓展（1）——多源BFS，最小步数，双端队列

矩阵距离（多源BFS）题意：给定一个01矩阵，求每个位置到所有1的最短曼哈顿距离。思路：朴素的做法是分别以每个1为起点遍历一遍，最后保留最小值，时间复杂度O（n^2）。在图论里，如果求所有点到最近起点的最短距离，可以建立一个虚拟源点，从虚拟源点往每个起点连一条边权为0的边，这时候再求一遍最...

2020-05-26

0 1278