51Dev开发社区
登录 注册
为你推荐

Dijkstra算法模板
自己对Dijstra算法的理解是：首先输入保存点，边的权值（注意无向图和有向图在保存时的区别）。将表示从起点st到顶点i的距离的d[i]数组的每一个值初始化为INF，令d[st]=0。 遍历d[]数组的下标i（即顶点i）这个操作是通过优先队列来实现的，然后遍历以顶点i为起点的边，更新d[i]的最小值。最后直接...
代码星球·2020-07-18

弗洛伊德算法模板
可以求得任意两点之间的最短路问题1intd[maxn][maxn];//d[st][en]表示边e={u,v}的权值(不存在时设为INF，d[i][j]=0)2intV;//顶点的个数34voidFloyd()5{6for(intk=0;k<V;k++)7for(inti=0;i<V;i++)8for(in...
代码星球·2020-07-18

匈牙利算法求最大匹配（HDU-4185 Oil Skimming）
如下图：要求最多可以凑成多少对对象大佬博客：https://blog.csdn.net/cillyb/article/details/55511666https://blog.csdn.net/denghecsdn/article/details/77619308https://www.cnblogs.com/wang...
代码星球·2020-07-18

Cat VS Dog HDU_3829（最大独立集最大匹配）
CatVSDog题意：一群小朋友去动物园，如果每个小朋友喜欢的动物是猫，那么不喜欢的动物一定是狗，反之也是。现在动物园的管理者要拿走一些动物，如果拿走的是某个小朋友不喜欢的动物，那这个小朋友就非常开心，反之，如果是某个小朋友喜欢的动物，这个小朋友就非常的不开心，问那完后最多有几个小朋友会非常开心。暑假最后一场个人赛，可...
代码星球·2020-07-18

UVA1001 Say Cheese（Dijkstra或Floyd）
题目链接：UVA1001题意：在一个巨大奶酪中的A要以最短的时间与B相遇。在奶酪中走一米的距离花费的时间是10s，而奶酪中有许多洞，穿过这些洞的时间是0s。给出A、B以及各个洞的坐标，求最短的时间。三维？？乖乖，这怎么用最短路算法。在搜了题解后才知道可以编号压缩成二维啊，这操作骚气，实在想不出来啊！！思路：将起点，终点...
代码星球·2020-07-18

UVA1395 Slim Span（kruskal）
题目：SlimSpanUVA1395题意：给出一副无向有权图，求生成树中最小的苗条度（最大权值减最小权值），如果不能生成树，就输出-1；思路：将所有的边按权值有小到大排序，然后枚举每一条边，以这条边开始利用Kruskal算法生成树，生成过程中求出权值的最大值，这个最大值减去当前枚举的边的权值就是苗条度，再动态维护一下最...
代码星球·2020-07-18

UVALive 3026（KMP算法）
UVALive3026   KMP中next[]数组的应用；题意：给出一个字符串，问该字符串每个前缀首字母的位置和该前缀的周期。思路：裸KMP直接上就是了；设该字符串为str，str字符串的长度为len，next[]的有关前缀的周期的性质：如果len%（len-next[len]）=&nb...
代码星球·2020-07-18

HDU 4027（线段树）
HDU4027题意：操作指令为0时，对区间[x,y]之间的数字进行开平方；指令为1的时候，对区间[x,y]之间的数字求和并输出；思路：线段树处理就OK了，但是64位内的数最多开8次平方就为1了（开始不信，试了试之后orz.......），所以在开平方的时候加一下限制条件使开平方操作提前结束没必要的操作就可以了，不然会超...
代码星球·2020-07-18

SGU180 Inversions（树状数组求逆序数）
题目：思路：先离散化数据然后树状数组搞一下求逆序数。离散化的方法：https://blog.csdn.net/gokou_ruri/article/details/7723378自己对用树状数组求逆序数的理解：输入数据并利用树状数组求出前边比它小和等于它的数据有几个，用输入数据的总的个数减去比它小的数就是比它大的数re...
代码星球·2020-07-18

HDU 1465（错排公式）
不容易系列之一题意：一个人要寄n个信封，结果装错了。信纸的编号为1到n，信封的编号为1到n，信纸的编号不能和信封的编号一样，全都不能一样。思路：错排公式。D(n)表示n件信封装错的所有的情况。1、将编号为n的信纸装进编号为k的信封，有n-1中装法；2、再将编号为n-1的信纸装进信封，此时有两种情况：（1）如果将编号为n...
代码星球·2020-07-18

CodeForces 580B（尺取法）
KefaandCompany题意：Kefa这个人要去吃饭，他要邀请一些朋友一起去，他的每个朋友有两个属性金钱和关系度，要求邀请的人里边任意两个人之间的金钱差的绝对值不大于d；求被邀请的所有朋友的关系度的和的最大值。思路：将朋友按金钱从小到大排序，然后对关系度用尺取法求得最大值，这里要用前缀和来求区间内的关系度的和，不然...
代码星球·2020-07-18

Sort HDU5884（二分+多叉哈夫曼树）
HDU5884Sort题意：有n个序列要进行归并，每次归并的代价是两个序列的长度的和，要求最终的代价不能超过规定的T，求在此前提下一次能同时进行归并的序列的个数k。思路：还是太单纯，看完题目一直以为要用归并排序来解题，如果已经看过多叉哈夫曼树的知识的话估计就不会这样了。先二分查找这个k，然后用多叉哈夫曼树来判断这个k是...
代码星球·2020-07-18

Entertainment Box Gym100781E(数据结构+贪心)
EntertainmentBox题意：有n个节目，每个节目给出开始时间(st)和结束时间(en)；有k个内存条这k个内存条可以同时存储节目。如果节目j的开始时间stj 大于等于节目i的结束时间，就可以放进内存条中；问这k个内存条最多可以存储多少个节目。思路：开一个multiset容器，开始压入k个0，表示k个...
代码星球·2020-07-18

P3808 【模板】AC自动机（简单版）
题意：给出n个模式串和一个文本串，问在文本串中出现了几个模式串。思路：AC自动机裸题；看过n个版本的AC自动机后终于理解了代码是如何实现的。再一次体会到光懂得原理和能利用原理解决问题之间的巨大的鸿沟。代码：#include<iostream>#include<cstdio>#include<...
代码星球·2020-07-18

Chat Group gym101775A(逆元，组合数)
传送门：ChatGroup（gym101775A）题意：一个宿舍中又n个人，最少k（k>=3）个人就可以建一个讨论组，问最多可以建多少个不同的讨论组。思路：求组合数的和，因为涉及除法取余，所以要求逆元来解题。虽然之前看到过有关逆元的知识，但是一直没有弄明白逆元的应用。嗯~~挖下的坑终于把自己给坑了。这次认栽！！最...
代码星球·2020-07-18
首页上一页...55345535553655375538...下一页尾页
按字母分类： ABCDEFGHIJKLMNOPQRSTUVWXYZ其他