阿里嘎多懒羊羊桑_

未归档

题解(36)

/ 注册

全部文章 / 未归档（共25篇）

算法实验（一）递归与分治

求运行时间快速排序 #include using namespace std; const int maxn=1e6+7; int a[maxn],n; int Partition(int *a,int p,int r){ int i=p,j=r+1; int x=a[p]; ...

2021-08-17

0 588

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 516

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

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

2020-05-28

0 1690

#关于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

牛客——中位数图（思维）

[CQOI2009]中位数图（思维）思路：感觉这个题很偏向思维，原谅本蒟蒻看了题解后才想明白。首先要考虑到的就是题目中的大小关系都只是一个相对的关系，所以大于b的数对答案的贡献都是一样的，小于b的数对答案的贡献都是一样的。不妨就设大于b的数的值为1，小于b的数的值为-1，等于b的数的值为0。...

2020-05-24

1 657

牛客——简单瞎搞题（bitsit优化DP）

UP:好像01的东西都会有些奇奇怪怪的优化，比如双端队列BFS就是一个很秀的算法。https://blog.csdn.net/weixin_45675097/article/details/106265696 前言：（bitset的学习）很容易看出来是背包问题，我们用dp[i] [j] 表示只由前...

2020-05-24

0 751

牛客——「土」秘法地震

牛客每日一题—— 「土」秘法地震题意：问有多少个大小为k*k的矩阵的元素之和至少为1 思路：因为矩阵的大小已经固定，我们可以直接枚举一下左上角的区间端点，这样就可以根据端点和矩阵大小得到右下角的端点。这时候如果再遍历区间的话，复杂度就是O（n^4），所以我们要想办法优化一...

2020-05-22

0 551